문제 1138번: 한 줄로 서기 문제 설명 N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다. 어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다. 사람들은 자기보다 큰 사람이 왼쪽에 몇 …

문제 1431번: 시리얼 번호 문제 설명 다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다. 모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다. 시리얼번호 A가 시리얼번호 B…

문제 1931번: 회의실 배정 문제 설명 한 개의 회의실이 있는데 이를 사용하고자 하는 N 개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I 에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 …

문제 1946번: 신입 사원 문제 설명 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 …

문제 연습문제 - 광물 캐기 문제 설명 마인은 곡괭이로 광산에서 광석을 캐려고 합니다. 마인은 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이를 각각 0개에서 5개까지 가지고 있으며, 곡괭이로 광물을 캘 때는 피로도가 소모됩니다. 각 곡괭이로 광물을 캘 때의 피로도는 아래 표와 같습니다. 예를 들어, 철 곡괭이는 다이아몬드를 캘 때 피로도 5가 소모되며, 철…

문제 정렬 - K번째 수 문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 1, 5, 2, 6, 3, 7, 4 , i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 5, 2, 6, 3 입니다. 1에서 나온 배열을 정렬하면 2, …

병합 정렬(Merge Sort)이란? 병합 정렬(Merge Sort) 은 분할 정복 기법(Divide and Conquer) 과 재귀 용법 을 활용한 정렬 알고리즘이다. 병합 정렬은 정렬할 원소 목록을 원소가 하나 밖에 남지 않을 때까지 절반으로 잘라 비슷한 크기의 두 부분으로 계속 나눈다. 정렬할 때는 각 절반의 가장 작은 요소를 비교하여 수행된다.…

퀵 정렬이란? 퀵 정렬은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 알고리즘이다. 퀵 정렬은 병합 정렬과 비슷하게 전체 데이터 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵 정렬하는 분할 정복법(Divide-and-Conquer) 을 사용한다. 그러나 퀵 정렬은 병합 정렬과 다르게 데이터 리스트를 비균등하게 분할한다. 퀵 …

삽입 정렬(Insertion Sort)이란? 삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉬운 알고리즘이다. 삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬(Insertion Sort) 이라고 한다. 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때 훨씬 효율적이다. 선택 정렬은 현재 …

선택 정렬(Selection Sort)이란? 선택 정렬의 원리 정렬되지 않은 원소 중 가장 작은 원소를 찾아 정렬된 요소의 끝에 배치한다. 즉, 배열의 요소 중에서 최소값을 발견한 다음, 이 최소값을 배열의 첫번째 요소와 교환환다. 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두번째 요소와 교환한다. 이 과정을 배열이 정렬될 …