알고리즘/Baekjoon

[C++] 백준 20056번 마법사 상어와 파이어볼

20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 에 수록된 문제. 구현 / 시뮬레이션 문제로, 문제에서 요구하는 대로 풀면 된다. 오랜만에 풀어보는 알고리즘 문제라서 특수한 알고리즘이 필요없는 구현 문제일 줄 알았는데 시간 복잡도를 생각 안하고 풀어서 시간 초과를 냈었다. 문제풀이 다음과 같은 순서대로 구현했다 모든 파이어볼을 이동시킨다. 2개 이상의 파이어볼이 있는 곳에서 합친 후 4개로 나눠준다. 1번 로직과 2번 로직을 반복만 시켜주..

[C++] 백준 2589번 보물섬

그래프 탐색 문제. 오랜만에 풀어보는 알고리즘 문제라 그런지 머리가 잘 안 돌아갔지만 그래프 탐색이란 것을 알고 쉽게 풀 수 있었다. 문제풀이 땅 - 땅으로 이동하는 거리중 가장 긴 거리를 찾으면 된다. 돌아가면 안되고 최단거리 기준이므로 DFS는 안되고 BFS로 탐색해야한다. 이 기준대로만 구현하면 쉽게 풀 수 있다. /* * 백준 2589번 보물섬 * https://www.acmicpc.net/problem/2589 * 그래프 탐색 이론 - 너비 우선 탐색, 브루트 포스 */ #include #include #include #include using namespace std; int height, width; char board[51][51]; bool visit[51][51]; vector visi..

[C++] 백준 20057번 마법사 상어와 토네이도

20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 에 수록된 문제. 구현 / 시뮬레이션 문제로, 문제에서 요구하는 대로 풀면 된다. 문제풀이 나는 다음과 같은 로직, 순서를 구현해서 풀었다. 0 = 좌, 1 = 하, 2 = 우, 3 = 상 이라는 방향을 잡았다. 이동하는 횟수는 (좌, 하) 1번씩, (우, 상) 2번씩, (좌, 하) 3번씩 ...의 규칙으로 반복된다. 각 방향이 이동할 때, (r, c)에 얼마를 계산해야 하는지, 그리고 계산한 좌표..

[C++] 백준 2096번 내려가기

다이나믹 프로그래밍 문제. 메모리 제한이 상당히 제약적인데, 이 부분을 잘 이해했으면 쉽게 풀 수 있는 문제다. 처음에 배열을 10만 x 3개씩 만들어서 풀어보려 했는데, 메모리 초과가 났다. 결국 게시판을 참고해서 풀 수 있었다. 문제풀이 문제에 표현된 그대로, N번째 줄마다 1, 2, 3번째에 도달했을 때 최대, 최소값을 기록해두면 된다. 첫번째 칸에 도달한 경우에는 이전에 1, 2번째 칸인 경우이다. 두번째 칸에 도달한 경우에는 이전에 1, 2, 3번째 칸인 경우이다. 세번째 칸에 도달한 경우에는 이전에 2, 3번째 칸인 경우이다. 이 문제의 핵심은 이전에 지나온 칸, 앞으로 지나올 칸의 수는 저장할 필요가 없다는 것이다. 따라서 입력을 받을 때마다 i번째 칸에서의 최대, 최소값을 기록해두면 된다...

[C++] 백준 2638번 치즈

2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 구현 / 시뮬레이션 / 그래프 탐색 문제. 문제에서 구현하라는 대로 구현해서 풀면된다. 제출하고 시간이 44ms가 나왔는데, 다른 사람들은 보통 12 ~ 20ms가 나온 것 같았다. 유의미한 차이는 아니라서 일단은 그냥 넘어갔다. 문제풀이 문제의 조건들은 다음과 같다. 격자의 가장자리들에는 치즈가 존재하지 않는다. 한 시간마다 외부공기와 동, 서, 남, 북 중 두 방향 이상 외부공기와 접한 치즈는 녹는다. 치즈로 둘러쌓인 공간은 외부 공간으로 치지 ..

[C++] 백준 23288번 주사위 굴리기 2

