Why not?

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 조합 문제를 dp로 풀어보았다. 규칙을 찾기 어려워서 일단 계산한 결과를 적어보았다. 행은 n을, 열은 k를 의미할 때 5C2(nCk)를 구하자고 해보자. 0 1 2 3 0 1 0 0 0 1 1 1 0 0 2 1 2 1 0 3 1 3 3 1 4 1 4 6 4 5 1 5 10 10 k가 n보다 큰 경우는 0을 넣어 계산에 영향을 미치도록 하지 않았다. 5C2의 값은 10이다. 그런데 위의 4C1 + 4C2의 값과 동일하다. 이는 우연이 아니다. 4C1은 3C0 + 3C..

https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 이 문제는 투 포인터를 쓰면 쉽게 풀 수 있다. 하지만, 나는 투 포인터를 써도 시간초과가 났는데... 그 이유는... # 두 수의 합 import sys input = sys.stdin.readline N = int(input()) A = list(map(int, input().split())) A.sort() X = int(input())..

https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 오큰수 문제와 비슷하다. 그런데... "시간초과" 이게 날 괴롭혔다. 애초에 문제를 잘못읽은 부분이 있었다. 빈도만 따지면 되는데 수까지 커야 한다고 생각한 것이다. 따라서 조건을 아래와 같이 두 개로 선정하였다. A[i] =F[stack[-1]-1] 그리고 리스트의 count 연산은 시간을 많이 소모한다. 따라서... 아래처럼 count를 쓰기 보다는 for 반복문으로 직접 세는게 더 낫다. 그리고 생각해보..

https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 문제를 처음 보고 든 생각은 문자열 A를 덱으로 만들어서 완전 탐색으로 앞에서도 넣어보고 뒤에서도 넣어보며 최솟값을 찾으려고 했다. 하지만 구현하면서 이거보다 더 좋은 방법이 있을 것 같다는 생각이 들어서 힌트를 살짝 보았다. # 문자열 import sys input = sys.stdin.readline A, B = input().split() answer ..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 1년만에 풀어보는 TSP 문제였다... 풀어본 문제임에도 오랜만에 푸니까 가물가물했다.. ㅜ 처음 작성했던 코드는 두 가지 오류가 존재했다. # 외판원 순회 2 import sys input = sys.stdin.readline N = int(input()) w = [] visited = [False for _ in range(N)] answer = 1..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net # 차이를 최대로 import sys input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) l = [] answer = -1e9 def solve(cnt): global answer if cnt == N: total = 0 for i in range(cnt-1): total += abs(l[i]-l[i+1]) answe..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 트리의 노드별로 부모를 입력받고, 지워야 할 노드의 번호를 입력받는다. 그런 다음 트리를 만들어주는데 이때 지워야 할 노드를 부모에 추가하는 과정은 생략한다. 왜냐하면 어차피 지워야 할 노드이기 때문이다. 덱을 생성하고 그 덱의 자식 노드가 있으면 while 반복문을 통해 자식 노드를 덱에 추가하며 제거해준다. 왜냐하면 트리에서 한 노드를 제거하면 그 노드의 자식노드도 제거되기 때문이다. 해..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net solve 함수는 재귀 함수이다. 원반이 하나라면 그냥 옮기면 끝이기 때문에 종료조건으로 설정한다. from_pos, to_pos, aux_pos 각각을 시작점, 도착점, 보조점이라고 생각한다. 즉, solve(N, 1, 3, 2) 는 N개의 원판을 1번 기둥을 시작으로 3번 기둥으로 옮기되 2번 기둥을 보조기둥으로 사용한다는 뜻이다. 하노이의 탑 문제에서 가장 중요한 것은 가장 큰 ..