퀵 정렬 개념 퀵 정렬의 세부과정은 다음과 같다. pivot이라는 요소를 선택한 후, pivot을 기준으로 왼쪽에는 pivot보다 작은 요소들을 놓고 오른쪽에는 pivot보다 큰 요소들을 놓는다. 이후 순환호출을 이용하여 재귀적으로 왼쪽, 오른쪽으로 분류해둔 요소들에 대해 전과 같은 과정을 반복한다. 위의 그림은 오른쪽 요소들에 대해 순환호출한 모습이다. 분할이 불가능할 때까지 반복하다보면 최소한의 요소로 나누어지고 이후 순서대로 결합을 진행한다. 위의 그림에서 색이 칠해져있는 요소들을 순서대로 합치면 된다. 퀵 정렬은 분할 정복 알고리즘 중 하나이다. pivot으로 2개의 부분 배열을 생성하는 분할(Divide) 과정과 부분 배열을 재귀적으로 호출하는 정복(Conquer) 과정과 정렬된 부분 배열을 합..

선택 정렬 개념 max, min 정렬이라고도 불린다. 처음부터 끝 원소까지 훑으면서 최소나 최대를 찾아서 리스트의 처음이나 끝에 넣고 해당 원소를 제외한 다른 원소에 대해 다시 정렬을 시행하는 방법이다. 무작위로 정렬된 데이터의 처음부터 끝까지 탐색한 후, 가장 큰 수를 리스트의 마지막 요소와 교환한다. 그 후 마지막 원소를 제외한 채로 처음부터 끝까지 데이터를 탐색한 후, 가장 큰 수를 리스트의 마지막 요소와 교환한다. 구현 의사 코드는 다음과 같다. (min 정렬) for i=0 to n: a[i]부터 a[n-1]까지 차례로 비교하여 최소값이 있는 a[j]를 찾는다. a[i]와 a[j]를 바꾼다. (max 정렬) for i=0 to n: a[0]부터 a[n-i-1]까지 차례로 비교하여 최대값이 있는 ..

그래프 용도 용어 정리 기본 심화 구현 인접 행렬 인접 리스트 비교 연산 분류 방향성에 따른 분류 연결에 따른 분류 사이클에 따른 분류 특수한 그래프 탐색 도출된 문제들 관련 알고리즘 참고 그래프 그래프란 '노드'와 노드를 연결하는 '간선'으로 이루어진 자료구조이다. 지금까지의 살펴본 자료구조들(리스트, 스택, 큐 등)과는 달리 그래프는 비선형 자료구조 이다. 용도 그래프는 일상생활에서 연결되어있는 객체 간의 관계를 표현할 때 사용된다. 예로 지도나 지하철 노선도, 전기회로, 도로 등을 들 수 있다. 또한 컴퓨터 세부전공에서는 통신 네트워크 분야에서도 쓰이며, 논리회로를 설계하고 분석하는 데에도 사용된다. 최근에는 웹사이트의 링크 연결(Page Rank)이나 SNS 상의 친구관계를 표현하는 데에도 사용되..

첫번째 과제이다. 시간 복잡도가 f(n)인 알고리즘의 소요시간이 1 nanosecond == 10^(-9) second 이라고 할 때, 왼쪽에 표시된 시간 복잡도를 가지고 있는 알고리즘에 대해 위쪽의 시간 내에 알고리즘이 완료되려면 최대로 어떤 N까지 계산할 수 있을지 알아보자. 대표로 하나를 계산해보면 1sec는 10^(9) nanosec 이므로 n^2의 시간복잡도를 갖는 알고리즘에서 n^2 = 10^(9) 로 두고 풀면 1sec 만에 계산될 수 있는 n 값이 나온다. n 값은 모두 정수로 가정하였다.

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 16367 3904 2522 25.125% 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,..

7.2 문제 : 쿼드 트리 뒤집기 (문제 ID:QUADTREE, 난이도: 하) 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2^N*2^N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다. 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다. 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다. 모든 픽셀이 같은 색이 ..

6.8 문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중) 문제 4x4 격자 형태로 배치된 열여섯 개의 시계가 있습니다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있는데, 이 시계들이 모두 12시를 가리키도록 바꾸고 싶습니다. 시계의 시간을 조작하는 유일한 방법은 열 개의 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 세 개에서 많게는 다섯 개의 시계에 연결되어 있습니다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직입니다. (12시일때는 3시로, 3시=>6시, 6시 =>9시, 9시=>12시) 스위치들과 그들이 연결된 시계들의 목록이 주어지고 현재 가리키는 시간들이 주어졌을 때 모든 시계를 12시로 돌리기 위해 최소한 ..