YANGORITHM

문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 문제 조건 중 "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고" 를 만족하기 위해 인접 리스트 형식으로 입력을 받은 후 정렬을 해줘야 한다. 그 후 dfs와 bfs를 진행 하면 된다. 코드 python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

문제 www.acmicpc.net/problem/17977 17977번: Triangulation A regular n-sided polygon P can be partitioned into n − 2 triangles by adding non-crossing line segments connecting two vertices of P. For example, a square can be partitioned into two triangles, a regular pentagon can be partitioned into three triangles www.acmicpc.net 풀이 각 정다각형에서 다음과 같은 답이 나온다. 1. 정육각형의 경우 내부에 정삼각형이 있어야 거리가 최소가 된다. 이때 최대거리..

문제 www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 다음과 같은 점화식을 만든다. 1. dp[i][0] = 수열에서 i번까지 선택했을 때 연속합의 최대값, 중간에 삭제를 진행하지 않음 2. dp[i][1] = 수열에서 i번까지 선택했을 때 연속합의 최대값, 이전에 삭제를 진행했다 or 현재 값을 삭제한다. n개의 수열 중에서 dp[n][0]와 dp[n][1] 까지 모두 구했을 때, 그 중에서 최대값을 찾으면 된다. 1번을 구하기 위한 점화식은 다음과 같다..

문제 www.acmicpc.net/problem/8895 8895번: 막대 배치 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. www.acmicpc.net 풀이 다음과 같은 점화식을 만든다. dp[n][l][r] = n개의 막대가 있을 때, 왼쪽에서 l개 오른쪽에서 r개 막대가 보인다. 그리고 길이 1인 막대가 왼쪽에 있을 때, 오른쪽에 있을 때, 가운데 있을 때로 나누어서 생각해 본다. 1. 길이 1인 막대가 왼쪽에 있을 때 : 이 막대가 사라졌을 때 왼쪽에서 보이는 막대가 1개 사라지므로 점화식은 다음과 같다. dp[n-1][l-1][r] 2...

문제 https://www.acmicpc.net/problem/6603 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 www.acmicpc.net 풀이 집합 S에 저장된 숫자들에 대해서 6개를 선택해서 만들 수 있는 조합을 출력하는 문제이다. 순열을 이용해서 조합을 구할 때는, 몇 개를 선택해서 조합을 이룰건지 알아야 한다. 이 때, 선택한 수들은 같은 숫자로 바꾸고 그 외 숫자들도 같은 수로 바꿔서 순열을 구하면 조합을 구할 수 있다. 예를 들어, 1 2 3 4 에서 3개를 선택해서 조합을 이루는 수를 구한다고 하면..

문제 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 풀이 모든 도시를 방문하고, 도시의 방문 순서를 다르게 하는 문제이다. 도시의 수는 최대 10개이다. 그러므로 가능한 방문 순서의 수는 10! 이 되고, 이를 순열을 이용해 나타낸다. d 배열을 이용해 도시를 저장하고, next_permutation() 함수를 이용해 d..

문제 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 www.acmicpc.net 풀이 그래프 탐색과 이분 탐색을 이용해서 해결하는 문제이다. 이분 탐색을 통해 중량 값을 찾고, 그래프 탐색을 통해 해당 중량 값으로..

문제 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마 www.acmicpc.net 풀이 주사위의 6면을 상하좌우앞뒤로 구분을 해서 생각한다. dice[6]에서 0:상, 1:뒤, 2:우, 3:좌, 4:앞, ..

문제 https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net 풀이 수열의 왼쪽에 있는 수가 오른쪽에 있는 수보다 몇 개가 더 큰지 알아내면 된다. 그 수 만큼 버블 정렬에서 swap이 일어나기 때문이다. 수열 1 3 5 2 4 의 경우 3은 2보다 크고, 5는 2와 4보다 크므로 버블 정렬에서 swap이 총 세번 일어난다. 병합 정렬을 이용해 왼쪽에 있는 수가 오른쪽에 있는 수보다 몇 개가 더 큰지 구할 수 있다. R 배열의 값을 새로운 정렬..

문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 풀이 문제에 나와있는 순서대로 구현을 해주면 된다. 특별히 신경 쓴 부분은 종료조건과 꼬리의 이동 부분이다. 뱀의 몸이 있는 공간을 che..