알고리즘 모음(C++)

문제 링크입니다 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 ..

문제 링크입니다 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net BFS 문제였습니다. 문제 접근 방법 1. 배추들의 좌표를 입력받은뒤, 배열에 배추의 존재여부를 표시한다. 2. For문을 통해서 배추가 존재하면서, 전에 방문하지 않았던 곳을 찾아 BFS를 실행한다. 3. 필요한 지렁이의 갯수를 출력한다. 4. Test_case 만큼 반복한다. 문제 접근 방법 - 1번 for (int i = 0; i > x >..

문제 링크입니다 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 간단한 bfs,dfs 문제였습니다. 저는 bfs로 풀었습니다. 문제 접근 방법 1. 연결된 컴퓨터들을 입력받은뒤, 각각의 백터에 저장한다. 2. BFS를 1번 컴퓨터 시작한다. 문제 접근 방법 - 1번 for (int i = 0; i > x >> y; com[x].push_back(y); com[y].push_back(x); } 연결..

문제 링크입니다 https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net MST 문제였습니다. Union() + Find()를 할 때 기존과 다르게 Union 부분에서 조건을 걸어줘야 했던 문제였습니다. 문제 접근 방법 1. 발전소의 번호를 입력받을때, 배열을 하나 만들어서 해당 지점에 발전소가 있다는 것을 표시한다. 2. 간선들의 정보를 입력받고, 비용에 따라 오름차순으로 정렬한다. 3. 정렬한 간선들의 갯수..

문제 링크입니다 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 2차원 공간에서의 최소 비용 구하기와 다르게 3차원이면서 N의 범위도 100,000 까지이기에 까다로운 문제였습니다. 방법을 생각하는데 꽤 오래걸린 것 같습니다.(괜히 골드1 문제가 아니였습니다) 문제 접근 방법 1. 각 좌표들을 입력받는다.(저는 구조체로 입력받았습니다) 2. 좌표들을 X, Y, Z축에 따라 오름차순으로 정렬한다. 3. 각 축으로 ..

문제 링크입니다 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 쿠르스칼 알고리즘을 사용해서 풀었습니다. 문제 접근 방법 1. 각 학교가 남초 대학인지 여초대학인지 알 수 있는 배열을 선언해 값을 저장합니다. 2. 구조체 백터를 통해서 출발점, 도착점, 비용을 저장한뒤, 비용값에 따라 오름차순으로 정렬합니다. 3. 백터의 처음부터 마지막까지 for문을 돌립니다. 4. for문 안에서 출발점과 도착점이 서..

문제 링크입니다 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 간단한 MST 문제였습니다. 본격적인 쿠르스칼 알고리즘을 실행하기 전에 연결되어 있는 지점들을 연결해주고 시작하는게 포인트였습니다. for (int i = 0; i > x >> y; Union(x, y); } 연결되어 있는 지점을 입력 받은 뒤에 Union함수를 통해서 연결해줬습니다. for (..