문제 링크 : https://www.acmicpc.net/problem/14916문제 설명춘향이는 2원과 5원짜리 동전만으로 손님에게 최소 개수의 동전으로 거스름돈 NNN원을 주어야 한다. 2원과 5원짜리 동전이 무한정 있을 때, 정확히 NNN원을 거슬러 줄 수 있는 최소 동전 개수를 구하는 문제이다.접근법처음에는 이 문제에 그리디 알고리즘이 필요하다는 점을 인지하지 못했지만, 문제를 분석하면서 각 단계에서 최적의 선택을 해야 함을 깨달았다.그리디 알고리즘을 적용하기 위한 조건은 다음과 같다: 1, 큰 단위의 동전 우선 사용: 5원짜리 동전이 2원짜리보다 크기 때문에, 큰 단위인 5원짜리를 우선적으로 사용해 거슬러 줌으로써 동전 개수를 최소화할 수 있다. 2, 남은 금액에 맞는 조정: 5원으로 나누어떨어..

문제 설명마법소녀 마도카는 고양이를 매우 좋아해 마법으로 고양이 N 마리를 키우고자 한다. 처음에는 고양이가 한 마리도 없으며, 아래 두 가지 마법을 사용하여 고양이를 늘릴 수 있다:생성 마법: 고양이 한 마리를 생성한다.복제 마법: 현재 집에 있는 고양이 수를 복제할 수 있다. 만약 현재 고양이가 k마리 있다면, 0마리 이상 k마리 이하를 추가로 만들 수 있다.목표는 이 두 마법을 사용해 최소 행동 횟수로 정확히 N 마리의 고양이를 만드는 것이다.접근법처음에는 그리디 알고리즘으로 접근해야 한다는 점을 깨닫지 못했지만, 문제를 분석하면서 각 단계에서 최적의 선택을 하는 것이 필요하다는 점을 알게 되었다.이 문제를 그리디 알고리즘으로 풀어야 하는 조건들은 다음과 같다: 1, 각 단계에서 최적의 선택: 고양..

이 문제는 여러 겹의 상자 안에 보관된 토마토가 익는 과정을 모델링하는 문제다. 상자 안에는 익은 토마토, 익지 않은 토마토, 그리고 토마토가 들어있지 않은 칸이 있다. 하루가 지나면 익은 토마토는 인접한 여섯 방향(위, 아래, 왼쪽, 오른쪽, 앞, 뒤)에 있는 익지 않은 토마토를 익게 만든다. 이 문제는 모든 토마토가 익을 때까지 최소 며칠이 걸리는지, 혹은 익지 못하는 토마토가 남는지를 계산하는 프로그램을 작성하는 것이다. 문제 링크 : https://www.acmicpc.net/problem/7569 접근법익은 토마토가 동시에 여러 방향으로 퍼져 나가는 상황을 모델링하기 위해 BFS(너비 우선 탐색)를 사용한다. 모든 익은 토마토의 위치를 큐에 넣고 BFS를 수행하여 익은 토마토가 하루 단위로 주변..

지구 온난화로 빙산이 녹으면서, 빙산이 여러 덩어리로 분리되는 최초의 시간을 구하는 문제입니다. 매년 빙산은 바닷물과 접한 부분만큼 높이가 줄어듭니다. 주어진 2차원 배열에서 각 빙산의 위치와 높이를 바탕으로 매년 빙산이 녹는 과정을 시뮬레이션하며, 빙산이 분리되는 최초의 시간을 출력합니다. 만약 모든 빙산이 녹을 때까지 분리되지 않는다면 0을 출력합니다.문제 링크 :https://www.acmicpc.net/problem/2573접근법1, 빙산 높이 감소 시뮬레이션:매년 동서남북 방향으로 바다(0)와 접촉하는 부분만큼 빙산의 높이를 줄입니다. 이를 afterYear() 함수로 구현하여, 각 칸마다 인접한 바다의 개수를 세고 빙산 높이를 줄입니다.2, 빙산 덩어리 개수 확인:매년 빙산의 덩어리 수를 BF..

