n-queens problem은 크기가 N인 체스판에, 여왕말 N개를 서로를 공격할 수 없게 두는 것이다. 이건 꽤 흥미로운데, 왜냐면 queen은 좌우상하 대각선4방향 전부 다 되기 때문...!!! 그래서 생각보다 놓을 수 있는 곳이 한정적이다. 이걸 풀기 위해서 backtracking이라는 기법을 적용했다. 백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. 출처: https://chanhuiseok.github.io/posts/algo-23/ 일단 어떻게 거기 놓을 수 있는지 판단하는 방법부터 알아보자. 다음과 같이 (1,2)에 놓인 queen이 있다. (왼쪽 위는 0,0이..
subset은 한국말로 '부분집합'이라는 뜻이고, subset sum problem은 따라서 부분집합 더하기 문제?라고 생각할 수 있다!! subset sum problem이 어떤거냐면, total = 11이고 {2, 3, 7, 8, 10}인 집합이 있으면, 집합의 원소들을 더해서 total값을 만들 수 있는지 확인하는 문제이다. 세로줄에는 각각 원소들, 가로줄에는 0부터 total까지가 배치되어 있다고 해 보자. 2, 3, 7, 8, 10을 0개씩 쓰면 합이 0이 될 수 있으므로 첫 줄을 다 T로 채워준다. 1은 2의 합으로 될 수 없으므로 F. 2는 2의 합으로 될 수 있으므로 T. 3 이상의 값은 2로 만들어질 수 없으므로 전부다 F. 3보다 작은 값은 !!!윗줄을 그대로 채워준다 3은 T 이제 4..
알고리즘 문제중에 굉장히? 그나마 흥미로운 문제라고 생각했던 knapsack problem!!!! knapsack은 작은 배낭이라는 뜻이다...귀엽네... 가방에 어떤어떤 물건을 넣을수 있을까? 를 물어보는 알고리즘 문제다. 미국놈들은 이렇게 문제 이름은 귀엽게 짓고, 문제는 ㅈㄴ 어렵게 내는 습관이 있는 것 같다. 아무튼 가방에 어떤 물건을 넣을 수 있을지 dynamic problem으로 풀어보자 ^^ 나에게는 이런 4개의 물건이 있다. 각각은 weight과 value를 가지고 있다. 그리고 나에게는 한개의 가방이 있는데, 이 가방에는 최대 7만큼의 weight만 들어갈 수 있다. 내가 넣은 물건들의 value의 합이 최대가 되게 하려면, 어떤 어떤 물건들을 넣어야 할까??? 이를 Dynamic pro..
button.layer.cornerRadius = 5
ko.reactjs.org/docs/conditional-rendering.html