거창한 시작

www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 알고리즘 종류 자료구조 분리집합 사고 과정 구현(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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #..

www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 알고리즘 종류 자료구조 스택 사고 과정 왜 스택으로 풀 수 있을까요? 문제에서 제시된 오큰수의 정의를 보면, Ai의 오른쪽에서 Ai보다 큰 수들 중에 가장 왼쪽에 있는 수 라고 합니다. A2의 오큰수는 A6의 7이 됩니다. 그런데 A2만 7이 오큰수이지는 않습니다. A3, A4, A5도 7이 오큰수 입니다. 이는 마치, 스택에 3,5,2,3,4가 있는 상태에서 7보다 작은 수는 모두 꺼내서 오큰수를 7이라고 명명하는 것과 같..

www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 알고리즘 종류 자료구조 부분 집합 사고 과정 문제에서 제시된 예시를 가지고 손으로 풀이를 해보고 있었습니다. 파티에서 참가하는 사람들을 하나로 묶고 그중에서 한 명이 진실을 알면 파티에 갈 수 없다고 생각했습니다. 즉, 부분 집합을 만들면 될 것 같았습니다. 1. 인접 리스트(party)로 파티에 들어갈 사람들을 담습니다. 그리고 for문으로 파티를 돌면서 부분 집합을 만듭니다. 2. 파티를 for문으로 돌면서 부모(대표..

www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 알고리즘 종류 자료구조 우선순위 큐 사고 과정 1. 최솟값과 최댓값을 저장할 우선순위 큐 2개가 필요합니다. 2. 최댓값을 저장한 우선순위 큐에서 최댓값을 제거하면, isVisited 배열에 해당 숫자를 제거했다고 표시합니다. 이렇게 표시하여 최솟값 우선순위 큐에서 해당 숫자를 처리할 수 있습니다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21..

www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 알고리즘 종류 자료구조 우선순위 큐 사고 과정 1. 강의실을 배정하기 위해서 시작 시간을 기준으로 오름차순 정렬을 합니다. 2. 수업 시간을 하나씩 가져옵니다. 현재 수업의 시작 시간이 이전 수업의 끝나는 시간보다 크다면 빈 강의실이므로 우선순위 큐(pq)에서 꺼냅니다. 꺼낸 강의실 번호를 저장합니다. 3. 빈 강의실이 있다면, 그 곳에 현재 수업을 배정합니다. 빈 강의실이 없다면, 강의실을 하나 추가합니다. 구현(C++) 1 2 3 4 5 6 7 8 9 1..

www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 알고리즘 종류 자료구조 스택 사고 과정 스택을 이용해서 풀 수 있습니다. 문제에서 제시된 예시를 손으로 풀어보면 나중에 나온 연산자가 알파벳 뒤에 먼저 붙는 것을 알 수 있습니다. 그리고 문자는 그대로 출력되는 것을 알 수 있습니다. 그래서 문자는 그대로 출력하고 연산자만 스택에 넣어서 해결하면 될 것 같습니다. 조건이 몇 가지 있습니다. 1. 괄호로 인해서 우선순위가 바뀔 수 있습니다. 그래서 괄호도..

www.acmicpc.net/problem/9081 9081번: 단어 맞추기 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알 www.acmicpc.net 알고리즘 종류 구현 사고 과정 next_permutation으로 해결하면 너무 쉽게 해결할 수 있다는 것을 알았습니다. next_permutation을 이용하면 순열을 쉽게 구할 수 있습니다. 이 문제의 경우 순열에서 2번째로 생성된 것을 출력하면 됩니다. 1번째는 자기 자신입니다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2..

www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 알고리즘 종류 구현 문자열 사고 과정 비트마스크를 사용하지 않고 구현하면 제출이 되었지만, 시간이 오래 걸렸습니다. 비트마스크를 사용하면 어떤 알파벳이 있는지 쉽게 알 수 있습니다. 1. 처음에는 모든 알파벳을 기억한다고 했으니 or 연산으로 모든 알파벳을 기억합니다. 2. 단어를 입력받으면, dict 배열에서 단어의 문자를 or 연산으로 기억합니다. 3. 쿼리르 입력 받으면, And와 or 연산을 이용해서..

www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 알고리즘 종류 완전탐색 사고 과정 읽을 수 있는 최대 단어의 개수를 찾아야 합니다. 시작 글자와 끝 글자를 제외하고 중간에 남는 글자들에서 중복을 제외해야 한다고 생각했습니다. 그리고 a~z중에서 k-5개를 선택해서 남은 글자들을 커버할 수 있는지 확인하면 될 것 같습니다. k가 5미만이면 무조건 0개의 단어를 읽을 수 있습니다. 1. 기본으로 선택된 글자들은 미리 선택되게 합니다. 그리고 DFS를 이용..

www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 알고리즘 종류 완전탐색 사고 과정 DFS로 풀려고하니 +과 같은 교차하는 것을 확인할 수 없었습니다. BFS로 하려고 하니 재방문 확인을 할 수 없었습니다. 그래서 25개의 공간에서 7개를 선택하여 확인하는 방법을 사용하기로 했습니다. 1. DFS를 이용해서 조합으로 7개의 위치를 선택합니다. 2. 7개의 위치를 골랐다면, 이다솜파가 4명이상인지 확인합니다. 3. BFS로 7개의 공간이 서로 붙어있는지 확인합니다...