728x90 Algorithm (C++ based)/BOJ51 백준 No.1944 [복제 로봇] 백준 No.1944 [복제 로봇] 문제 1944번: 복제 로봇 (acmicpc.net) 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 설명 * MST * BFS 위와 같은 테스트 케이스가 있다고 하자! 먼저, bfs 를 통해 위와 같이 하나의 시작점과 각 Key 들이 이루는 그래프를 구했다. 그래프의 간선들은, 연결된 두 노드의 최소 거리이다. Key는 최대 250개, 지도 크기는 최대 50 * 50 == 2,500 이니까, Key 하나하나 2,500 크기의 맵을 BFS 해도 .. 2023. 2. 5. 백준 No.2008 [사다리 게임] 백준 No.2008 [사다리 게임] 문제 2008번: 사다리 게임 (acmicpc.net) 2008번: 사다리 게임 사다리 게임을 할 때 사용되는 사다리가 있다. 세로선은 N개가 있고, 가로선은 M개가 있다. 세로선은 맨 왼쪽 것부터 1, 2, …, N의 번호가, 가로선은 맨 위의 것부터 1, 2, …, M으로 번호가 붙어 있 www.acmicpc.net 설명 * dp 2차원 dp 를 이용하여 풀이가 가능하다. dp[i][k] : i 번째 가로선까지 체크를 했을 때 시작점에서 k 번째 세로선까지 오기까지의 최소비용 위 값을 결정하기 위해선 이전 dp 값의 왼쪽, 현재 위치, 오른쪽 인 dp[i - 1][k - 1], dp[i - 1][k], dp[i - 1][k + 1] 을 고려한다. 1) dp[i - .. 2022. 12. 4. 백준 No.1167 [트리의 지름] 백준 No.1167 [트리의 지름] 문제 1167번: 트리의 지름 (acmicpc.net) 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 설명 * DFS 백준 No.1967 [트리의 지름] (tistory.com) 백준 No.1967 [트리의 지름] 백준 No.1967 [트리의 지름] 문제 1967번: 트리의 지름 (acmicpc.net) 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온.. 2022. 11. 28. 백준 No.1967 [트리의 지름] 백준 No.1967 [트리의 지름] 문제 1967번: 트리의 지름 (acmicpc.net) 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 설명 * DFS 트리의 지름은 트리의 정점들간 경로들 중 가장 긴 거리를 말한다. DFS를 통해 크게 두 단계로 해결할 수 있다. DFS를 통해 임의의 정점에서 가장 먼 정점을 확인한다. DFS를 통해 위 확인된 정점에서 가장 먼 정점까지의 거리가 트리의 지름이다. 저 방법으로 어떻게 트리의 지름이 구해질까? 위 경우는 [A 정점]에서 가장 먼 정점이 .. 2022. 11. 28. 백준 No.1725 [히스토그램] 백준 No.1725 [히스토그램] 문제 1725번: 히스토그램 (acmicpc.net) 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 설명 * 스택 스택 자료구조를 이용하여 히스토그램 그래프상에서 가장 넓은 직사각형을 구하는 문제이다. 아래 특징을 고려해야 한다. [특징] 1. k 번째 값을 입력받았을 땐, k - 1 번째 값까지 다뤄진 stack 을 다룬 뒤, 마지막으로 k 번째 값을 stack에 push 한다. => k 번째 값은 그대로 push 되는게 아니라, stack에서.. 2022. 11. 13. 백준 No.1167 [트리의 지름] BOJ No.1167 [트리의 지름] 문제 1167번: 트리의 지름 (acmicpc.net) 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 설명 * Tree * DFS 트리의 지름이란, 트리 상에서 가장 먼 거리를 가지는 두 정점 사이의 경로이다. 위 예시 트리에서 H 노드와 G 노드 사이의 거리는 23이며, 이 경로가 트리의 지름이 된다. 트리의 지름은 다음과 같은 순서로 구해진다. 1. DFS를 통해 임의의 정점(x)으로부터 가장 먼 정점(y)을 구한다. 2. DFS를 통해 구해진 (y).. 2022. 7. 13. 백준 No.10986 [나머지 합] BOJ No.10986 [나머지 합] 문제 10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 설명 * 구간 합 (Prefix sum) 구간 합을 간단하게 활용 한 문제이다. 참고 Link : 2022.04.19 - [Algorithm (C++ based)/Algorithm 이론] - 구간 합 (Prefix sum) 만약 4번째 원소 (index == 3) 부터 19번째 원소 (index == 18) 까지 구간 합이 .. 2022. 4. 19. 백준 No.1019 [책 페이지] BOJ No.1019 [책 페이지] 문제 1019번: 책 페이지 (acmicpc.net) 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 설명 * 수학 숫자의 영역을 3개로 나누어 카운팅을 한다. 위 예시는 입력값이 8853 인 경우이다. 처음에 값을 입력 받으면, 위 예시처럼 입력된 숫자와 가장 가까운 9로만 이루어진 더 작은 숫자를 찾는다. 위 경우에는 999 가 이에 해당된다. 이 숫자를 기점으로 first area, second area 로 나뉘게 된다. 그리고, 9로 끝나는 가장 가까운 수를 찾는다. 이 숫자를 기점으로 second area, last area 로 나.. 2022. 4. 13. 백준 No.5670 [휴대폰 자판] BOJ No.5670 [휴대폰 자판] 문제 5670번: 휴대폰 자판 (acmicpc.net) 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 설명 * 자료 구조 * 트라이 (Trie) 문자열을 저장하는 자료구조 (Trie : 트라이 (Trie) : 문자열 저장 자료구조) 를 이용하는 문제이다. 각 Node 의 옆에 파란 숫자는 그 글자까지 나오기까지 키보드를 누른 횟수이다. 또한 빨간 테두리 Node 는 단어의 끝을 알리는 Node 이다. 키보드를 누르는 경우는 크게 세 가지가 있다. 1. 아직 아무 문자도 안 눌.. 2022. 4. 2. 백준 No.7420 [맹독 방벽] BOJ No.7420 [맹독 방벽] 문제 7420번: 맹독 방벽 (acmicpc.net) 7420번: 맹독 방벽 첫 번째 줄에 건물의 수 N과 거리 L이 주어진다. (3 ≤ N ≤ 1000, 1 ≤ L ≤ 1000, N과 L은 정수) 다음 N개의 줄에 거쳐 건물의 좌표 Xi와 Yi가 정수로 주어진다. (-10000 ≤ Xi, Yi ≤ 10000) 모든 건물의 좌 www.acmicpc.net 설명 * 볼록 껍질 (컨벡스 헐 : Convex hull) 볼록 껍질을 응용하여 풀 수 있는 문제이다. 아래 예시를 들어 보았다. 건물들의 좌표를 위와 같이 입력을 해 보았다. 또한 해당 좌표들을 좌표평면에 표시 해 보았다. 위 좌표들을 모두 감싸면서 건물들에선 최소 L 만큼 떨어져 있어야 하는 방벽을 세워야 한다. .. 2022. 3. 28. 백준 No.1708 [볼록 껍질] BOJ No.1708 [볼록 껍질] 문제 1708번: 볼록 껍질 (acmicpc.net) 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 설명 * 볼록 껍질 / 컨벡스 헐 (Convex hull) 볼록 껍질 위와 같이 평면 좌표에 N개의 점이 있을 때 점들을 이어 볼록 다각형을 만들면서, 잇지 않은 나머지 점들은 볼록 다각형 내부에 있도록 하는 것 이다. 볼록 껍질을 구현하기 위한 전처리 과정은 아래와 같이 정리할 수 있다. 1. 점들 중 껍질을 만들기 시작하는 점을 찾는다. - 보통 y값.. 2022. 3. 26. 백준 No.11400 [단절선] BOJ No.11400 [단절선] 문제 11400번: 단절선 (acmicpc.net) 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net 설명 * 그래프 * 단절선 단절선 : 어떠한 그래프에서 임의의 간선을 제거했을 때 두 개 이상의 그래프들로 나누어지게 하는 간선 [단절점]과 거의 비슷하게 생각을 하면 된다. 하지만 간선을 제거하는 경우는 단절점과 같이 정점을 제거하는 경우와 조금 다르게 다뤄지는 부분이 있다. 1. 단절선을 찾는 알고리즘은 단절점을 찾는 알고리즘과는 달리 루트노드를 .. 2021. 8. 29. 백준 No.3190 [뱀] BOJ No.3190 [뱀] 문제 3190번: 뱀 (acmicpc.net) 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 설명 * 구현 우선순위 큐 와 셋 을 사용하여 구현을 해서 풀었다. 게임이 끝나는 조건은 두 가지 조건이 있다. 1. 벽과 만나는 경우 -> 현재 위치가 맵을 벗어났을 때 현재 시간을 return 하였다. 2. 몸과 부딪히는 경우 -> 현재 몸이 있는 좌표들을 set 에 추가하여 몸과 부딪히는 여부를 파악하였다. 2-1) 현재 좌표에 해당하는 set 이 이미 있다면, 몸과 부딛힌 경우이므로 현재.. 2021. 8. 26. 백준 No.11266 [단절점] BOJ No.11266 [단절점] 문제 11266번: 단절점 (acmicpc.net) 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 설명 * 그래프 * 단절점 단절점 : 어떠한 그래프에서 임의의 정점을 제거했을 때 두 개 이상의 그래프들로 나누어지게 하는 정점 개념 자체는 간단하다. 위 그래프에서 단절점은 3, 5 번째 정점이 될 것이다. 3번 정점을 제거함으로써 3개의 그래프로 나뉘어지고, 5번 정점을 제거함으로써 2개의 그래프로 나뉘어졌기 때문이다. 단절점에 대한 파악은 루트노.. 2021. 8. 21. 백준 No.1261 [알고스팟] BOJ No.1261 [알고스팟] 문제 1261번: 알고스팟 (acmicpc.net) 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 설명 * Dijkstra (다익스트라) * 너비 우선 탐색 (BFS) 주어진 미로의 각 좌표들을 노드라고 생각하고, 좌표에서 이동할 수 있는 방향은 상하좌우로 인접한 네 방향이므로 이 네 방향을 하나의 간선이라고 생각할 수 있다. 좌표의 최대 크기는 100 * 100 이다. 따라서 노드의 최대 개수는 10,000 개가 되며 한 노드당 좌표의 모서리에 위치한.. 2021. 8. 17. 이전 1 2 3 4 다음 728x90
