거창한 시작

www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 알고리즘 종류 DP 사고 과정 최댓값이 만들어지는 과정을 보고 DP같다라는 생각을 했습니다. 제가 DP를 해결하는 방법은 과정을 깔끔하게 나열하고 규칙을 찾는 것입니다. 최솟값을 나열하기로 했습니다. n을 20까지 나열해 보니 규칙이 보이기 시작했습니다. 성냥개비 2배부터 8개까지를 뒤에 붙이는 식으로 숫자가 생성되었습니다. 예를 들어, n=10이면 다음의 경우가 나옵니다. 8,2 / 7,3 / 6.4 / 5,5 / ..

www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 알고리즘 종류 트리 LCA 사고 과정 1. 인접행렬로 노드 쌍을 받아습니다. 그리고 depth과 parents 배열로 트리를 만들어 줍니다. 2. 공통 부모를 찾을 두 노드를 받습니다. 두 노드의 깊이가 같아질 때까지 부모를 타고 올라갑니다. 두 노드가 같은 깊이에 도달하면, 동시에 타고 올라가면서 공통 부모가 될때까지 올라갑니다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..

www.acmicpc.net/problem/13308 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net 알고리즘 종류 다익스트라 DP 사고 과정 이 문제는 노드에 비용과 간선의 거리가 존재합니다. 이 2가지를 고려해야 합니다. 이 문제를 간단하게 생각해 보겠습니다. 노드가 그물형으로 연결된 것이 아닌 선형으로 연결되어 있다고 가정하겠습니다. 상태가 아래와 같을 때, 1번노드에서 2번 노드로 가는 비용은 20 * 거리가 됩니다. 이제 2번 노드에서 3번으로 가겠습니다. 비용 30과 비교했을..

www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 알고리즘 종류 다익스트라 DP 사고 과정 1번 노드에서 N번 노드로 가는 최소비용을 구하는 문제입니다. 이때, 도로를 포장하거나 하지 않을 수 있습니다. 접근하기 전에 가장 일반적인 다익스트라 문제를 생각해 보겠습니다. 이 문제를 기본적인 다익스트라 문제로 바꿔본다면, 모든 도로를 포장하지 않고 1번 노드에서 N번 노드로 이동하는 최소 비용을 구하는 문제가 될 것입니다. 그러..

www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 알고리즘 종류 부분 집합 자료 구조 사고 과정 부분 집합을 할 parents 배열을 만듭니다. 그리고 몇 명이 연결되어 있는지 기록할 state라는 배열을 만듭니다. 이후 union_find으로 해결하면 됩니다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36..

www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 알고리즘 종류 자료구조 분리집합(Union-Find) 사고 과정 무식하게 하게 2중 for문으로 하면 시간복잡도가 N^2이 나온다. 따라서 다른 방법을 사용해야 한다. gi가 주어지면 gi부터 넣는 것이 빠르게 처리된다. 그리고 이후 -1씩 감소하면서 빈 곳을 찾으면 된다. 그렇다면, gi를 기준으로 왼쪽에 빈 곳이 있는 지 한 번에 알 수 있을까? 분리 집합을 이용하면 된다...

www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 알고리즘 종류 스위핑 사고 과정 시작점을 기준으로 오름차순 정렬합니다. 그리고 선을 그을 때 3가지의 경우가 나옵니다. 1. 이전 선에 모두 포함되는 경우 2. 이전 선에 일부만 포함되는 경우 3. 이전 선에 포함되지 않는 경우 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3..

www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 알고리즘 종류 백트레킹 사고 과정 처음과 끝의 구슬을 제외하고 하나씩 선택합니다. 선택한 구슬은 배열에서 제외합니다. 이 과정을 백트레킹으로 코드를 작성하면 됩니다. 배열은 vector로 하여 요소를 삭제하고 삽입하기 쉽게 할 수 있습니다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 3..

www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 알고리즘 종류 구현 BFS 사고 과정 지훈과 불의 움직임을 BFS로 표현해야 합니다. 그래서 2개의 큐를 이용해서 문제를 해결했습니다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 5..

www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 알고리즘 종류 완전탐색 사고 과정 DFS로 3개의 씨앗을 심을 위치를 선택합니다. 위치를 선택할 때에는 범위 밖으로 나가는지, 다른 꽃과 겹피는지 확인합니다. 이후, 3개를 심을 수 있으면 비용을 계산하여 최소 비용으로 갱신해 줍니다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ..