PS/BOJ

1. 문제https://www.acmicpc.net/problem/14502 2. 문제 풀이이 문제는 지도를 순회하면서 바이러스가 퍼지지 않은 안전영역의 최대 크기를 구해야 한다. 여기에서 바이러스가 최소한으로 퍼지도록 벽을 총 3개만! 놓을 수 있다.  그래서 지도에서 0인 구역을 찾고 벽을 세운 다음(1로 처리), 3개의 벽을 다 세우고 나면 bfs를 통해서 안전구역의 개수를 구한다. 그래서 0인 구역을 찾을 때는 완전탐색, 바이러스가 퍼지고 난 후 안전구역을 찾을 때는 BFS를 사용해야 한다. 마지막으로 안전구역의 최대값을 구해주면 된다.#include #include #include using namespace std;int dx[4] = {-1, 0, 1, 0};int dy[4] = {0, 1,..

1. 문제https://www.acmicpc.net/problem/1753 이 문제는 시작점 k부터 나머지 간선까지 최단 경로를 구하는 문제다. 정점과 간선의 개수는 1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000로 아주 큰 숫자다. 이를 주의해서 풀이해야 한다. 2. 문제 풀이처음에는 다익스트라 알고리즘을 사용해서, 2차원 벡터 weight에 각각의 방향 그래프를 초기화하고, distance를 업데이트하는 방식을 사용했다. 이렇게 하니까 메모리 초과가 떴다. 그 이유는 위에선 언급한 것처럼, 정점과 간선의 개수가 너무 많은데, 불필요하게 weight를 (n+1) * (n+1) 크기를 갖도록 설정해 희소행렬이 되어버렸다. #include #include #include #define INF 99..

1. 문제https://www.acmicpc.net/problem/5427 2. 문제 풀이이 문제는 불이 매초마다 번질 때, 상근이가 몇 초만에 건물을 탈출 할 수 있는지 출력해야 한다. 불은 벽으로 번질 수 없으며 상근이는 벽을 통과하지 못한다. 상근이는 불이 옮겨진 칸이나 이제 불이 옮겨질 칸으로 이동할 수도 없다. 불이 상근이의 위치에 옮겨짐과 동시에 상근이가 다른 칸으로 이동할 수는 있다. 불도 매초마다 이동하고 상근이도 매초마다 이동할 수 있기 때문에 각각 BFS를 구현해야 한다. 그래서 상근이의 위치인 '@'이 입력으로 들어오는 경우와 불의 위치인 '*'이 입력으로 들어오는 경우, 각각의 큐에 push 한다. 불이 먼저 이동한 후에, 상근이가 이동해야 한다.불이 확산되는 BFS에서는 현재 fi..

1. 문제https://www.acmicpc.net/problem/1697 2. 문제 풀이수빈이와 동생의 위치를 입력받아서 동생의 위치까지 가는데 걸리는 시간을 출력하는 문제다.수빈이의 위치가 X라고 할 때, 1초만에걸어가면 X-1 혹은 X+1 만큼 갈 수 있다.순간이동하면 X * 2 만큼 갈 수 있다. 이때 1초에 이동할 수 있는 모든 경우의 수를 q에 넣고 하나씩 탐색하며 visited된 상태인지만 확인해주면 된다.#include #include using namespace std;queue > q;int visited[100001] = {0,};int main() { int n, k; cin >> n >> k; q.push(pair (n, 0)); visited[n] = 1;..

1. 문제https://www.acmicpc.net/problem/2573  2. 문제 풀이문제의 핵심은 다음과 같다.빙산과 바다 데이터를 2차원 배열로 입력받는다.바다에 많이 접한 빙산일 수록 높이가 더 빨리 줄어든다.1년마다 빙산의 높이가 줄어든다.덩어리가 2개 이상으로 분리되는 최초의 시간을 출력한다. 처음에는 BFS를 1번 돌면서 0에 맞닿아 있는 수만큼 값을 빼주었더니, 0이 되어버린 경우까지 포함되어서 BFS를 두 번 도는 방법을 택했다. 할 일은 다음과 같이 2가지로 나눌 수 있다.컴포넌트 개수 세기주변의 바다(0) 개수만큼 높이 낮추기컴포넌트를 세는 BFS, 주변의 바다 개수만큼 빼주는 BFS를 구현해보자. 먼저 컴포넌트를 세는 건 일반 BFS처럼 방문처리하고 q에서 하나씩 읽어오면 된다...

