알고리즘 모음(C++)

문제 링크입니다 https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1≤N≤1,000)과 도로의 개수 M(1≤M≤n*(n-1)/2) 이 주어진다. 입력의 두 번째 줄 www.acmicpc.net MST를 두번 실행하면 풀리는 문제였습니다! 문제 접근 방법 1. 출발점, 도착점, 비용을 백터에 저장한다. 2. 비용에 대해서 내림차순으로 먼저 정렬한다.(1 -> 내림막길임으로 내림차순으로 했습니다) 3. 최소 비용을 구한다. 4. 비용에 대해서 오름차순으로 정렬한다. 5. 최대 비용을 구한다. 간단한 MST 문제임으로 자세한 것은 코드를 참고해주세..

문제 링크입니다 https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 크루스칼 알고리즘을 사용하면 쉽게 풀리는 문제였습니다! 1번 도시는 정복하고 있기에 1번에서 최소 비용으로 갈 수 있는 곳을 먼저 정복한 뒤 Union+Find를 해주면 되는 문제였습니다! 문제 접근 방법 1. 백터에 시작점과 끝점, 비용을 저장한다. 2. 비용에 대해서 오름차순으로 정렬한다. 3. 1번 도시를 찾은 후, 먼저 연결해주고 시작한다. 4. Union+Find를 통해서 모..

문제 링크입니다 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 삼성 SW 역량 테스트 기출문제였습니다! 문제 접근 방법 1. 상어의 정보를 vector에 저장한다. 2. 먼저 낚시꾼이 상어를 잡는다. -> 이때 잡은 상어는 잡았다는 표시를 한다. 3. 상어를 움직인다. -> 이때 speed만큼 전부 움직인다면 시간초과가 된다. 따라서 움직이는 횟수를 줄여야한다. -> 한마리 상어를 전부 움직였을때, 그 자리에 상어가 있다면..

문제 링크입니다 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net DFS +DP를 이용하면 풀 수 있는 문제였습니다. 무한번 움직일 수 있는 경우, 모든 선택지마다 값을 새로 찾는 경우 -> 시간 초과가 생긴다! 따라서 해당 칸에서 움직일 수 있는 최대 횟수, 이미 왔던 곳에 다시 왔다면 무한이라고 처리해야하는 문제입니다! 문제 접근 방법 1. char배열로 값을 입력 받은뒤 int형 배열에다가 옮긴다. (H는 0으로 옮겼습니다) 2. dfs탐색..

문제 링크입니다 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 접근 방법 1. map을 입력받는다. 2. (1,1) 부터 BFS를 시작한다. -> check[x][y][k]로 만들었습니다. 이때 k는 벽을 얼마나 부셨는가? 입니다. 3. (N,M)에 도달했다면, 이동 횟수를 return 합니다 4. (N,M)에 도달하지 못했다면, -1를 return합니다. 5. return 값에 따라서 출력을 다르게 ..

문제 링크입니다 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 6방향 탐색을 이용한 탐색 문제였습니다! 문제 접근 방법 1. 입력과 동시에 시작 위치를 저장한다. 2. 6방향 탐색을 통해서 갈 수 있는 곳을 찾는다 -> 이전에 방문하지 않았으면서, building[i][j] == '.'인 곳 3. 탐색 중, 출구에 도착한다면 -> 이동 횟수를, 도착하지 못한다면 -> -1를 return 한다 문제 접근 방법 - 2번 + 3번 int bfs() { ..

문제 링크입니다 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 마지막으로 남은 치즈를 출력할때 사용 문제 접근 방법..