본문 바로가기

Python144

[Python] 백준 10844 쉬운 계단 수 🧑‍💻 [Python] 백준 10844 쉬운 계단 수 Silver 1 - DP 코드 N = int(input()) stairs = [[0] * 10 for _ in range(N)] for i in range(1, 10): stairs[0][i] = 1 for i in range(1, N): for j in range(10): if j == 0: stairs[i][j] = stairs[i-1][j + 1] elif 0 < j < 9: stairs[i][j] = stairs[i-1][j+1] + stairs[i-1][j-1] elif j == 9: stairs[i][j] = stairs[i-1][j-1] print(sum(stairs[N-1]) % 1000000000) 2023. 3. 24.
Udemy : 동적 계획법 (DP) Udemy : 동적 계획법 (DP) udemy 알고리즘 코딩 테스트 Dynamic Programming 문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는 것을 반복 분할정복과 비슷한 느낌 배열 또는 딕셔너리를 만들어서, 작은 문제의 답을 넣는다 메모이제이션 (Memoization) 구현 : 재귀 | 저장방식 : 메모이제이션 (Top-down) cache 방식이라고 할 수 있고, 중복연산을 방지한다 직관적이라 코드 가독성이 좋다 재귀함수 호출이 많이 해서 느릴 수 있다 타뷸레이션 (Tabulation) 구현 : 반복 | 저장방식 : 타뷸레이션 (Bottom-up) 테이블을 채워나가는 것 필요 없는 부분 문제까지 전부 구하는 것 시간과 메모리를 좀 더 아낄 수 있다 DP 테이블 채워.. 2023. 3. 23.
[Python] 백준 11726 2 x n 타일 🧑‍💻 [Python] 백준 11726 2 x n 타일 Silver 3 - DP n을 1부터 5까지 타일을 임의로 채워주다보면, 피보나치 수열이란 것을 알 수 있다 cache 리스트에 0을 1001개를 넣는다 먼저 cache[1]과 cache[2]에 1과 2를 넣어 피보나치 수열을 시작한다 for문에 피보나치 수열을 계산하는 식을 넣는다 코드 Num = int(input()) cache = [0] * 1001 cache[1], cache[2] = 1, 2 for i in range(3, 1001): cache[i] = cache[i - 1] + cache[i - 2] print(cache[Num] % 10007) 2023. 3. 22.
[Python] 백준 15683 감시 🧑‍💻 [Python] 백준 15683 감시 Gold 4 - 구현 DFS를 하는 것인데, CCTV를 DFS 하는 것이다 CCTV 가 3개가 있으면 3개의 감시하는 방향을 DFS로 탐색을 한다 탐색한 방향에다가 '#'을 넣는다 0의 개수를 센다음, 제일 작은 수를 찾는 것 지도가 주어진다고, DFS를 지도에 할 생각부터 하지 말자 ㅜ.ㅜ 코드 from copy import deepcopy N, M = map(int, input().split()) dr,dc = [-1, 0, 1, 0], [0, 1, 0, -1] direction = [[], [[0], [1], [2], [3]], [(0, 2), (1, 3)], [(0, 1), (1, 2), (2, 3), (3, 0)], [(0, 1, 2), (1, 2, .. 2023. 3. 20.
[Python] 백준 14719 빗물 🧑‍💻 [Python] 백준 14719 빗물 Gold 4 - 구현 입력 값 M, N = 4, 8 3 1 2 3 4 1 1 2 i left right min(max(left), max(right)) block[i] water 1 3 2, 3, 4, 1, 1, 2 3 1 2 2 3, 1 3, 4, 1, 1, 2 3 2 3 3 3, 1, 2 4, 1, 1, 2 3 3 3 4 3, 1, 2, 3 1, 1, 2 3 4 3 5 3, 1, 2, 3, 4 1, 2 2 1 4 6 3, 1, 2, 3, 4, 1 2 2 1 5 left, right 는 현재의 인덱스 기준으로 왼쪽과 오른쪽에, 더 큰 지역이 있는지 보는 것이다 이것을 통해서 물이 고이는지 안 고이는지 알 수 있다 min(max(left), max(right).. 2023. 3. 15.
[Python] 백준 15686 치킨 배 🧑‍💻 [Python] 백준 15686 치킨 배 Gold 5 - 구현 치킨과 집의 좌표들을 각 chicken과 home 리스트에 넣었다 일단 최대 치킨의 수를 입력 받으니깐, 치킨의 좌표를 combinations를 통해 순열을 찾는다 그리고 집의 기준으로 치킨 좌표들과 비교해서, 제일 가까운 거리를 찾으면 된다 코드 from itertools import combinations N, M = map(int, input().split()) city = [list(map(int, input().split())) for _ in range(N)] chicken, home = [], [] result = N ** N for i in range(N): for j in range(N): if city[i][j] ==.. 2023. 3. 14.
[Python] 백준 14502 연구소 🧑‍💻 [Python] 백준 14502 연구소 Gold 4 - 구현 from copy import deepcopy 깊은 복사를 하는 것이다 깊은 복사를 하면, 완전 다른 인스턴스가 만들어진다 (남남이 되는 것) combinations 을 사용해서 배치할 벽들의 좌표를 구했다 empty_space 리스트에 비어 있는 공간들의 좌표들을 넣었다 비어있는 공간들의 좌표의 순열을 통해 벽들을 배치하고, 바이러스가 얼마나 퍼지는지 구하는 것 for empty in combinations(empty_space, 3): 비어있는 공간들의 좌표 3개를 통해 벽들을 배치해준다 BFS를 하는데, BFS는 마지막에 퍼진 바이러스의 개수를 반환해준다 퍼진 바이러스의 개수의 최소값을 구하면 된다 코드 디테일 queue = deq.. 2023. 3. 14.
Udemy : 알고리즘 이분 탐색 Udemy : 알고리즘 이분 탐색 udemy 알고리즘 코딩 테스트 이분 탐색 하나 하나 다 찾는 것이 아닌다 (완전 탐색으로 매우 오래 걸린다) Up & Down 게임이라고 생각하면 된다 정답을 기준으로, 무작위로 고른 숫자가 정답 숫자가 무작위로 고른 숫자 기준으로 더 작은지, 또는 큰지 말해주는 것이다 예) 정답 7 10을 말하면 Down 5를 말하면 Up 즉 값들을 정렬하고, 정렬한 값들 중에 중간 값을 기준으로 탐색을 하는 것이다 예) 1,2,3,4,5,6,7,8,9,10 중 8 찾기 먼저 5를 탐색한다, 7은 5보다 크기 때문에 6~10 중 숫자들을 찾는다 6~10 의 중간값은 8 from bisect import bisect_left, bisect_right array = [0, 1, 2, 3.. 2023. 3. 14.
Udemy : 알고리즘 DFS, BFS, 백트래킹 Udemy : 알고리즘 DFS, BFS, 백트래킹 udemy 알고리즘 코딩 테스트 그래프 자료구조 그래프는 노드와 링크로 이루어진 자료구조다 노드는 점들이고, 노드를 이어주는 링크, Edge 또는 간선이라고 한다 SNS / 메신저 관계도를 그래프로 만들 수 있다 지도 / 네비게이션 같이 그래프를 실생활에 사용될 수 있다 무방향 또는 방향 그래프로 만들 수 있다 무방향이나 양방향 그래프는 동일한 개념이다 트리 자료구조 순환성이 없는 무방향 그래프다 코드를 그래프로 나타날 때에는 인접 리스트와 행열을 만들 수 있다 연결 행 연결 리스트 DFS (Depth First Search) 깊이 우선 탐색 스택 또는 재귀를 사용해서 구현을 한다 DFS는 완전 탐색이다 BFS (Breadth First Search) 너.. 2023. 3. 13.

티스토리툴바