pwd

문제링크 : https://www.acmicpc.net/problem/1107난이도 : 골드5알고리즘 : 브루트포스풀이 과정0부터 9까지 숫자와 +, - 버튼이 있는 리모컨이 있다. 지금보고 있는 100번 채널에서 수빈이가 원하는 채널로 이동하기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 문제다. 원하는 채널로 이동하는 방법은 여러가지다.먼저, +, - 버튼만을 눌러서 이동할 수 있을 것이다. 또한, 숫자 버튼을 사용하여 원하는 채널의 번호를 입력하여 바로 이동할 수도 있다. 이 때, 숫자 버튼이 고장났을 수도 있기 때문에 원하는 채널로 바로 이동할 수 없는 경우도 있다. 그렇기 때문에 숫자 버튼을 사용하여 다른 채널로 이동한 뒤에 +, - 버튼을 사용하여 원하는 채널로 이동하는 경우를 고려해야 한다...

문제링크 : https://www.acmicpc.net/problem/16236난이도 : 골드3알고리즘 : 그래프 탐색, 구현풀이 과정N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어가 상하좌우로 인접한 칸으로 이동하는데 1초가 걸린다. 아기 상어는 자신의 크기 보다 작은 크기의 물고기만 먹을 수 있다. 아기 상어는 가장 가까운 물고기를 먹으려한다. 가장 가까운 물고기가 여러 마리인 경우 가장 위쪽, 가장 왼쪽에 있는 물고기를 먹는다. 아기 상어는 자신의 크기와 같은 수의 물고기를 먹으면 크기가 1 증가한다. 아기 상어가 몇 초 동안 물고기를 먹을 수 있는지 구하는 문제이다. 우선, ..

문제링크 : https://www.acmicpc.net/problem/2638난이도 : 골드3알고리즘 : 그래프 탐색, 구현풀이 과정세로 길이 N, 가로 길이 M의 모눈종이에 치즈가 올려져 있고, 치즈가 없는 공간에는 공기가 있다. 치즈는 치즈 외부의 공기와 2변 이상이 접촉하면 1시간만에 녹아버린다. 주어진 치즈가 모두 녹아 없어지는데 걸리는 시간을 구해야 한다.  치즈가 녹는 과정을 구현하려면 매 시간마다 모든 치즈에 대해 외부 공기와 접촉했는지 여부를 검사해야 한다. 이 때, 먼저 고려해야 할 것은 치즈 내부의 공간은 외부 공기와 접촉하지 않은 것으로 가정하는 조건이다. 이 조건 때문에 무작정 치즈에 인접한 공기의 개수를 세어서는 문제를 해결할 수 없었다. 한편, 모눈종이의 맨 가장자리는 치즈가 놓..

문제링크 : https://www.acmicpc.net/problem/17144난이도 : 골드4알고리즘 : 구현, 시뮬레이션풀이 과정크기가 R×C인 격자판 모양의 집에 미세먼지와 공기청정기가 있다. 매 초마다 미세먼지가 있는 칸은 인접한 네 칸으로 미세먼지가 확산된다. 미세먼지 확산이 끝나면 두 개의 공기청정기로 인해 공기가 순환하고 공기청정기로 들어간 미세먼지는 사라진다. 입력으로 주어지는 T초 후의 남아있는 미세먼지의 양을 구해야 한다.  문제의 요구사항에 맞춰 미세먼지 확산과 공기 순환을 구현하면 쉽게 해결할 수 있다.  먼저, 배열을 돌면서 미세먼지가 있는 칸이 있으면 각각 확산을 수행한다. 미세먼지는 (미세먼지의 양)/5 만큼 인접한 칸으로 확산하고 (확산한 칸의 수) x (미세먼지의 양) / ..

문제링크 : https://www.acmicpc.net/problem/5639난이도 : 골드4알고리즘 : 그래프, 재귀풀이 과정이진 검색 트리의 전위 순회 결과를 입력으로 받아서 후위 순회 결과를 출력하는 문제다. 먼저, 주어진 입력에 대해 이진 탐색을 수행하여 트리 구조를 만들어야 한다. 첫 번째 입력을 루트로 지정하고, 다음부터 입력되는 값에 대해 다음 규칙에 따라 위치를 지정한다.새로운 값이 루트 노드의 값보다 작은 경우왼쪽 자식 노드가 없으면 새로운 값을 왼쪽 자식 노드로 할당한다.왼쪽 자식 노드가 있으면 해당 노드를 루트로 하는 트리에 대해 다시 탐색한다.새로운 값이 루트 노드의 값보다 큰 경우오른쪽 자식 노드가 없으면 새로운 값을 오른쪽 자식 노드로 할당한다.오른쪽 자식 노드가 있으면 해당 노..

