본문 바로가기

Algorithm85

섹션 6. 수열 추측하기 순열라이브러리와 DP를 통해 이항계수를 구한 풀이법 from itertools import permutations n, f = map(int, input().split()) tri = [[1] * 11 for _ in range(11)] tri[2][1] = 2 cnt = 0 for i in range(3, 11): for j in range(1, i): cnt += 1 tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j] b = tri[n - 1] b = b[:n] seq = list(range(1, n + 1)) for v in permutations(seq): seq = list(v) res = 0 for i in range(n): res += seq[i] * b[i] .. 2022. 10. 17.
섹션 6. 순열 구하기 DFS를 이용한 풀이 def dfs(l): global cnt if l == m: print(*res) cnt += 1 return for i in range(1, n + 1): #내 처음 코드. in연산자를 쓰기 때문에 체크리스트를 쓰는 게 더 효율적임. # if i in res: # continue # res[l] = i # dfs(l + 1) # res[l] = 0 #중복순열이 아니기에 res에 중복된 요소가 들어가는 걸 방지하기 위해 체크리스트 사용 #다음 레벨에서 고를 수 있는 수는 부모레벨에서 선택한 값 제외 모두 가능 if ch[i] == 0: ch[i] = 1 res[l] = i dfs(l + 1) ch[i] = 0 n, m = map(int, input().split()) res = [0.. 2022. 10. 17.
이진트리 순회(DFS) 전위순회, 후위순회, 중위순회를 구현한 코드이다. 이진트리를 순회할 때는 재귀함수를 두번 호출하게 되는데 이 때 실행문을 어느 위치에 작성하는지에 따라 위 세가지 방법으로 출력할 수 있다. # 전위순회 출력 def dfs(v): if v > 7: return #함수 호출 전 현재 노드 출력 -> 탐색 순서대로 찍힌다. print(v) dfs(v * 2) dfs(v * 2 + 1) # 후위순회 출력 def dfs(v): if v > 7: return dfs(v * 2) dfs(v * 2 + 1) #모든 재귀호출이 끝나야 루트노드가 출력됨 -> 먼저 리턴된 재귀함수 순으로 출력된다. print(v) # 중위순회 출력 def dfs(v): if v > 7: return #첫번째로 호출한 함수가 리턴되면 현재 .. 2022. 10. 8.
백준 10799-쇠막대기 (파이썬) https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다. 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 각 쇠막대기를 자르는 레이저는 적어.. 2022. 10. 6.
백준 1931-회의실 배정 (파이썬) https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 10.. 2022. 10. 4.
백준 9465-스티커 (파이썬) https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 .. 2022. 10. 1.
백준 1074-Z (파이썬) https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제 한수는 크기가 \(2^N*2^N\) 인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 \(2^{N-1}*2^{N-1}\)로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 \(2^2*2^2\) 크기의 배열을 방문한 순서이다. N이 주어.. 2022. 9. 30.
백준 2630-색종이 만들기 문제 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의.. 2022. 9. 28.
분할정복(Divide and Conquer) 알고리즘 분할 정복이란? 분할 정복으로 통칭하는 이 패러다임은 한 문제를 유형이 비슷한 여러 개의 하위 문제로 나누어 재귀적으로 해결하고 이를 합쳐 원래 문제를 해결한다. 분할 정복 방식이 하위 문제를 재귀적으로 해결하기 때문에 하위 문제 각각은 원래 문제보다 범위가 작아야 하며 하위 문제는 각 문제마다 탈출 조건이 존재해야 한다. 분할 정복 알고리즘을 이해하기 위해 다음과 같이 세 부분으로 나눠서 생각해보자. 분할(divide): 문제가 분할이 가능한 경우 2개 이상의 하위 문제로 나눈다. 정복(conquer): 하위 문제가 여전히 분할 가능하면, 또 다시 분할을 수행한다. 그렇지 않으면 문제를 푼다. 합치기(combine): 정복한 하위 문제들의 답을 합쳐서 원래 문제를 해결하자. 문제를 제대로 나누면 con.. 2022. 9. 28.

티스토리툴바