알고리즘 모음(C++)

문제 링크입니다 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 이 문제와 동일한 문제였습니다 https://junseok.tistory.com/63 백준 5427 - 불(C++) 문제 링크입니다 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동 junseok.t..

문제 링크입니다 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 문제 접근 방법 1. 상근이의 위치와 불의 위치를 입력과 동시에 저장한다. 2. 저장한 불의 위치에서 상하좌우로 불을 붙인다. 3. 불을 피해 상윤이의 위치에세 상하좌우로 이동한다. 4. 2번과 3번이 끝난뒤의 각 정보들을 큐에 저장한다. 5. answer값에 따라서 출력한다. 6. 1~5번을 Test_case 만큼 반복한다. 문제 접근 방법 - 2번 + 3번 + 4번 int bfs() { i..

문제 링크입니다 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 에라토스테네스의 체 + BFS를 이용하는 문제였습니다! 문제 접근 방법 1. 에라토스테네스의 체를 이용해 1000~9999까지의 소수를 구한다 2. 소수 한 쌍을 입력받은 뒤, 소수 경로를 구하는 BFS에 저장한다. 3. answer의 값에 따라 출력한다. 문제 접근 방법 - 1번 void find_prime_number() { for (int i = 2; i = 1000 && check[..

문제 링크입니다 https://www.acmicpc.net/problem/15644 15644번: 구슬 탈출 3 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net https://junseok.tistory.com/60 백준 13460 - 구슬 탈출 2(C++, 복습) 문제 링크입니다 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음..

문제 링크입니다 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 삼성 SW 역량테스트 기출 문제입니다. 답을 알기 전에는 매우 어렵지만, 원리를 알면 쉽게 풀리는 문제였습니다. 빨간 구슬과 파란 구슬을 동시에 움직이는 것을 구현하는게 핵심입니다! 문제 접근 방법 1. 처음 빨강, 파랑 구슬의 위치를 저장한다. 2. 빨간 구슬의 위치에서 상,하,좌,우에서 갈 수 있는 곳을 찾는다. 3. 빨간 구슬..

문제 링크입니다 https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 문제 접근 방법 1. 현재 남아 있는 치즈의 갯수를 확인한다. 2. 치즈가 남아있을 경우, 공기를 BFS를 통해서 탐색한다. 3. 공기와 접촉되어 있는 치즈를 녹은 상태로 만들어준다. 4. 치즈를 녹여준뒤, 다시 반복한다. 문제 접근 방법 - 1번 bool get_cheese() { int cnt = 0; for (int i = 1; i 마지막으로 남은 치즈를 출력할때 사용 문제 접근 방법..

문제 링크입니다 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 삼성 SW 문제였습니다. 구현하는 것이 많았던만큼, 신경을 써야했던 문제였습니다. 문제 접근 방법 1. 궁수 3명을 DFS를 통해서 순차적으로 선택한다. 2. map을 확인하면서 적이 남아있는지를 확인한다. 3. 적이 남아 있다면, 궁수와의 거리를 측정해, 쏠 수 있는지의 여부를 정한다. 4. 적을 이동한다. 5. 적이 없어질때까지 반복한뒤, 죽인 적의 수를 최댓값과 비교한다. 문제 접근 방..

문제 링크입니다 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net BFS와 DFS를 모두 사용하는 문제였습니다. 방문할 수 있는 지점이 다수일 경우, 작은 수부터 출력하는 것을 주의해야 했습니다. 문제 접근 방법 1. 백터를 이용해 정점에서 갈 수 있는 다른 정점들을 저장합니다. 2. 시작 지점부터 DFS를 탐색하면서, 방문 노드를 출력합니다. 3. 시작 지점부터 BFS를 탐색하면서, 방문 노드를 출력합니다...

문제 링크입니다 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 이분 그래프가 어떤 것인지는 https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html [알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 이분의 깃허브를 참고..

문제 링크입니다 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제입니다. DFS를 이용하는 것이 핵심이였습니다. 위 도형중에서 'ㅗ' 모양의 보라색 도형을 제외한다면 나머지 모두는 상하좌우 4번을 연속해서 이동한다면 모두 구할 수 있습니다. 문제 접근 방법 1. 모든 칸마다 DFS를 통해서 상하좌우 이동한다. 2. 4번 이동한다면, 지금까지의 최댓값과 비교한다. 3. 조건에 맞다면 'ㅗ' 모양으로 나올 수 있는 ..

문제 링크입니다 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS 문제였습니다 문제 접근 방법 1. 미로를 입력 받는다. 2. (1,1) 부터 (N,M) 까지 BFS를 통해서 최소 거리를 탐색한다. 문제 접근 방법 - 2번 void bfs(int a, int b){ q.push({a,b}); while(!q.empty()){ int x1 = q.front().x; int y1 = q.front().y; q.pop(); for(int i = 0; i < 4; i++){ i..

문제 링크입니다 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net BFS 문제입니다. 문제 접근 방법 1. 4방향 탐색과, 말로 이동할 수 탐색을 만든다. 2. BFS를 통해, 말로 이동할때와, 4방향으로 탐색할때를 모두 확인한다. 3. 도착점의 좌표를 확인해 최솟값을 찾는다. 문제 접근 방법 - 2번 while (!q.empty()) { int x1 = q.front().x; int y1 = q.front().y; int k1 ..