본문 바로가기

알고리즘107

[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] 백준 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.
[Python] 백준 3107 IPv6 🧑‍💻 [Python] 백준 3107 IPv6 Gold 5 - 구현 이 문제는 IPv6를 고려해서, 상황들을 생각해서 코드를 짜면 되는 것이다 특히 ::를 집중적으로 생각해야 한다 :: 만 없었다면 그냥 0만 채우면 되는 문제 예) 25:09:1985:aa:091:4846:374:bb 같은 경우 그냥 0025:0009:1985:00aa:0091:4846:0374:00bb으로 바꿔주면 된다 그래서 입력을 먼저 받을 때에 : 기준으로 나눠서 리스트에 넣는다 그리고 그 리스트 안에 있는 요소들을 순회한다 만약 중간에 ::가 있으면, 리스트에는 ''으로 반환되어 있을 것이다 리스트 길이가 8이면 그대로 0만 채워 넣으면 된다 하지만 리스트 길이가 8이 아니면, ::를 채워 넣어줘야 한다 리스트 길이를 8로 맞출.. 2023. 3. 12.
Udemy : 알고리즘 탐욕법 탐욕법 매 순간마다 최선의 경우만 골라간다 다른 경우는 고려하지 않는다. 나중은 생각하지 않는다 모든 것을 보지 않기 때문에 완전탐색보다 빠르다 무엇이 최선인지 찾는게 포인트다 규칙을 찾는게 제일 좋다 시간 초과가 안 뜨게 되면 완전 탐색으로 문제를 풀어도 된다 하지만 시간 초과가 나면, 더 효율적인 알고리즘을 찾아야 한다 2023. 3. 10.

티스토리툴바