'백준' 태그의 글 목록
본문 바로가기
728x90

백준12

백준 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.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.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.12015 [가장 긴 증가하는 부분 수열 2] Baekjoon Online Judge No.12015 [가장 긴 증가하는 부분 수열 2] 문제 12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 설명 2021.07.28 - [Algorithm (C++ based)/BOJ] - 백준 No.11053 [가장 긴 증가하는 부분 수열] 백준 No.11053 [가장 긴 증가하는 부분 수열] Baekjoon Online Judge No.11053 [가장 긴 증가하는 부분 수열] 문제 11053번: 가.. 2021. 7. 28.
백준 No.11053 [가장 긴 증가하는 부분 수열] Baekjoon Online Judge No.11053 [가장 긴 증가하는 부분 수열] 문제 11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 설명 Dynamic programming 을 이용하여 Memoization 을 통해 풀 수 있다. 아래와 같이 가장 긴 증가하는 부분수열을 구해야 하는 arr 배열이 있다. 정답을 구하기 위해서 arr 의 첫 번째 수 부터 li.. 2021. 7. 28.
백준 No.1328 [고층 빌딩] Baekjoon Online Judge No.1328 [고층 빌딩] 문제 1328번: 고층 빌딩 (acmicpc.net) 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 설명 핵심 변수 : unsigned long long city[N][L][R]; N개의 빌딩이 있고, 좌측에서는 L 개의 빌딩, 우측에서는 R 개의 빌딩이 보일 때 경우의 수의 값을 의미한다. city[1][1][1] 은 1개의 빌딩이 있고, 좌측에서는 1개의 빌딩, 우측에서는 1개의 빌딩이 보이는 경우의 수의 값을 의미한다. 이 경우엔 그냥.. 2021. 7. 12.
백준 No.1937 [욕심쟁이 판다] Baekjoon Online Judge No.1937 [욕심쟁이 판다] 문제 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 설명 DFS를 활용한 DP문제이다. land[i][j] array 를 입력되는 대나무 숲에 대한 정보이고, dp[i][j] array 를 (i, j) 위치에서 최대로 살 수 있는 일수라고 하자. 백준 사이트에 있는 입력 예시이다. 한 위치를 예로 설명을 해 볼 것이다. 위 경우를 가지고 dp[0][1]의 값을 구하는 과정, 식은 아래와 같다. dp[0][1] = max(dp[0.. 2021. 7. 11.
백준 No.17386 [선분 교차 1] Baekjoon Online Judge No.17386 [선분 교차 1] 문제 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 설명 선분 교차 여부를 확인하기 위해서 CCW를 사용하였다. CCW 설명 Link : 2021.06.27 - [C++ Algorithm/Math] - CCW (Counter Clock Wise) 위 첨부된 사진을 보면 CCW(A, B, C) 의 값은 양수이고 CCW(A, B, D) 의 값은 음수이다. 또한 CCW(C, D, A) 의 값은 음수이고 CCW(C, D, B.. 2021. 6. 28.
728x90

티스토리툴바