문제링크 : https://www.acmicpc.net/problem/1043난이도 : 골드4알고리즘 : 그래프 탐색풀이 과정문제에서 지민이는 거짓말하기를 좋아한다. 거짓말쟁이라는 것을 들키지 않으면서 최대한 많은 파티에서 거짓말을 하려한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 진실을 아는 사람에게 거짓말을 하거나, 거짓을 아는 사람에게 진실을 말하면 거짓말쟁이라는 것을 들키게 된다.  따라서 진실을 아는 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 이 때, 거짓말을 할 수 있는 파티 개수의 최댓값을 구해야 한다. 풀이의 핵심은 '진실을 아는 사람들과 같은 파티에 참가한 사람은 모두 진실을 아는 사람이다.' 라는 것이다. 진실을 아는 사람이 있는 파티는 반..

문제링크 : https://www.acmicpc.net/problem/1865난이도 : 골드3알고리즘 : 벨만-포드풀이 과정백준이가 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우 즉, 왕복 거리가 음수인 경우가 있는지 없는지 판단하는 문제이다. 다른 그래프 문제와 달리 M개의 양방향 도로와 함께 W개의 단방향 웜홀이 등장한다. 웜홀은 시계가 거꾸로 가는 길으로, 길이가 음수인 간선을 의미한다. 그래프에 길이가 음수인 간선이 존재하므로, 바로 벨만-포드 알고리즘을 생각했다. 처음에는 왕복 거리가 음수인 경우가 있는지 없는지 판단하기 위해서 모든 정점에서 벨만-포드 알고리즘을 수행해야 할 것이라 생각했다.하지만 ..

문제링크 : https://www.acmicpc.net/problem/3015난이도 : 플래티넘5알고리즘 : 스택풀이 과정두 사람 A와 B 사이에 A 또는 B 보다 큰 사람이 없는 경우의 수를 구하는 문제이다.브루트포스로 풀면 시간복잡도가 O(N^2) = 500,000^2 으로 1초의 시간제한을 훌쩍 뛰어넘어 버린다. 다른 방법을 생각해야 했다.왼쪽에서 오른쪽으로 이동하면서 쌍의 수를 카운트해보면, 바로 왼쪽에 있는 사람의 키에 따라 쌍의 수가 결정됨을 알 수 있었다. 왼쪽에 있는 사람의 키가 자신보다 크면 왼쪽 사람만 카운트하고, 작으면 바로 왼쪽 사람과 그 뒤의 사람까지 카운트하는 등의 규칙이 있어 보였다. 따라서 스택을 활용하여 규칙을 정의해보았다.  가장 핵심적인 규칙은 스택이 내림차순을 유지해야..

문제링크 : https://www.acmicpc.net/problem/1504난이도 : 골드4알고리즘 : 그래프 탐색풀이 과정간선의 가중치가 각각 다른 무방향 그래프에서 최단 경로를 구해야 하는 문제이다.다익스트라 알고리즘을 사용하면 얼핏 쉽게 풀릴 것 처럼 보이지만, 특이한 조건이 하나 있다. 문제에서 주어지는 두 정점을 반드시 거치면서 최단 경로로 이동하는 거리를 구해야 한다. 또한 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다.생각한 방법은 전체 경로를 3개의 경로로 나누는 것이다. 만약 1에서 부터 v1과 v2를 지나 n에 도착해야 한다고 하자. (여기서 v1과 v2의 순서는 무관하다.) 전체 경로를 1에서 v1까지의 최단 경로, v1에서 v2까지의 최단 경로, v2에서 ..

문제링크 : https://www.acmicpc.net/problem/15686난이도 : 골드5알고리즘 : 브루트포스풀이 과정1개 이상 13개 이하의 치킨집 중에서 M개를 골라서 모든 집의 치킨 거리의 합이 최소가 되어야 한다. 첫 번째로 전체 치킨집 중에서 M개를 고르는 작업을 생각해보자.치킨집을 고르는 작업에서 최악의 경우는 기존에 있던 치킨집의 개수가 13개이고 그 중에서 6군데 또는 7군데를 고르는 경우이다. 이는 곧 13C6(13C7)을 의미한다. M개의 치킨집을 고르고 나서, 모든 집에 대해 "치킨 거리"(가장 가까운 치킨집과 떨어진 거리)를 구해야 한다. 각각의 집들에 가장 가까운 치킨집을 선택된 치킨집들 중에서 찾아야 하므로 브루트 포스로 구현하면 2N *  M이라고 할 수 있겠다. 총 작..