본문 바로가기

백준55

[Python] 백준 1520 내리막길 🧑‍💻 [Python] 백준 1520 내리막길 Gold 3 - DFS DFS는 확실히 알았으나, 이걸 어떻게 DP로 풀어야 할지 몰랐다 1) 50 ▶️ 35 ▶️ 30 ▶️ 27 ▶️ 24 ▶️ 22 ▶️ 15 ▶️ 10 2) 50 ▶️ 45 ▶️ 37 ▶️ 32 ▶️ 20 ▶️ 17 ▶️ 15 ▶️ 10 3) 50 ▶️ 45 ▶️ 37 ▶️ 30 ▶️ 25 ▶️ 20 ▶️ 17 ▶️ 15 ▶️ 10 위를 보면, 15 ▶️ 10 은 3 경로 모두 겹친다 그리고, 20 ▶️ 17 ▶️ 15 ▶️ 10은 2번과 3번이 겹친다 겹치는 부분은 한번만 탐색을 하면 된다 즉 이미 방문을 했다면, 10까지의 경로는 겹치는 것이다 즉 겹치는 경로를 굳이 한번 더 탐색할 필요가 없다 코드 import sys sys.se.. 2023. 2. 15.
[Python] 백준 24482 알고리즘 수업 🧑‍💻 [Python] 백준 24482 알고리즘 수업 Silver 2 - DFS DFS 문제이다 깊이 우선 탐색으로, 탐색을 할 때마다 1씩 더해주면 된다 연결이 아예 안 되어 있을 때에는 -1 이다 내림차순 문제풀이 DFS 코드를 짜면 된다 코드 import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline def dfs(start, count): visited[start] = count for cur in graph[start]: if visited[cur] == -1: dfs(cur, count + 1) N, M, start = map(int, input().split()) visited = [-1] * (N + 1) graph = [[].. 2023. 2. 14.
[Python] 백준 7569 토마토 🧑‍💻 [Python] 백준 7569 토마토 Gold 5 - BFS 무조건 BFS로 풀어야 하는 문제이다 시작점이 하나가 아닐 수 있다 그래서 queue 안에다 시작점들을 모두 찾아서 넣는다 BFS를 할때마다 주변 노드에다 방문 표시 대신 1을 더해서, 더한 숫자를 넣는다 마지막에 다시 탐색을 해야하는데, 0이 하나라도 있으면 -1을 출력하고, 그게 아니면 더한 숫자들 중 제일 큰 숫자에 1을 빼서, 답을 출력한다 7576과 같은 문제이지만, 높이가 추가가 되었다 3중 포문을 쓰되, 3중 리스트 사용법을 익혀야 한 문제풀이 bfs 식 주변을 탐색하고, 주변에 있는 노드 위주로 탐색하기 위해 popleft를 사용 첫 for문 queue에다가 시작 점들을 넣는다 시작점이 하나일 때에는 for문을 돌릴 필요가.. 2023. 2. 13.
[Python] 백준 7576 토마토 🧑‍💻 [Python] 백준 7576 토마토 Gold 5 - BFS 무조건 BFS로 풀어야 하는 문제이다 시작점이 하나가 아닐 수 있다 그래서 queue 안에다 시작점들을 모두 찾아서 넣는다 BFS를 할때마다 주변 노드에다 방문 표시 대신 1을 더해서, 더한 숫자를 넣는다 마지막에 다시 탐색을 해야하는데, 0이 하나라도 있으면 -1을 출력하고, 그게 아니면 더한 숫자들 중 제일 큰 숫자에 1을 빼서, 답을 출력한다 문제풀이 bfs 식 주변을 탐색하고, 주변에 있는 노드 위주로 탐색하기 위해 popleft를 사용 첫 for문 queue에다가 시작 점들을 넣는다 시작점이 하나일 때에는 for문을 돌릴 필요가 없지만, 이 문제에서는 시작점이 1개 이상이 주어질 수 있다 두번째 for문 결과값을 탐색한다 bfs.. 2023. 2. 13.
[Python] 백준 25418 정수 a를 k로 만들기 🧑‍💻 [Python] 백준 25418 정수 a를 k로 만들기 Silver 3 - 그리디 A에서 K를 찾는 것이 아닌, K에서 A를 찾는 것이 제일 쉽다 제일 큰 수에서, 짝수이면 2를 나누고, 홀수이면 1을 빼준다 단 짝수에서 2를 나눴을 때에 항상 A보다 커야 한다 문제풀이 K를 A로 만들어야 하고, 2로 최대한 많이 나누어야지, 최소로 연산을 할 수 있다 while 문을 통해 K가 A가 될때까지 순회를 한다 K가 짝수이거나, 2로 나누었을 때 A보다 커야지만 2로 나눌 수 있다 그게 아니고, 홀수이거나 K를 2로 나누었는데, A보다 작으면 계속 1로 빼준 코드 end, start = map(int, input().split()) count = 0 while start != end: if start .. 2023. 2. 10.
[Python] 백준 2644 촌수계산 🧑‍💻 [Python] 백준 2644 촌수계산 Silver 2 - DFS / BFS DFS도 사용할 수 있지만, BFS를 이용해서 촌수를 찾았다 부모 노드와 연결되어 있는 노드들을 먼저 탐색을 한다 탐색을 하면서 같은 번호를 찾으면 된다 문제풀이 BFS를 이용해서, 노드와 연결된 노드들 중에서 end와 같은 번호가 있는지 확인을 해야 한다 여기서 중요한 것은 while문에서 그냥 count를 넣으면, queue에서 뽑을때마다 count에 1이 더해진다 이것을 방지하기 위해, queue에 튜플 형식으로, (노드번호, 촌수)를 넣는다 코드 from collections import deque n = int(input()) start, end = map(int, input().split()) start, en.. 2023. 2. 9.
[Python] 백준 1388 바닥 장식 🧑‍💻 [Python] 백준 1388 바닥 장식 Silver 4 - 그래프 탐색 탐색을 두 번 해야한다. 즉 2중 for문을 두번 사용한다. 탐색을 해서 '-' 가 연결되어 있는 나무 판자와 '|'가 열결되어 있는 나무 판자들의 개수를 센다 단 나무 판자의 너비는 1이다 문제풀이 2중 for문을 두번 순회를 해야 한다. 첫 번째는 가로형 나무 판자들을 찾는 것이고, 두 번째는 세로형 나무 판자들을 찾는 것이다 먼저 '-' 이면 계속 순회를 하되, 다음 판자가 '|'이면, 그 나무 판자를 count에 1을 더해준다 즉 '|'이 나타나면, '-' 의 연속 된 나무 판자가 끊겼다는 것이다 그리로 2중 for문 중 2번째 fo.. 2023. 2. 8.
[Python] 백준 1260 DFS와 BFS 🧑‍💻 [Python] 백준 1260 DFS와 BFS Silver 2 - DFS / BFS DFS는 깊이 우선이다. 먼저 한 쪽을 선택해서, 탐색을 하는 것이다 BFS는 넓이 우선 탐색이다. 즉 부모 노드에 여러 자식 노드가 있으면, 바로 연결되어 있는 자식 노드들 부터 탐색을 한다 문제풀이 함수를 사용했다 리스트를 만들고, 리스트 안에 있는 요소들을 오름차순으로 정렬했다 (만약 길이 2개 이상이면, 숫자가 작은 곳부터 탐색을 한다) DFS 같은 경우, 재귀를 이용한다 즉 DFS는 만약 방문을 안 한 노드가 있으면, 그 노드를 다시 DFS(V)를 한다 방문을 했으면 for문은 끝까지 돌아갈 것이다. 즉 for문이 끝났다는 것은, 이미 모든 노드를 한번씩 탐색을 했다는 것이다 BFS 같은 경우 queue를.. 2023. 2. 6.
[Python] 백준 1083 소트 🧑‍💻 [Python] 백준 1083 소트 Gold 5 - 그리디 문제풀이 최대한 제일 큰 숫자가 앞으로 와야 한다 숫자의 움직임에 제한이 있다 일단 swap만큼의 숫자들을 슬라이스를 통해 슬라이스 안에 제일 큰 숫자를 가지고 온다 그리고 i까지, 뒤로 그 큰 숫자를 앞으로 가지고 온다 이것을 swap이 0이 될때까지 반복을 한다 코드 N = int(input()) array = list(map(int, input().split())) swap = int(input()) for i in range(N): max_num = max(array[i : i + swap + 1]) max_num_index = array.index(max_num) for j in range(max_num_index, i, -1):.. 2023. 2. 1.

티스토리툴바