Heecheol's blog

문제 https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음에 풀었을 때는 반복문의 중첩으로 배열을 전부 탐색해서 해결했다. 그래서 세 개의 케이스에서 시간초과가 났따. 10^5이므로 최악의 경우 충분히 시간초과가 나올 수 있는 크기였다. 그래서 한 번의 반복문을 통해 해결하려고 해보았따. 해결하기까지는 오래걸렸지만 막상 해결하고 나니 충분히 더 빨리 풀 수 있는 문제였다. 우선, 가장 마지막부터 처리하는 것이 가장 빠른 방법인 것을 알아..

문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 처음엔 문제도 제대로 이해못했고, 제대로 이해하고 나서도 푸는데 오래걸렸다. 그래프가 두 집합으로 나뉠때 각 집합의 원소들이 연결되어있지 않아야한다. 나는 BFS를 이용했다. visited의 첫 값을 0으로 두고, 1부터 차례대로 반복문을 돌렸다. 그래서 visited값이 0인 경우엔 값을 1로 만들고, 해당 점과 연결된 모든 점을 확인했다. 해당 점과 연결이 되어있다는건 같은 집합에 ..

문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 이 문제에서 중요한 것은 외부 공기와 접촉해야한다는 것이다. 처음에 아무생각없이 닿는 공기가 두 개 이상이면 바로 없애도록 해서 틀렸었다. 가장자리에는 치즈를 두지 않으므로 이를 이용해서 바깥 공기를 구해주면된다. 처음에 풀었던 방식은 우선 바깥공기를 전부 배열에 넣고, 다시 처음부터 BFS를 돌려 치즈를 구한 뒤에 공기랑 닿는 면이 바깥공기 배열에 들어가 있는지 확인해서 ..

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 어려웠다... 다른 BFS문제들과 대부분 비슷했지만, 먹이를 먹는 기준때문에 오래걸렸다. 처음에는 단순히 dx, dy의 순서만 바꿔서 해결하려고했는데, 이렇게 해서는 풀 수 없다는 것을 알게되었고 정렬을 해야 해결이 된다는 것을 알게되었다. 기본적인 BFS를 사용하는 것은 동일하다. 근데 이제 더 이상 갈 곳이 없다면 while문은 종료될 것이다. 이때, 탐색하는 동안 먹을 수 ..

문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 처음에는 벽을 어디에 세워야 바이러스가 최소한으로 퍼질지 고민을 오래했다. 근데 벽의 개수가 반드시 3개이고 n과 m이 큰 숫자도 아니기때문에 일단 모든 경우를 구해보기로 했다. 우선, 0인 위치를 전부 찾아서 3개로 만들 수 있는 모든 조합을 구했다. 다음으로 각 조합별로 실제로 벽을 세워 각각 BFS를 돌려 확인했다. 각 경우마다 안전범위를 구하는 것은 직접 하나하나 확인하지 않고, 처음에 구했..