룰루랄라 알고리즘

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 학교 전공 시간에 너무 듣기 싫어서 오랜만에 문제를 풀어봤다. 물론 전공시간 동안 못 풀어서 집에서 마저 풀었다. 체스에 조예가 깊었던 나는 맘에 드는 제목을 보고 덥석 풀어봤지만 시간복잡도의 늪에 빠져 몇 시간을 헤맸다. 3트 끝에 겨우 통과했다. 그럼 내가 처음에 제시했던 아이디어와 그 이후 가지치기로 시간복잡도를 줄인 코드를 살펴보자. 3가지 방법이 생각났다. 1. Pair(x, y) 클래스를 생성 후 Se..

앞서 푼 문제 N과 M (1)에서 출력 결과가 오름차순인 조건만 추가된 문제다. 풀이가 앞선 문제와 너무 비슷하고 간단해서 올리지 말까 고민하다가 그냥 올린다. https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아래처럼 DFS를 조금만 수정해 주면 오름차순 조건이 추가되어 출력된다. DFS 백트래킹에서는 방문처리가 중요하니까 이에 신경 써서 풀자!

백준에서 N과 M 문제를 오랫동안 봐왔는데 이번 기회에 (1)부터 차례대로 풀어봐야겠다. https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M이 1부터 8사이이긴 하지만 브루트포스로 돌리면 시간복잡도가 말도 안 되게 높아질 것 같아서 다른 방법으로 풀어야 하는데 문제에 비해 생각보다 풀이법이 떠오르지 않았다. 블로그에서 예전에 풀었던 문제중에 비슷한 걸로 찾아봤더니 DFS를 활용한 백트래킹 문제였다. 내가 가장 못 푸는 문제 유형이니까 이..

리스트를 잘라서 수열이 일치하는지 여부를 확인하는게 주요했던 문제 처음에는 아래 코드 처럼 백트래킹을 사용하지 않고 while문을 통해 나름대로 규칙을 세워서 시도 했었는데 백트래킹을 쓰지 않고는 풀 수 없는 문제인걸 깨닫고 다시 백트래킹 코드로 고쳤다.

무작위 좌표 3개를 어떻게 구성할지 고민하다가 중복순열 prodct 라이브러리를 활용해 풀었다. 조건 중에 꽃이 벽을 넘어서면 안된다고 제시 했기 때문에 좌표를 1~N-1로 제한 했다. for문과 함수호출을 많이 하는 코드라서 시간 초과가 나오지 않을까 걱정했는데 느리긴 하지만 시간내에 통과했다. 21~28줄의 예외처리 코드를 작성하지 않고 제출해 틀렸다가 수정했다. 비용이 모두 0이면 0을 출력해야 하는데 result에 초기 설정된 최댓값이 출력되어 수정했다.

DFS를 활용한 백트래킹으로 문제를 풀었다. 사실 DFS를 안쓰고 백트래킹 하는 법을 잘 모르겠다. 아무튼 코드가 복잡하다 다른 분이 푼 코드에 비해 현저히 길다. 내가 푼 방식으로 봤을 때 키포인트는 1. 33,34줄에서 방문처리와 pop() DFS를 활용한 백트래킹에서 가장 중요한 부분인것 같다. 2. 56줄 부터 나오는 join int형은 길이를 셀 수 없기때문에 str형태로 바꿔서 max_num의 길이를 측정하고, 리스트에 str로 append해서 str(0) 과 join했다. join은 str형태 밖에 쓸 수 없다. 아래는 다른 사람이 푼 코드를 보고 따라한 방식이다. max_num, min_num을 처음부터 str형태로 저장했다. 위 풀이는 아무리봐도 이해가 안된다. 절대 내가 생각해 낼 수 ..

백준 14888번 내 기준 dfs를 활용한 백트래킹 정석 문제 1. modify 리스트에 연산자의 개수를 저장 2. dfs 함수로 깊이 depth, 총 점수 total, 연산자의 개수를 변수로 넘김 3. 깊이가 N이 될 때 마다 total의 최댓값, 최솟값을 저장하고 함수를 빠져나오면 깊이가 N-1인 다른 dfs 함수가 실행되어 또 다시 total의 최대,최소 판별 4. 이렇게 모든 경우의 수를 백트래킹으로 판별가능

원래는 브루트 포스로 하나하나 대입해서 풀었는데 코드도 더럽고 내 취향이 아니라 다르게 풀어봤음 DFS를 이용하여 값을 더해가는 풀이 idx = 1 일 때(즉, 두개의 블럭을 선택했을 때) 새로운 블럭에서 다음 블럭을 탐색하는 것이 아니라 다시 기존블럭에서 탐색하게 만들면 ㅗ,ㅏ,ㅓ,ㅜ 모양을 만들 수 있다. 가지치기 하는 코드 2차원배열에서 최대값을 찾아서 max(map(max, graph)) 선택할 수 있는 남은 블럭의 갯수만큼 (3 - idx) 곱해주고 현재 누적합 total 에 더해서 max_result 와 비교해주는 방식 가지치기 안하니까 시간초과 나옴 ***방문처리 주의하자***