아이테킨의 끄적끄적

이 문제도 점화식을 구하면 쉽게 풀 수 있는 문제다 그림을 유심히 살펴보거나 혹은 결과들을 유심히 살펴보면 숫자들간에 규칙이 있는것을 발견할 수 있다. (사실 다른 더 논리적이고 멋있는 해설이 있기야 하겠지만 나는 이렇게 풀었다...;;) 점화식 $$ a_n = a_{n-5} + a_{n-1} $$ 코드 # 9461번 - 파도반 수열 import sys input = sys.stdin.readline t = int(input()) for _ in range(t): dp = [0] * 101 dp[1] = 1 dp[2] = 1 dp[3] = 1 dp[4] = 2 dp[5] = 2 n = int(input()) for i in range(6,n+1): dp[i] = dp[i-5] + dp[i-1] print..

일단 이 문제는 점화식으로 표현할 수 있다면 쉽게 풀 수 있는 문제다. $$A_n = A_{n-1} + A_{n-2}$$ 처음 1,2 까지의 값만 다른 피보나치 수열이다. 점화식을 알았으니 반복문 또는 재귀함수를 이용해서 풇어주면 된다. 반복문을 이용해서 풀어보았다. # 1904번 - 01타일 # 반복문을 이용해서 - 바텀업 import sys input = sys.stdin.readline n = int(input()) tile_list = [0]*(n+1) tile_list[1] = 1 tile_list[2] = 2 for i in range(3,n+1): tile_list[i] = (tile_list[i-1] + tile_list[i-2])%15746 print(tile_list[n]) 이때 주의해..

메모이제이션을 이용해서 풀어야 하는 DP 문제다. 3차원 리스트를 이용하면 쉽게 풀 수 있다. # 9184 - 신나는 함수 실행 dp = [[[0]*21 for _ in range(21)] for __ in range(21)] def w(a, b, c) : print(dp) if a20 : return w(20, 20, 20) if dp[a][b][c]: return dp[a][b][c] if a

피보나치 함수를 구하는 문제이다 보통 피보나치 수열은 재귀함수를 이용해서 구할 수 있다. def fibo(x): if x == 1 or x == 2: return 1 else: return fibo(x-1) + fibo(x-2) 이런 식으로 구할 수 있는데 문제는 숫자가 조금만 커지게되면 연산횟수가 급격하게 증가하고 그에 따라서 속도도 엄청 느려지게 된다. 이런 문제를 메모이제이션(재귀함수이용) 또는 반복문을 이용해서 해결할 수 있다. 메모이제이션은 이미 한번 연산을 했던 값은 따로 저장해뒀다가 필요할때마다 찾아서 쓴다는 아이디어다. 말 그대로 따로 메모해둔다고 생각하면 된다. 반복문을 이용하는 방법은 작은 문제부터 하나하나씩 풀어나가는 방법이다. 결론적으로는 선형시간의 시간복잡도를 갖는다. 코드로 살펴..

통계학에서 주로 사용되는 개념들을 직접 구현해보라고 만든 문제인 것 같다. 산술평균이나, 중앙값, 범위 구하는 문제는 max,min,sum,등등 파이썬 내장함수를 이용하면 어렵지 않게 구할 수 있는 문제다. 특별히 최빈값을 구할때 collections 모듈에서 Counter클래스 썻다. 코딩테스트에서는 다른 라이브러리를 불러오지 못하게 하는 경우도 있다고 들어서 이런 모듈을 불러와서 문제를 풀어도 될지에 대해서 불안하지만 Counter함수에 대해서 공부도 할겸 구글링하면서 풀어보았다. 여기에 counter에 대한 documentation이 있다. https://docs.python.org/ko/3/library/collections.html#collections.Counter collections — 컨..

