내 맴

문제 ) https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net [ 풀이 IDEA ] - 다익스트라(Dijkstra) 알고리즘을 이용해서 문제를 해결하였다. 다익스트라 알고리즘은 최소 힙(heapq) 이용해서 풀어주면 좋다는거!! 꼭 기억하자 1️⃣ 초기화 사항 => 시작점으로 부터의 거리 list(distance), heapq 정의 2️⃣ [시작 점(start) 👉 최소 힙에서 추출한 점(node) 👉 해당 점(node)와 연결된 다른 점(nnode)] 으로..

문제 ) https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net [ 풀이 IDEA ] BFS이용해서 문제를 풀어줄 수 있다 1️⃣ BFS를 통해 열린 국경선을 체크한다. (조건: 두 나라의 인구 차이 L이상, R이하) 2️⃣ 국경이 열린 나라들의 위치를 list에 저장 3️⃣ 국경이 열린 나라들의 인구를 update 4️⃣ 국경이 열리지 않을 때까지 반복 - python code from collections import deque dx..

문제 ) https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net [ 풀이 IDEA ] 1. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이 2. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이 위의 2가지를 구해야한다. 2번 뿐만 아니라, 1번을 구할 때에도 문자열의 앞뒤가 같은 문자여야만 한다. 그렇기 때문에, 1/2번은 한번에 구해주면 된다! dictiona..

문제 ) https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net [ 풀이 IDEA ] 문제만 보면 단순해보이지만 그냥 BFS로만 풀다가는 시간오류가 난다 를 1턴으로 두고, 다음턴에 백조가 탐색 할 위치 큐 / 다음턴에 얼음이 녹을 위치 큐 를 따로 두고 BFS로 문제를 풀어야한다. 💡 문제 아이디어가 생각나지 않아서 다른분의 블로그를 참조해서 문제를 해결했다. https://itsmain.tistory.com/10 백준 ..

문제 ) https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net [ 풀이 IDEA ] 1. BFS/DFS로 풀어야하는 문제! 2. 그러나, 단순히 풀면 시간에러가 난다. 💡 SET 이용해서 문제 해결! ▶ BFS의 경우, queue대신에 set을 사용 & set에 좌표/visited(지나온 알파벳)을 저장한다 - python code dx = [0,0,-1,1] dy = [-1,1,0,0] def solution(board): global ma..

문제 ) https://www.acmicpc.net/problem/14658 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net [ 풀이 IDEA ] 1. N, M ≤ 500,000 이므로 트램펄린을 한칸씩 옮기는 Brute Force로는 문제를 해결할 수가 없다! 2. 그러나, K

문제 ) https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net [ 풀이 ] 아파트들을 모두 순회해야함으로 탐색 알고리즘 DFS를 사용하여 문제를 풀어보았다. 우선, 입력받은 값들 (집의 위치)을 home list에 저장하였고 방문한 집을 표시하는 visit list도 만들어주었다. 또한, 방향을 알려주는 list인 dx와 dy를 이용하여 문제를 풀어주었다. 현재 집을 기준으로 오른쪽,왼쪽,위,아래에 있는 집들을 접근하기 위한 list이다. x좌표 (..

문제 ) https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net [ 풀이 ] 그래프 탐색에 대한 문제이다. BFS, DFS 방법으로 둘 다 구현해 보았다. 먼저, DFS방법으로 푼 코드이다. 재귀함수를 이용해준다. - Python code (DFS ) visit=[1] def DFSWorm(current): global count, visit for i in range(1,n+1): # 바이러스에 걸리지 X & 길이 연결되어있는 경우 if i not i..