목록Algorithm (111)
S E P H ' S
코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr 풀이 1. 제한사항에서 n은 20이하의 자연수라고 되어있다. 시간 복잡도가 n! 인 permutations를 사용하면 제한시간 초과로 풀지 못하는 테스트 케이스가 발생한다. 2. 수학적 응용과 문제의 규칙을 이용해서 풀어야함. 3. 문제에서 처럼 k를 5라고 했을때, k 이전에 있는 배열의 개수는 4. 이 중에 1로 시작하는 경우 2개, 2로 시작하는 경우 2개이다. 즉, n = 3일때, 하나를 골랐을 때 나머지를 고를 수 있는 경우의 수와 같다...
코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만 programmers.co.kr 풀이 1. n이 s보다 크면 집합을 만들 수 없으므로 [-1] 리턴 2. s를 n으로 나눈 몫을 n개 만큼 answer에 append 3. s를 n으로 나눈 나머지를 1씩 뒷쪽부터 더해준다. def sol(n, s): answer = [] if n > s: return[-1] v = s // n for i in range(n): answer.append(v) idx = len(answer) - 1 for i in range(s % n):..
코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대 programmers.co.kr 풀이 1. 세 개의 기둥을 각각 From, To, Sub로 생각. 2. 원반 하나를 옮기는 것을 반복. => 재귀 3. F : 1 / T : 3 / S : 2 4. 옮겨야 하는 가장 맨 위의 원반 1->2, 2->3 def solution(n): def hanoi(n, F, T, S): if n == 1: answer.append([F, T]) return hanoi(n - 1, F, S, T) answer.append([F, T]) ha..
코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr def dfs(queen, row, n): cnt = 0 if n == row: return 1 for col in range(n): queen[row] = col for r in range(row): if queen[r] == queen[row]: break if abs(queen[r] - queen[row]) == row - r: break else: cnt += dfs(queen, row+1, n) return cnt def solution(..