💡 Problem Solving

[백준 - 4179] 불! [C++]

1. 문제 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 2. 풀이 불의 Queue와 지훈이의 Queue를 만들어서 동시에 BFS를 돌려주면 된다. 처음에는 지훈이의 Queue를 만들고 깊이가 바뀔때 2중포문으로 직접 불을 확산시켜줬더니 시간초과가 났다. q.size()를 이용하면 이전 레벨의 노드를 모두 꺼내서 쓰기때문에 while한번돌때마다 깊이가 하나 증가하는 셈이다. 3. 코드 #include #include #incl..

[백준 - 6593] 상범 빌딩 [C++]

1. 문제 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 2. 풀이 전형적인 BFS로 최단거리를 구하는 문제지만, 3차원이라는 것이 주요 특징이다. 3. 코드 #include #include #include #include #include using namespace std; int L, R, C; // 층, 행, 열 int df[6] = {0, 0, 0, 0, 1, -1}; int dy[6] = {-1, 0, 1, 0, 0, 0}; int dx[..

[백준 - 1946] 신입 사원 [C++]

1. 문제 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 2. 풀이 그리디 문제이다. 일단 n이 10만이므로 O(n^2) 으로는 풀 수 없다. 그래서 우선 서류순으로 정렬하고, 1번째 지원자는 서류로 1등이니 반드시 뽑힌다. 2번째 지원자부터는 면접순위를 비교하면서 세줬다. 어떤 지원자가 서류점수는 낮더라도(정렬되어있으니 당연히 낮음) 현재까지의 최고 면접 순위보다 높은경우 그 지원자를 선발하고 key를 교체한다. 3. ..

[백준 - 4358] 생태학 [C++]

1. 문제 https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 2. 풀이 문제 자체는 어렵지 않지만 자주 안쓰면 까먹을법한 내용들이 많이 들어있다. 1. 입력의 개수가 따로 주어지지 않고 EOF면 종료하는 방법 while(getline(cin, str)) { // EOF면 종료 ... } 2. 소수점 자리수 맞추는 방법 // 소수점 4자리까지 표시 cout

[백준 - 20055] 컨베이어 벨트 위의 로봇 [C++]

1. 문제 https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 2. 풀이 시뮬레이션 문제이다. 문제의 주어진 조건을 꼼꼼히 보고 수행하면된다. 시뮬레이션 풀 때 함수를 작게 쪼개면 편한 것 같다. 일단, 나는 마지막 테스트케이스에서 계속 틀렸었는데.. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 이 조건을 제대로 안봤다.. 그래서 해당 로직을 수행하는 for문을 역순으로 바꾸..

[백준 - 1197] 최소 스패닝 트리 [C++]

1. 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 2. 풀이 크루스칼 문제이다. 1. 간선을 가중치를 기준으로 정렬한다. 2. 사이클이 생기지 않는 경우 반복하여 합친다. (사이클의 판정은 unino-find를 사용) 3. 합쳐진 간선의 개수가 (정점의 개수 - 1)인 경우, MST가 완성되었으므로 종료한다. 3. 문제 #include #include #include using namesp..