전체 글
[백준 - 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..
[백준 - 7490] 0 만들기 [C++]
1. 문제 https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 2. 풀이 전형적인 브루트포스 문제이다.. 나의 경우 두번 '출력 형식이 잘못되었습니다' 를 받았었는데.. '각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.' 이것을 간과한채 제출했었다.. 케이스별로 한 줄씩 띄워주니까 맞았다.. 문제는 연산자 3개로 표현가능한 모든 식을 만들어보고 그 식을 계산했을 때 0인지 판정하면된다. c++에는 eval함수가 없어서 직접 구현했다.. 3. 코드 #include #include #include #..