본문 바로가기

백준55

[Python] 백준 2841 외계인의 기타 연주 🧑‍💻 [Python] 백준 2841 외계인의 기타 연주 Silver 1 - 스택 ![img](https://blog.kakaocdn.net/dn/cC1MR5/btr1QwKHa2P/iVlOamnCuGQNGj3KIqU18K/img.png) 코드 N, M = map(int, input().split()) stack = [[] for _ in range(7)] count = 0 for _ in range(N): l, p = map(int, input().split()) while stack[l] and stack[l][-1] > p: stack[l].pop() count += 1 if not stack[l] or stack[l][-1] < p: stack[l].append(p) count += 1 print(.. 2023. 3. 25.
[Python] 백준 1018 체스판 다시 칠하기 🧑‍💻 [Python] 백준 1018 체스판 다시 칠하기 Silver 4 - 완전 탐색 코드 N, M = map(int, input().split()) board = [list(input()) for _ in range(N)] def chess(i, j): global result change_1,change_2 = 0, 0 for row in range(8): for column in range(8): if (row + column) % 2 == 0 and board[i + row][j + column] == "B": change_1 += 1 elif (row + column) % 2 == 1 and board[i + row][j + column] == "W": change_1 += 1 if (row .. 2023. 3. 24.
[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.
[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.

티스토리툴바