backtracking5 [Baekjoon] 1759.암호 만들기 # Problem 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다. 새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수.. 2021. 4. 29. [Baekjoon] 1987. 알파벳 # Problem 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 입력 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주.. 2021. 4. 29. [Baekjoon] 9663. N-Queen # Problem N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 퀸은 대각선, 좌우상하 이동가능 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. # Solution 1 def check(x): # 상하좌우, 대각선 확인 for i in range(x): if row[x]==row[i]: return False if abs(row[x]-row[i])==x-i: return False return True def dfs(x): global result if x==n: result+=1 else: f.. 2021. 4. 29. [코딩 + 알고리즘 완주반] 24일차. 백트래킹 # 백트래킹 - 제약조건만족 문제에서 해를 찾기 위한 전략 - 해를 찾기 위해 조건을 점진적으로 체크하다가 해당 후보군이 제약조건을 만족할 수 없다고 판단하는 즉시 backtrack( 다시 이 후보군을 체크하지 않음) 하고 다른 후보군으로 넘어가 최적의 해를 찾는 방법 - 모든 경우의 수를 상태공간트리 (State Space Tree) 를 통해 표현 - 각 후보군을 DFS 방식으로 확인 - Promising : 해당 루트가 조건에 맞는지 검사하는 기법 - Pruning (가지치기) : 조건에 맞지 않으면포기하고 다른 루트로 바로 돌아서서 탐색의 시간을 절약하는 기법 # N-Queen 문제 N*N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제 퀸 : 수직, 수평, 대각선 이동 가능 Pr.. 2021. 4. 14. [LEET CODE] 39. Combination Sum # Problem Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.. 2021. 4. 9. 이전 1 다음 반응형
