1. 아이디어 ▪ DP 알고리즘 사용 ▪ A(n) = A(n-1) + A(n-2) - 타일 크기가 1일 때: 1가지 - 타일 크기가 2일 때: 2가지 - 타일 크기가 3일 때: 3가지 ▪ 타일 크기에 해당하는 방법의 수 초기 배열 만들기 -> [0,1,2] ▪ 3부터 n까지 for 문 돌면서 이전값과 전전값 더하고 %10007하고 append ▪ 배열의 n번째 값 출력 2. 시간복잡도 ▪ O(N) 3. 변수 ▪ 타일 크기 별 방법의 수 배열: int[] Code import sys input = sys.stdin.readline n = int(input()) dp = [0,1,2] for i in range(3,n+1): dp.append((dp[i-1]+dp[i-2])%10007) print(dp[n]..

1. 아이디어 ▪ 입력받은 동전 내림차순으로 정렬 ▪ for 문 돌면서 - 해당 동전 사용한 개수 더하기 - 나머지 원 갱신 2. 시간복잡도 ▪ O(N) 3.변수 ▪ 동전 리스트: int[] ▪ 사용한 동전의 수: int Code import sys input = sys.stdin.readline N, K = map(int, input().split()) coin_list = [int(input()) for _ in range(N)] cnt = 0 coin_list.reverse() for coin in coin_list: if coin

1. 아이디어 ▪ N개의 정수 정렬 ▪ for문 돌면서 이진탐색 M번 수행 ▪ 이진탐색 - 존재하면 1 출력 - 존재하지 않으면 0 출력 2. 시간복잡도 ▪ N개 입력값 정렬 = O(NlogN) ▪ M개를 N개 중에서 탐색 = O(MlogN) ▪ O(NlogN+MlogN) = O(N+M(logN)) = O(2e5*log2e5) = O(4e6) 3. 변수 ▪ 자연수 배열: int[] ▪ 찾는 수 배열: int[] Code import sys input = sys.stdin.readline N = int(input()) nums = list(map(int,input().split())) M = int(input()) find_nums = list(map(int,input().split())) nums.sor..

1. 아이디어 ▪ 처음 K개의 숫자 합 구하기 ▪ for 문 돌면서 K개 중 가장 첫 번째 값은 빼주고 새로운 값 더해주기 - 더한 값이 기존 max값보다 크면 갱신 2. 시간복잡도 ▪ O(N) 3. 변수 ▪ 배열을 저장할 map: int[] ▪ K개 합: int ▪ 최대값: int Code import sys input = sys.stdin.readline N,K = map(int,input().split()) map = list(map(int,input().split())) v_sum = sum([map[i] for i in range(K)]) max_sum = v_sum for i in range(K,N): v_sum -= map[i-K] v_sum += map[i] if v_sum > max_su..

1. 아이디어 ▪ while문으로 구현하고 특정 조건에 도달하면 break - 현재 칸이 0인 경우 청소(map 2로 바꾸기)하고 청소한 칸 개수 +1 ▪ for문으로 주변 4칸 살펴보기 - 주변칸이 0인 칸이 있으면 좌표 이동하고 방향 바꾸고 break ▪ 4칸 모두 살펴봤는데 없으면 - 현재 방향 기준 뒤로 후진 - 만약 벽이거나 map 범위 밖으로 벗어나면 break - 아니면 현재 좌표 이동 2.시간복잡도 ▪ O(NM) = 50*50 3. 변수 ▪ map: int[][] ▪ 현재좌표,방향: int ▪ 청소한 방의 개수: int 4. 오답노트 ▪ 북과 남의 좌표가 잘못됬음 ->북:(-1,0),남:(1,0) ▪ 청소 안한 방을 찾으면 break 해야됨 ▪ map 범위 밖으로 벗어나면 break Cod..

1. 아이디어 ▪ 선택한 숫자의 개수가 M이 되면 멈추고 출력 ▪ 백트래킹으로 for문 돌리면서 방문하지 않은 숫자 선택 - 방문여부 True로 갱신 - 선택한 숫자 리스트에 추가 - num+1 하고 재귀호출 - 방문여부 False로 갱신 - 선택한 숫자 리스트에 뺴기 2. 시간복잡도 ▪ log(N!) 3.변수 ▪ 방문여부: bool[] ▪ 선택한 숫자: int[] Code import sys input = sys.stdin.readline N, M = map(int, input().split()) chk = [False] * (N+1) rs = [] def back(num): if num == M: print(' '.join(map(str, rs))) return for i in range(1,N+1)..

1. 아이디어 ▪ 2중 for문 돌면서 1이고 방문하지 않았으면 dfs - 집의 수 변수 0으로 초기화 - 방문여부 갱신 - 단지수 += 1 - 집의 수 결과 리스트에 append ▪ dfs - 재귀함수로 구현 - 처음 호출 부분에 집의 수 += 1 - 이때 호출받은 집의 수는 global로 구현 - 입력받은 좌표의 상하좌우 재귀호출 - 이때 상하좌우 자표가 지도의 크기를 넘지 않는 지 확인 - 1이고 방문하지 않았으면 - 방문여부 갱신 - dfs 함수로 재귀호출 2. 시간복잡도 ▪ O(V+E) = O(V+4V) = O(5V) = 5*25*25 3. 변수 ▪ map: int[][] ▪ 방문여부: int[][] ▪ 단지수: int ▪ 집의 수 결과 리스트: int[] 4. 오답노트 ▪ dfs 함수 재귀호출..

1. 아이디어 ▪ 2중 for문 돌면서(for문은 y부터 돌고 x돌기) 1이고 방문하지 않았으면 bfs - 그림의 개수 +1 - 가장 큰 그림의 넓이 갱신 - 방문여부 체크 ▪ bfs - 기본 넓이는 1로 시작 - queue로 구현 - 상하좌우가 1이고 방문하지 않았으면 - queue에 추가하고 넓이 +1 - 방문 여부 표시 - queue에 값이 더이상 없을떄 까지 수행 2. 시간복잡도 ▪ O(V+E) = O(V+4V) = O(5V) = 5*500*500 3. 변수 ▪ map: int[][] ▪ 방문여부: bool[][] ▪ 그림의 개수, 가장 큰 그림의 넓이: int 4. 오답노트 ▪ bfs에서 입력받은 좌표의 상하좌우가 map size를 넘는지 확인 Code from collections import..