계수정렬(counting sort)을 사용해서 풀어야하는 문제다. 계수정렬의 가장 큰 특징은 비교정렬이 아니다 라는 점이다. 비교정렬은 두수의 대소관계를 반복적으로 계산하면서 푸는 정렬방법인데 계수정렬은 이런 방법을 사용하는게 아니라 말 그대로 숫자들의 개수를 세면서 정렬한다. 그리고 계수정렬의 시간복잡도는 선형시간이다 O(n) 성능이 좋다는 다른 정렬방법(퀵정렬 - O(n^2), 병합정렬 - O(nlogn), 힙정렬 - O(nlogn))들 보다도 훨씬 빠르다. 그러나 단점은 제한이 많다는 것이다. 값들간의 차이 크기가 별로 없거나 값들이 정수로만 이루어져있을때 사용이 가능하다. 역시나 모든 문제에서 좋은 알고리즘은 없고 그때그때마다 상황에 맞는 알고리즘을 찾아서 사용해야 한다. 계수정렬의 스탭별 자세한..

먼저 이 글은 나동빈님의 '이것이 취업을 위한 코딩테스트이다' 이진탐색 파트를공부하고 정리한 것임을 밝힙니다. 순차탐색(Sequential Search) 리스트 안에서 특정 원하는 데이터를 찾으려고 할때 가장 먼저 떠올릴 수 있는 아이디어는 처음부터 하나하나 확인하면서 일치하는 데이터의 인덱스를 뽑아내는 것이다. 이를 순차탐색(Sequential Search) 이라고 한다. 반복문과 조건문을 적절히 이용하면 큰 어려움 없이 만들어볼 수 있다. 이때의 시간복잡도는 당연히 O(N)이다 이제 더 빨리 찾아낼 수 있는 이진탐색에 대해서 알아보자. 이진 탐색(Binary Search) 먼저 이진탐색은 데이터가 정렬이 되어있는 상태에서 사용할 수 있는 알고리즘이다. 이진탐색의 아이디어는 위치를 나타내는 변수 3개를..

시간복잡도 O(nlogn)을 가지는정렬을 사용해야 통과가 가능한 문제이다 1. 파이썬 내장함수 사용(sorted) 2. 퀵정렬 3. 퀵정렬(cache사용없이) 4. 병합정렬 5. 힙정렬 이 다섯가지 정렬방법으로 풀어보았다. (그리고 시간이 중요한만큼 sys.stdin.readlind으로 입력값을 받았다.) 1. 파이썬 기본 내장함수 sorted() import sys n = int(input()) li = [] for _ in range(n): li.append(int(sys.stdin.readline())) for i in sorted(li): print(i) 병합정렬을 기반으로 만들어진 함수이며 O(nlogn)의 시간복잡도를 가지는 알고리즘이라고 한다. 일반적으로 직접 함수를 만들어서 사용하는 것보다..

최단거리를 찾는 문제이므로 bfs탐색 알고리즘을 사용하면 쉽게 풀수 있다. 또 시간초과가 떳다. 이게 시간초과가 뜬 내가 만든 코드이고 from collections import deque import sys input = sys.stdin.readline def bfs(): while queue: x,y = queue.popleft() for step in range(8): nx,ny = x + dx[step], y+dy[step] if 0

이 코드로 했더니 테스트케이스의 답들은 잘 나오는데 시간초과가 떠버렸다. 3차원 배열을 사용해야 하는 문제라서 반복문 3개를 썻다고 시간초과가 나오는 건 아닐거라고 생각한다. 확실한 이유는 아닐 수도 있지만 내 생각에 중간에 zip내장함수를 이용해서 좌표를 만들어낼때 내부적으로 연산이 더 되는게 아닌가 싶다. 사실 잘 모르겠다. 어떤 부분에서 시간 초과가 나는지...ㅠㅠ # 7569 토마토 3차원 문제 import sys input = sys.stdin.readline m,n,h = map(int,input().split()) graph = [[] for _ in range(h)] for i in range(h): for _ in range(n): graph[i].append(list(map(int,in..