거창한 시작

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 ..

www.acmicpc.net/problem/2422 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 www.acmicpc.net 알고리즘 종류 구현 완전탐색 사고 과정 순서가 있고 중복없이 아이스크림을 선택합니다. 그리고 안 좋은 조합을 고르지 말아야 합니다. 저는 DFS와 백트레킹을 이용해서 아이스크림을 선택하기로 했습니다. 그리고 안 좋은 조합을 제외하는 경우를 배열을 이용해서 처리했습니다. 이 방법 말고도 2차원 배열을 이용해서 3중 for문으로 완전탐색하는 방법도 있습니다. 2차원 배열에는 좋..

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개의 줄에 지도 www.acmicpc.net 알고리즘 종류 구현 사고 과정 주사위 면의 상태(state)와 값(val)을 나타낼 배열을 각각 생성합니다. 1. 명령어에 따라 주사위의 위치를 바꿔줍니다. 만약에 범위 밖으로 나가면 continue로 무시합니다. 2. 명령어에 따라 각 주사위 면의 상태를 바꿔줍니다. 3. 바닥과 맞닿은 지도의 값이 0인지 아닌지에 따라 처리합니다. 4. 주사위..

www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 알고리즘 종류 구현 사고 과정 뱀의 몸을 저장하기 위해서 deque으로 배열을 만들어 줍니다. 뱀의 움직임을 저장할 배열 rotate를 만들어 줍니다. 1. 뱀이 움직일 시간이면 방향을 바꿔줍니다. 2. 머리를 움직여 봅니다. 그리고 아래 조건으로 확인합니다. 2-1. 끝? 범위 밖 또는 자신의 몸과 부딪혔는지 확인합니다. 2-2. 사과? 사과가 있으면, 몸을 늘려줍니다. 사과가 없으면 꼬리 부분을 비웁니다. 구현(C..

www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 알고리즘 종류 MST 크루스칼 사고 과정 입력된 모든 랜선의 길이를 저장합니다. 그리고 크루스칼 알고리즘으로 MST를 만들면 연결된 길이를 빼줍니다. 그리고 모든 컴퓨터가 연결되었는지 확인해야 합니다. 모든 컴퓨터가 연결되어 있는지 확인할 수 있는 방법은 무엇일까요? A노드와 B노드가 연결되어 있는지는 parents 배열에 저장해두었습니다. 그렇다면, 이 배열을 for문으로 순환하면서 부모가 모두 동일하다..

www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 알고리즘 종류 MST 크루스칼 사고 과정 '논 사이 연결 VS 논에 우물파기'를 비교해야 하는 문제입니다. 생각해보면, 트리가 여러 개 나올 수 있다는 것을 알 수 있습니다. 이럴 경우, 가상의 노드를 생성하여 해결할 수 있습니다. 즉, 가상의 노드 0을 만들고 0과 연결된 간선을 우물을 파는 비용으로 하면 됩니다. 아래 그림으로 설명해드리겠습니다. 우선 초기 상태입니다. 붉은색은..