728x90 BOJ45 백준 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 [트리의 지름] 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.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. 백준 No.1626 [두 번째로 작은 스패닝 트리] BOJ No.1626 [두 번째로 작은 스패닝 트리] 문제 1626번: 두 번째로 작은 스패닝 트리 (acmicpc.net) 1626번: 두 번째로 작은 스패닝 트리 첫째 줄에 그래프의 정점의 수 V(1 ≤ V ≤ 50,000)와 간선의 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 간선으로 연결된 두 정점과 그 간선의 가중치가 주어진다. 가중치는 100, www.acmicpc.net 설명 * 최소 스패닝 트리 / 최소 신장 트리 (MST) * 최소 공통 조상 (LCA) 먼저 최소 스패닝 트리(MST) 를 먼저 구해야 한다. 두 번째로 작은 스패닝 트리는 앞서 구한 MST 보다 총 가중치의 값은 최소한으로 늘어나야 한다. 문제에서 예제 입력을 가지고 최소 스패닝 트리.. 2021. 8. 17. 백준 NO.13537 [수열과 쿼리 1] Baekjoon Online Judge No.13537 [수열과 쿼리 1] 문제 13537번: 수열과 쿼리 1 (acmicpc.net) 13537번: 수열과 쿼리 1 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 설명 * 정렬 * 인덱스드 트리 * 세그먼트 트리 (Segment tree) 세그먼트 트리, 인덱스드 트리를 이용하여 풀 수 있으며 이번에는 인덱스드 트리를 통해 풀어보았다. 세그먼트 트리나 인덱스드 트리에서 가장 중점은 트리의 노드를 어떻게 정의하느냐 인 것 같다. 이번 문제에선 각 트리의 노드.. 2021. 8. 14. 백준 No.14427 [수열과 쿼리 15] Baekjoon Online Judge No.14427 [수열과 쿼리 15] 문제 14427번: 수열과 쿼리 15 (acmicpc.net) 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 설명 * 세그먼트 트리 (Segment tree) 기본적인 세그먼트 트리 자료구조를 통해 풀 수 있는 문제이다. 1. 트리의 노드들에 그 노드에 해당하는 수열의 영역 내에서 최소값을 가지는 원소의 {값, 인덱스} 를 저장한다. 최소값을 저장하는 조건은 문제의 요구대로 아래.. 2021. 8. 13. 백준 No.2887 [행성 터널] Baekjoon Online Judge No.2887 [행성 터널] 문제 2887번: 행성 터널 (acmicpc.net) 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 설명 최소 스패닝 트리(최소 스패닝 트리 / 최소 신장 트리 (MST)) 를 통해 풀 수 있는 문제이다. 각 정점끼리의 간선의 가중치의 값은 두 정점의 거리에 따른다. 결국 모든 정점 사이에 간선이 존재하게 된다. 정점의 수는 최대 100,000 개 이기 떄문에 이 때 총 간선의 수는 약 (100,000^2) .. 2021. 8. 10. 이전 1 2 3 다음 728x90
