Why not?

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번 기둥을 보조기둥으로 사용한다는 뜻이다. 하노이의 탑 문제에서 가장 중요한 것은 가장 큰 ..

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 문제를 처음 봤을 때는 막연하게 2차원 배열을 만들어야 하나? 생각했다. 하지만 조금만 더 생각을 해보면 1차원 배열로도 충분히 풀 수 있다는 것을 알 수 있다. 문제를 접근한 방식은 아래와 같다. 1. 0번째 인덱스의 값을 max_height라는 리스트에 인덱스와 함께 저장한다. (ex. max_height = [0, 3]) 2. for 반복문으로 1번째 인덱스부터 접근한다. ..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 이 문제를 풀 때 가장 중요한 점은 '우선순위 큐'를 사용한다는 것이다. 그리고 파이썬에는 heapq 모듈에 구현되어 있다. 우선 카드의 수를 입력받은 리스트 A를 힙으로 바꾼다. 그리고 우선순위 큐는 우선순위가 낮은 값부터 pop하기 때문에 최솟값을 쉽게 구할 수 있다. 따라서 두 번의 pop을 통해 최솟값을 꺼내고 그 둘을 더한 뒤 다시 우선순위 큐에 넣는다. 이 과정을 진행하면..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 이 문제를 보고 처음 생각이 난 풀이 방법은 '각 원소에 대해 오른쪽에 있는 원소를 하나씩 살펴보며 더 큰지 검사하는 방법'이었다. 하지만 이는 최악의 경우인 '9 8 7 6 5 4 3 2 1'의 경우 모두 -1이 출력되는데, 각각의 원소에 대해 더 큰 값이 있는지 살펴보기 위해 리스트 전체를 뒤지는 상황이 생긴다. 이러한 접근 방식은 무조건 시간 초과가 발생하기 때문에 올바른 방법이 아니다. 그렇게 생각한..

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 문제를 보고 처음에 든 생각은 누적합을 이용해서 합 배열을 구한 후, 그 합 배열을 for 반복문으로 돌며 나머지 연산을 진행하여 나누어 떨어지는지 검사하는 것이다. # 나머지 합 import sys input = sys.stdin.readline N, M = map(int, input().split()) A = list(map(int, input(..

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 정말.. 많은 시간초과가 났다... 틀린 이유에는 두 가지가 있었는데 1) check, toggle 에서 copy를 통해 새로운 집합을 생성한 후 비교 정말 비효율적인 코드라고 생각한다. 만약 길이로 비교를 하고 싶었다면, 기존 집합 S에 더해보고 길이가 같으면 1을 출력하고 다르다면 0을 출력한 뒤 다시 remove 하면 되는데 생각이 짧았던 것 같다. 2) 아래의 데이터셋에 잘못된 결과를 냄 2 all check 20 이거는 h..

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 이 문제를 풀기 위해 처음 떠올린 알고리즘은 쉬웠다. 파이썬의 리스트 index 함수를 사용하여 일치하는 값이 있으면 해당 인덱스부터 폭발 문자열의 길이만큼 요소를 삭제한 후에 새로운 string을 복사하여 폭발열과 일치하는 문자열이 없을 때까지 반복했다. # 문자열 폭발 import sys input = sys.stdin.readline string = input().rstrip(..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 위에서 아래로 내려간다고 생각하니까 배열을 더하는 공식을 짜기가 어려웠다. 하지만 밑에서 아래로 올라간다고 생각하고 위의 두 값 중에 더 큰 값을 더한다고 생각하니 쉽게 구현할 수 있었다. # 정수 삼각형 import sys input = sys.stdin.readline N = int(input()) triangle = [] for _ in range(N): triangle.append(list(map(int, input().split()))) for i in ran..