내 맴

문제 ) 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/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..

문제 ) https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [ 풀이 ] BFS 와 DFS에 대한 문제이다. DFS와 BFS는 이진트리로 밖에 안해봤었는데 이 문제는 조금 달랐다 . DFS의 경우 , 만약 Node사이에 연결선이 존재한다면 연결된 Node부터 이어주게 된다. 그러나 BFS의 경우에는 level이 같은 Node들 부터 출력하게 된다. - DFS 설명 https://luz0911.tistory.co..

문제 ) https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)�� www.acmicpc.net [ 풀이 ] 피보나치 수열의 경우 재귀함수를 사용하면 안되는 대표적인 문제이다. 재귀함수를 사용하게 되면 중복호출이 매우 많아지기 때문이다. 재귀 알고리즘을 이용해 피보나치 수를 구하려면 의사코드는 이런식으로 작성된다 이때, Fib함수가 얼마나 호출되는지 보기 위해서 그래프로 그려보았다. 재귀함수를 이용해 피보나치 수를 구하면 그래프의 분홍색 동그..