23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 수록 문제. 구현 / 시뮬레이션 문제이다. 이해하기 어려웠고, 시간을 잡아먹었던(자꾸 8번째 테스트 케이스가 이상하게 나와서 고쳤다.) 것들이 있었다. 조건들을 정리해가면서 문제 풀이를 정리해 보겠다. 문제풀이 문제의 조건들을 정리해보면, 다음과 같은 순서로 구현하면 된다. 높이, 너비, 주사위 이동횟수를 입력받는다. 격자의 각 칸의 숫자를 입력받는다. 여기까지가 기본 입력이다. 그 후에 이동횟수만큼 아래를 반복..

[C++] 백준 2573번 빙산

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 구현 / 그래프 탐색 문제. 삼성 기출 문제와 유사한 문제였다. 문제에서 제시하는대로 구현하면 맞출 수 있는 문제다. 문제풀이 다음과 같은 순서로 만들면 된다. 0이 아닌 칸들에서 인접한 칸들 중 0인 칸들의 개수를 큐에 저장해둔다. 큐에 있는 정보를 토대로 각 칸마다 0인 칸들의 개수만큼 높이에서 빼준다. DFS / BFS를 통해 연결 요소의 개수를 구해서 2 이상인 경우에는 몇 년 걸렸는지 출력한다. 2 미만일 경우에는 1로 돌아간다. 이 때 DFS /..

[C++] 백준 13549번 숨바꼭질3

다익스트라 문제. 이 문제는 처음에 BFS로 접근했는데 자꾸 틀렸습니다. 가 나왔다. 게시판을 참고하고 나서 다익스트라로 풀었다. 그런데 사람들을 보니 우선순위 큐 + BFS이면 풀 수 있다고 했다. 나도 우선순위 큐 + BFS로 시도했었는데 왜 못풀었을까..흠.. 문제풀이 이 문제는 다익스트라로 풀어야 한다. 왜냐하면 이전의 숨바꼭질 문제들은 +1, -1, *2의 시간초과가 모두 같았지만, 이번 문제의 경우 *2가 걸리는 시간이 0초이다. 따라서 *2들 먼저 모두 탐색한 후에 또 거기서 +1, -1 *2들 먼저.. 이런식으로 탐사해야한다. /* * 백준 13549번 숨바꼭질3 * https://www.acmicpc.net/problem/13549 * 그래프 탐색 이론 - 다익스트라 * 다익스트라에서는 ..

[C++] 백준 12851번 숨바꼭질 2

그래프 탐색 문제. BFS 너비 우선탐색을 통해서 풀면 되는 문제다. 조건이 꽤 까다로운 문제다. 다른 그래프 탐색 문제들처럼 풀면 메모리 초과가 난다. 문제풀이 예전에 숨바꼭질1을 풀었었는데, 그 때는 그냥 가장 빠르게 목적지에 도달한 경우 몇 초인지만 알면 되는 문제였다. 이 문제는 가장 빠르게 목적지에 도달한 경우가 몇 초이고, 그 시간대로 가는 경우가 몇 가지가 존재하는지 출력하면 된다. 조건은 짜기 나름이므로, 코드 전문을 보고 틀린 이유만 정리하겠다. /* * 백준 12851번 숨바꼭질 2 * https://www.acmicpc.net/problem/12851 * 그래프 탐색 이론 - 너비 우선 탐색(BFS) */ #include #include using namespace std; int s..

[C++] 백준 1068번 트리

그래프 탐색 문제. 그 중에서도 트리 & DFS문제이다. 트리의 기본 개념만 안다면 쉽게 풀 수 있다. 조건을 하나 잘못 생각해서 틀렸었다. 문제풀이 어려운 것 없이, 부모 - 자식, 자식 - 부모 관계를 모두 저장해둔다. 그리고 각각 다음에 사용한다. 부모 - 자식 관계 : 트리에서 깊이 우선 탐색을 통해 리프 노드가 몇 개인지 구할 때 사용한다. 자식 - 부모 관계 : 지울 노드의 부모 노드의 번호를 구하고 해당 부모 노드에서 부모 - 자식 관계에서 지울 노드를 찾은 후 지울 때 사용한다. 루트 노드가 예시 케이스에서는 -1이 모두 첫번째로 나오긴 했지만, 나중에 나오는 경우를 대비해서도 코드를 구현했다. /* * 백준 1068번 트리 * https://www.acmicpc.net/problem/10..