NAN-NOO

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 순열 구하는 문제 # 1

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 유명한 백트래킹 완전 탐색 문제라고 해서 풀어봤다. Python3로 풀면 시간 초과가 나서 PyPy3로 제출했다. # 1

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 2023.04.11 - [코딩 테스트/개념] - Dijkstra algorithm # 1

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 2023.04.11 - [코딩 테스트/개념] - Topological sort # 1

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 2023.04.11 - [코딩 테스트/개념] - Union-Find # 1

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 2023.04.11 - [코딩 테스트/개념] - Union-Find # 1 ≤ N ≤ 90 import sys readline = sys.stdin.readline n, m = map(int, readline().split()) union_find = [i for i in range(n + 1)] def find(v): if union_find[v] == v:..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 2023.04.14 - [코딩 테스트/개념] - dynamic programming # 1 ≤ N ≤ 90 import sys readline = sys.stdin.readline N = int(readline()) # d[n] = n자리 이친수 개수 # d[i] = d[i - 1] + d[i - 2] # init: d[1] = 1, d[2] = 1 d = [0 for _ in rang..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 2023.04.14 - [코딩 테스트/개념] - dynamic programming # 1 ≤ N ≤ 10^6 import sys readline = sys.stdin.readline N = int(readline()) # d[n] = 숫자 n이 1이 될 때까지 필요한 연산 횟수의 최솟값 # d[i] = min(d[i // 3] + 1, d[i // 2] + 1, d[i - 1] + 1) # 초기화: d[1] = 0 d = [0 for _ in range(N + 1)] # bottom-up for i in ra..

동적 계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제를 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 말한다. 🔰특징 큰 문제를 작은 문제로 나눌 수 있어야 한다. 작은 문제들이 반복적으로 나타나고 사용되며, 작은 문제의 결과값은 변하지 않아야 한다. 모든 작은 문제를 한 번만 계산해 dp 테이블에 저장하여 재사용한다. 이를 memoization이라 한다. 탑-다운 방식과 바텀-업 방식으로 구현할 수 있다. 🔰접근 방법 피보나치 수열에서 6번째 수를 구하는 문제가 있다고 가정하자. 동적 계획법으로 풀 수 있는지 확인한다. 6번째 수는 5번째 피보나치 수와 4번째 피보나치 수의 합이다. 따라서 5번째 수를 구하는 문제와, 4번째 수를 구하는 작은 문제로 나눌 수 있고, 그 ..

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 2023.04.14 - [코딩 테스트/개념] - combination # 1 ≤ N ≤ 1,000 # 0 = 1 # 초기화: d[i][i] = 1, d[i][0] = 1, d[i][1] = i d = [[0] * (N + 1) for _ in range(N + 1)] for i in range(1, N + 1): d[i][i] = d[i][0] = 1 d[i][1] = i for i in range(2, N + 1): for j in range(1, i): d[i][..