선택 정렬은 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법 입니다. 선택 정렬은 구현 방법이 복잡하고, 시간 복잡도 또한 O(n²)으로 효율적이지 않아 많이 사용하지 않습니다. 정렬 과정 남은 정렬 부분에서 최솟값 또는 최댓값 탐색 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터 swap 가장 앞에 있는 데이터의 위치를 변경해 남은 정렬 부분의 범위 축소 남은 정렬 부분이 없을 때까지 반복 소스 코드 void selectionSort(int[] list) { int indexMin, temp; for (int i = 0; i < list.length - 1; i++) { indexMin = i; for (int j = i + 1; j < list.lengt..
데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방법입니다. 시간 복잡도는 O(n²)으로 다른 정렬 알고리즘 보다 속도가 느린 편입니다. 정렬 과정 비교 연산이 필요한 루프 범위를 설정 인접한 데이터 값을 비교 swap 조건에 부합하면 swap 루프 범위가 끝날 때까지 2~3번 반복 정렬 영역을 설정. 다음 루프에서는 이미 정렬된 영역을 제외 비교대상이 없을 때까지 1~5를 반복 소스 코드 void bubbleSort(int[] arr) { int temp = 0; for(int i = 0; i < arr.length - 1; i++) { for(int j= 1 ; j < arr.length-i; j++) { if(arr[j]
스택(Stack) 스택은 삽입과 삭제 연산이 후입선출(LIFO : Last In First Out)로 이루어지는 자료구조입니다. 후입 선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있습니다. 그림을 보듯 새 값이 스택에 들어가면 top이 새 값을 가리킵니다. 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 되어 있으며 결과적으로 가장 마지막에 넣었던 값이 나오게 됩니다. 용어 위치 top : 삽입과 삭제가 일어나는 위치 연산 push : top 위치에 새로운 데이터를 삽입하는 연산 pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산 스택은 깊이 우선 탐색(DFS : Depth First Search..
합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘입니다. 합 배열 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 합니다. 배열 A가 있을 때 합 배열 S는 다음과 같이 정의 합니다. S[i] = A[0] + A[1] + A[2] + ... + A[i] + A[i-1] // A[0] 부터 A[i]까지 합 Index 0 1 2 3 4 A 1 2 3 4 5 S 1 3 6 10 15 합 배열이 없이 A[i]부터 A[j]까지의 배열 합을 구하게 되면 최악의 경우 i = 0, j = n 이면 시간 복잡도는 O(N)입니다. 이런 경우 초기에 값을 입력할 때 합 배열을 함께 만들어 사용하면 O(1)시간으로 구할 수 있습니다. 합 배열을 만들 때는 S[i] = S[i -1] + A..
배열 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조이며 배열의 값은 인덱스를 통해 참조할 수 있습니다. Index 0 1 2 3 4 Value Value1 Value2 Value3 Value4 Value5 특징 인덱스를 사용하여 값에 바로 접근 가능 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하게되면 주변의 값을 이동하는 과정이 필요 배열의 크기는 선언할 때 지정할 수 있고 한 번 선언하면 크기를 늘리거나 줄일 수 없음 구조가 간단 리스트 값과 표인터를 묶은 노드를 포인터로 연결한 자료구조입니다. 특징 인덱스가 없기에 값에 접근하려면 Head 포인터부터 순서대로 접근해야함 → 접근속도가 느림 포인터로 연결되어 있으므로 데이터의 삽입과 삭제 연산 속도가 ..
시간 복잡도 시간복잡도는 문제를 해결하기 위한 연산 횟수를 말하고 일반적으로 수행시간은 1억번의 연산을 1초의 시간으로 간주하여 예측합니다. 시간 복잡도의 표기법은 아래와 같이 3가지 유형이 있습니다. 최상의 경우 : 빅-오메가 표기법 (Big-Ω Notation) : 최선일 때 평균의 경우 : 빅-세타 표기법 (Big-θ Notation) : 보통일 때 최악의 경우 : 빅-오 표기법 (Big-O Notation) : 최악일 때 1 ~ 10의 숫자가 무작위로 섞여있을 때 임의의 값을 하나 찾는 프로그램이 있다고 할 때 각 표기법의 시간 복잡도는 아래와 같습니다. 빅-오메가 표기법 (Big-Ω Notation) : 1 빅-세타 표기법 (Big-θ Notation) : 2 / N 빅-오 표기법 (Big-O ..
문제 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 문제이해 조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다. 이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다. 조규현의 좌표 (x1, y1)와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출..
문제 1021번: 회전하는 큐 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서..
문제 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net 문제이해 출발지의 좌표와 도착지의 좌표가 주어지며 n개의 행성의 좌표와 원의 반지름이 주어진다. 출발지에서 도착지까지 이동할 때 행성에 진입하고 이탈하게 되는데 최소한의 진입과 이탈을 하게 되는 경우의 수를 구해야 한다. 입력 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주어지며, 세..
문제 1673번: 치킨 쿠폰 강민이는 치킨 한 마리를 주문할 수 있는 치킨 쿠폰을 n장 가지고 있다. 이 치킨집에서는 치킨을 한 마리 주문할 때마다 도장을 하나씩 찍어 주는데, 도장을 k개 모으면 치킨 쿠폰 한 장으로 교환 www.acmicpc.net 문제이해 치킨을 한마리 주문할 수 있는 쿠폰이 n장이 있고, 치킨을 먹을때마다 도장을 찍어준다. 도장을 k개 모으면 다시 치킨 쿠폰 한 장을 얻을 수 있을 때 쿠폰을 이용하여 최대 몇 마리의 치킨을 먹을 수 있는지 구하는 문제이다 입력 여러 줄에 걸쳐서 자연수 n 과 k가 주어진다. n k 출력 각 입력마다 한 줄에 정답을 출력한다. 풀이 n개의 쿠폰에서 n개의 도장을 얻게되고 n/k 개의 쿠폰을 얻게 됩니다. 기존에 남은 도장 n%k개와 새로 얻게된 쿠폰..