1. 문제https://www.acmicpc.net/problem/7569 2. 문제 접근문제를 요약하면 다음과 같다. 위, 아래, 오른쪽, 왼쪽, 앞, 뒤 총 6방향을 탐색해야 한다.익은 토마토는 익지 않은 토마토에 영향을 준다.한 상자에 들어있는 토마토가 모두 익는데까지 걸리는 기간을 출력한다.만약 배열에 저장될 때부터 모든 토마토가 익은 상태면 0, 모든 토마토가 익지 않은 상태면 -1을 출력한다. 이를 기반으로 문제를 풀어보자. 입력될 때부터 익은 토마토라면 q에 위치를 저장한다. 그리고 익은 토마토 위치에서부터 bfs 탐색을 시작하고, 만약 익지 않은 토마토가 인접해있다면 1로 바꾸어주고 tmp에 push 한다. 이때 tmp는 입력된 이후, 다른 토마토에 의해 익은 토마토가 된 것의 위치를..

1. 문제https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 2. 문제 해석이 문제는 주어진 숫자를 적절히 더하거나 빼서 target를 맞추는 경우의 수를 구하는 문제이다. 예를 들어, [1, 1, 1, 1, 1] 이라는 배열이 주어졌을 때, 각각을 더하거나 뺄 수 있으므로 자연스럽게 트리 구조를 떠올릴 수 있다. 그래서 재귀적인 방법을 사용해 트리를 순회해 최종 리프 노드의 값이 target과 같으면 answer++ 해주면 된다. #include #..

1. 문제 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 2. 문제 접근 문제를 이해하다보니 BFS로 풀면 되겠다고 답이 나왔다. 그래서, BFS 코드를 구현했더니 틀렸다. 문제를 제대로 안봤으니까. 결론적으로 1부터 5까지 각 숫자에 도달할 때까지 거리를 구하면 80%는 해결이다. 예시의 그래프는 아래와 같이 표현할 수 있다. 1부터 예시를 들면, 1은 2까지 [1-3-2]로 2단계, 3까지 ..

1. 문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 2. 문제 접근 입력 받은 N 값을 어떻게 하면 최대한 적은 봉지로 나눌 수 있는지 생각해야 한다. 초기에는 N값을 받고 5로 나누고, 5로 나눈 나머지 값을 다시 3으로 나눈 나머지가 0이면, (5로 나눈 몫 + 3으로 나눈 몫) 으로 결과값을 내려고 했다. 그러나, 이런 방식은 오래 걸리고 복잡하다. 그래서 결론적으로 시도했던 방법은, Dynamic Programming을 이용했다. DP[] ..

문제에서 주어진 조건은 다음과 같다. N이 되기 위한 조건 주어지는 진짜 약수들의 배수이다. N은 주어진 진짜 약수들과 같은 수가 아니다. 진짜 약수들은 1과 N을 제외한 수이다. 예를 들어, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24인데, 문제 조건에 따라 1과 24를 제외하면 진짜 약수인 2, 3, 4, 6, 8, 12가 남는다. 문제에서는 진짜 약수를 보고 N을 찾아야 하는데, 진짜 약수의 최솟값과 최댓값을 곱하면 24가 나온다는 것을 알 수 있다. 따라서 주어지는 약수들을 배열로 먼저 받고 이들을 오름차순 정렬한 다음, 최솟값과 최댓값을 곱하면 된다. #include #include #include #include using namespace std; int main() { int..