주어진 단방향 그래프에서 출발 정점(1번)에서 시작하여 특정 정점에 팬클럽이 있는 경우를 피할 수 없는지 여부를 확인하는 문제입니다. 출발 정점에서 가능한 모든 경로를 탐색하며, 팬클럽을 만나지 않고 종착점에 도달할 수 있는 경우 "yes"를, 그렇지 않다면 "Yes"를 출력합니다.문제 링크 :https://www.acmicpc.net/problem/25195접근법1, 그래프 초기화: 주어진 정점 수와 간선을 기반으로 단방향 그래프를 구성합니다. 또한 팬클럽이 있는 위치를 표시하기 위해 has_fanclub 배열을 초기화하여 팬클럽이 있는 정점은 2로 표시합니다. 2, BFS 탐색: BFS를 사용하여 출발 정점(1번)에서 이동 가능한 모든 경로를 탐색합니다. 이때, 팬클럽이 있는 정점(2)으로 이동하는 ..

오늘은 특정 거리의 도시 찾기 문제를 해결하면서 BFS(너비 우선 탐색)를 이용하여 최단 거리를 계산하는 방법을 복습했습니다. 이 문제는 특정 시작 도시에서 다른 도시들까지의 최단 거리를 탐색하고, 최단 거리가 정확히 K인 도시들을 찾는 것이 목표입니다.문제 링크 : https://www.acmicpc.net/problem/18352내 문제 접근 방법1, 그래프 구성주어진 도시와 도로를 단방향 인접 리스트 loads로 나타내어 그래프를 구성했습니다. 각 도시는 정점, 도로는 간선으로 표현되며, BFS를 통해 각 도시로의 최단 거리를 탐색할 수 있도록 구현했습니다.2, BFS를 이용한 최단 거리 탐색최단 거리 문제에서 BFS를 활용하면, 시작점으로부터 각 도시로의 최단 거리를 계산할 수 있습니다.visit..

오늘은 체스판 위의 나이트 이동 문제를 해결하면서 BFS(너비 우선 탐색)를 이용해 최단 이동 횟수를 계산하는 방법을 배웠습니다. 나이트가 특정 위치에서 목표 위치까지 최단 거리로 이동해야 하는 문제로, BFS를 사용하여 레벨 단위로 탐색하며 최단 거리를 구할 수 있었습니다.문제링크 : https://www.acmicpc.net/problem/7562 내 문제 접근 방법1, 그래프 문제로 인식체스판 위의 칸을 정점으로 보고, 나이트의 이동 가능 경로를 간선으로 연결하여 그래프 형태로 문제를 이해했습니다.2, BFS로 최단 거리 탐색최단 거리 문제에서는 BFS가 유리하므로, 시작 위치에서 목표 위치로 이동할 때 BFS를 사용했습니다. BFS는 현재 위치에서 가능한 이동들을 순서대로 탐색하며, 가장 먼저 도..

오늘은 촌수 계산 문제를 해결하면서 DFS(깊이 우선 탐색)를 이용해 두 사람 간의 촌수를 계산하는 방법을 배웠습니다. 이 문제는 부모-자식 간 관계로 구성된 그래프 구조에서 두 노드 간의 거리를 찾는 문제입니다. DFS를 통해 경로를 탐색하고 촌수를 계산하여 해결할 수 있었습니다.문제 링크 : https://www.acmicpc.net/problem/2644 내 문제 접근 방법1, 그래프 구성 : 각 사람의 부모-자식 관계를 양방향 그래프로 나타내기 위해 인접 리스트 형태의 map을 사용했습니다. 주어진 관계에 따라 두 사람의 번호를 서로 연결했습니다.2, DFS를 이용한 촌수 계산 : DFS를 통해 시작 사람부터 목표 사람까지의 경로를 탐색하며, visited 배열을 사용하여 방문 여부와 촌수를 기록..