728x90 ProgramSolve/Baekjoon23 [BOJ] 1911번 - 흙길 보수하기 (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 이 문제는 [물웅덩이들을 모두 덮으려고 한다.] 라는 조건이 있으므로 물웅덩이가 보이면 일단 덮으면 된다. 그러나 널빤지의 길이는 정해져 있으므로 덮다보면 입력받은 물웅덩이의 위치가 이미 덮여져 있을 수 있다. 어차피 모든 웅덩이는 덮어야하니 웅덩이의 [끝 위치 - 시작 위치]를 통해 웅덩이의 길이를 구하여 필요한 널빤지의 개수를 구했다. 단, 위에서 설명했듯이 이미 덮여져 있는 위치가 존재할 수 있으므로 이에 대한 처리로 current라는 변수를 두어 시작 위치를 덮여져 있지 않은 위치로 변경할 수 있도록 했다. 🍀 풀이 🍀 import sys n, l = map(int, sys.stdin.readline().split()) water = [list(map(int, sy.. 2023. 9. 7. [BOJ] 13549번 - 숨바꼭질3 (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 어제 공부한 다익스트라 알고리즘을 연습해보았다. 다익스트라 알고리즘과 BFS 2가지 방식으로 풀어보았다. (코드는 아래에) 1. 다익스트라 알고리즘을 이용한 풀이 1. 수빈이의 위치를 시작 정점으로 둔다. 2. 현재 위치 i에 +1, -1 *2 한 위치에 대해 저장되어 있는 시간 times[k]와 도달한 시간(times[i] + 1 또는 times[i])을 비교하여 도달한 시간이 더 작으면 times[k]를 갱신한다. 3. heap이 빌 때까지 2번 과정을 반복한다. 이때, 주의할 점은 가중치가 없지만 가중치로 생각한 값은 도달한 시간으로 times의 값이다. 만약 이를 times를 도착 정점의 개수만큼만 만들면 올바른 값을 도출하지 못할 것이다. 위의 문제에서 주어진 예.. 2023. 9. 5. [BOJ] 1753번 - 최단경로(Python) + Dijkstra Algorithm 🗒️ 다익스트라 알고리즘 (Dijkstra Algorithm) 모서리 또는 정점에 가중치가 부여된 그래프에서 두 정점 사이의 최단 경로를 찾는 알고리즘 가중치가 없는 그래프에서의 최단경로는 BFS를 사용! 어떤 시작점 s가 주어졌을 때, 그 정점에서 시작하여 다른 모든 정점으로 가는 최단 경로를 찾는다. 단, 음수인 가중치가 없는 경우에만 쓸 수 있다. 실제 최단 경로는 우리집에서 옆집으로 이동하는 것이지만, 우리집에서 은행을 거쳐 가는 것이 비용상 이득이 되는 경우가 발생한다. 즉, 값이 음수인 모서리가 있으면 경로를 만들어가는 도중에 아주 작은 음수 값을 가지는 모서리가 있어서 이미 트리에 들어있는 최단 경로와 전혀 다른 경로를 만들어야 할 수 있다. 동작 과정(간선 완화 과정) 1. 모든 꼭짓점을 .. 2023. 9. 4. [BOJ] 6064번 - 카잉 달력(JAVA) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 중국인의 나머지 정리 참고 블로그 https://blog.joonas.io/23 중국인의 나머지 정리 - 이해하기 쉬운 설명 중국인의 나머지 정리(CRT; Chinese Remainder Theorem)연립 합동식의 유일한 해를 찾는 정리이다. 예를 들면서 설명과 함께 전개하는 게 가장 이해하기 쉽다. 개념 이해를 위해 연립 합동식이 2개일 때 blog.joonas.io 나머지 연산을 사용해보려고 했지만 어려워서 구현 실패 그래서 문제 풀이 블로그를 참고했는데 여기서 내가 이해한 부분을 정리하기 위해 글을 작성 문제풀이 참고 블로그 https://girawhale.tistory.com/10 [백준] 6064번: 카잉 달력 - JAVA 문제 링크 BOJ 6064번: 카잉 .. 2023. 3. 27. [BOJ] 2667번 - 단지번호붙이기(JAVA) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 시작 정점 찾기 이미지 상으로 확인했을 때 왼쪽 위 > 오른쪽 위 > 왼쪽 아래 > 오른쪽 아래 와 같이 Z 모양으로 시작 정점을 찾는다. 현재 위치의 값이 1이면서 방문하지 않으면 시작 정점이다. 시작 정점을 기준으로 그래프 탐색 BFS 그래프 탐색 사용 대각선을 제외한 상하좌우 위치에 아파트가 있으면 현재 단지에 있는 아파트 수 증가 BFS 탐색이 끝나면 탐색한 아파트 수 반환 탐색이 끝나고 아직 남은 정점이 있으면 ①,②번 과정 반복 모든 정점의 탐색이 끝나면 올바른 형식으로 출력 후 프로그램 종료 ★ 아파트 단지내에 있는 아파트 수를 저장하는 배열(aparts[]) 초기화 ★ 🍀 풀이 코드 🍀 import java.io.BufferedReader; import ja.. 2023. 3. 23. 이전 1 2 다음 728x90
