note

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 무작정 그려놓고 규칙을 찾았다 처음엔 삼각형이 생기는 순서대로 규칙을 계산했다가 [인덱스-2] + [인덱스-3] 으로도 계산이 된다는 걸 찾음 d = [0] * 101 d[1], d[2], d[3] = 1, 1, 1 for i in range(4, 101): d[i] = d[i-2] + d[i-3] t = int(input()) for i in range(t): n = int(input()) print..

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 피보나치 수열이랑 똑같은 간단한 문제였다 그러나... 첫 번째 코드 - 메모리 초과 n = int(input()) d = [0] * (n + 1) d[1] = 1 d[2] = 2 for i in range(3, n+1): d[i] = d[i-1] + d[i-2] print(d[n] % 15746) 두 번째 코드 - 나머지 계산을 반복문 안에 넣어줌. 런타임 에러 n이 1일 때 d[2] = 2에서 인덱스..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 처음 코드 - 걍 냅다 계산.. 당연히 시간 초과 날 줄 알았음 def fib(n): d = [0] * (n + 1) if n == 0: count[0] += 1 return 1 if n == 1: count[1] += 1 return 1 d[n] = fib(n - 1) + fib(n - 2) return d[n] t = int(input()) for i in range(t): n = int(input()) count = [0, 0] fib(n) print(count[0], count[1]) ..

중복되는 연산을 줄이자 - 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. - 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다. - 수학적 점화식을 프로그래밍으로 표현하려면 재귀 함수를 사용하면 간단하다. # 피보나치 함수를 재귀 함수로 구현 def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(x-2) print(fibo(4)) - 그런데 피보나치 수열의 소스코드를 이렇게 작성하면 심각한 문제가 생길 수 있다. - f(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문! -> O(2^N) - 피보나치 수열의 호출 과정을 그림을 그려..

https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 알고리즘 자체는 쉬우나 문제 풀이를 이해하는 과정이 너무 어려웠다 그래서 일주일 전 쯤에 풀다가 그 상태로 방치하고 오늘 다시 함..ㅋㅋㅋ 2차원 배열 -> 1차원 배열로 바꾸는 비효율적인 방법밖에 생각이 나질 않아서 다른 사람들 풀이 참고해서 풀었는데 그마저도 이해가 안 가서 오랫동안 끙끙 앓았다ㅠ n = int(input()) k = int(input()) sta..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 첫 제출은 시간 초과가 떴다.. 입력받는 부분만 sys.stdin.readline()으로 바꿔주니까 통과함 import sys n, c = map(int, sys.stdin.readline().split()) house = [int(sys.stdin.readline()) for _ in range(n)] house.sort() start = 1 ..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이진탐색 알고리즘 공부하면서 풀었던 문제랑 똑같네! 하고 후다닥 풀었지만 50%에서 시간 초과.. 시간을 줄이고자 이리저리 고쳐봤지만 더이상 고칠게 없는 거 같은데도 시간 초과.. 결국 구글링.. 이진 탐색으로 풀면 pypy3로 제출해야 시간초과가 뜨지 않는다고 한다ㅠ Counter 라이브러리 쓰면 python3도 통과된다고 하긴 함.. import sys ..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 처음엔 제일 작은 수부터 시작해서 점점 길이를 줄이면서 잘라내고 자른 개수 >= N 이면 멈추는 방식으로 코드를 짰는데 틀렸다. # 틀림 import sys k, n = map(int, sys.stdin.readline().split()) cable = [] for i in range(k): cable.append(int(sys.stdin.readline())) len..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 채점하는데만 1분 30초는 걸려서 나 처음에 시간 초과 뜨는 줄^^,, import sys n = int(input()) card = sorted(map(int, sys.stdin.readline().split())) m = int(input()) find = list(map(int, sys.stdin.readline().split())) dict_card = d..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 반복문으로 이진탐색을 풀어주었다 import sys n = int(sys.stdin.readline().rstrip()) a = list(map(int, sys.stdin.readline().split())) m = int(sys.stdin.readline().rstrip()) b = list(map(int, sys.stdin.readline().s..