3냥 집사이면서 게임 개발자입니다.

구현은 사실 아주 쉬운 알고리즘입니다. 말 그대로 문제 그대로 구현을 하면 됩니다. 예를 들어서 배열을 회전하라, 스택에 넣어라 하면 말 그대로 rotate 함수를 사용하고 stack.push 등을 하면 되는 것 입니다. 다음과 같이 문자열을 선언하고 아래의 문제를 풀어보겠습니다. string faker = "tunatuna"; Q1. 앞에서부터 세 개의 문자열을 출력하라. Q2. 해당 문자열을 거꾸로 해서 출력하라. Q3. 해당 문자열 끝에 "mistake"이란 문자열을 추가하라. 라고 하면 다음과 같은 코드를 구축해야 합니다. #include using namespace std; string faker = "abcde"; int main() { // 3개 출력 cout

누적합이란 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것을 말합니다. 이는 앞에서부터 더하는 prefix sum과 뒤에서부터 더하는 suffix sum이 있지만 코딩테스트는 prefix sum만 나오지 prefix sum 만 공부해도 좋습니다. 누적합의 경우 0번 배열에 넣지 않고 1번 배열부터 담는 것이 구현하는 것이 쉽습니다. 누적합이란 누적해서 더해진 값들의 배열을 의미합니다. 1,2,3,4 라는 배열의 누적합은 1,3,6,10이란 배열이 됩니다. 이렇게 만들어놓으면 구간 쿼리에 대응하기가 쉽습니다. 예를 들어 0 번째 요소에서 3 번째 요소까지 다 더하라고 했을 때 누적합 배열 3 번째 요소를 이용하면 되기 때..

공간복잡도는 "입력크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양"을 가리킵니다. 이는 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함하여 배열이든 맵이든 셋이든 요소들을 담을 공간이면 모두 적용됩니다. 다음 코드에서 int형 배열 1000만 개 1개, 1004개 1개를 선언했습니다. 둘 다 포함해서 공간복잡도를 계산합니다. int a[10000000]; void f() { int b[1004]; } int main() { return 0; } 예를 들어 입력이 N이 들어오고 거기에 따라 N개 int형 요소를 담아야 할 공간이 필요하다면 4N바이트의 공간이 필요합니다. 이를 빅오표기법으로 나타내면 O(N)이 됩니다. 상수는 버립니다. ..

Q4. 다음 코드의 시간복잡도는? tip. 로그(log)는 지수 함수의 역함수이다. 어떤 수를 나타내기 위해 고정된 밑을 몇 번 곱하여야 하는지를 나타낸다고 볼 수있다. #include using namespace std; int N; void solve(int N) { int a = 0, i = N; while(i > 0) { a += i; i /= 2; } cout N; solve(N); return 0; } // 디버깅 작업했을 때 // 입력 32 // 횟수 6 // 입력 8 // 횟수 4 위 코드를 보면 solve 함수 내에 while 문을 사용한 알고리즘이 몇 번 반복하는지가 시간복잡도를 결정하는 핵심 알고리즘이라는 걸 알 수 있습니다. cnt 를 선언하고 디버깅했을 때 (logn)+1 임을 알..

복잡도는 시간복잡도와 공간복잡도로 나뉘어지는데 먼저 시간 복잡도에 대해 알아봅시다. 시간복잡도란 입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요 로직의 반복 횟수를 중점으로 측정됩니다. 시간? 시간이라는 것은 컴퓨터 사양 등 여러가지 요소에 영향을 받곤 합니다. 그래서 시간복잡도를 설명할 때는 시간이 아니라 어떤 알고맂므이 주어진 입력 크기를 기반으로 어떤 로직이 몇번 반복했는가를 중점으로 설명합니다. 예를 들어 다음 코드는 어떤 시간복잡도를 가질까요? for(int i = 0; i nlog..

삽입 정렬이란 자료 배열의 모든 요소를 앞에서부터 비교하고자 하는 타겟값(tmp)과 정렬된 값을 비교해 자신의 위치를 찾아 삽입하면서 정렬해나가는 알고리즘입니다. 매번 비교할 때마다 앞 부분에 해당하는 범위 모두 타겟값과 비교해 해당 원소를 삽입할 수 있는 위치를 찾아 배열 위치에 넣습니다. 정렬 프로세스 1. 2번째 원소부터 시작한다. 2. 이전 위치에 있는 원소들과 타겟이 되는 원소들을 비교한다. (타겟 원소는 임시 변수에 넣는다.) 3. 타겟 원소가 이전 위치에 있던 원소보다 작다면 위치를 바꾼다. 4. 이전 데이터도 차례대로 비교하며 정렬해나간다. 5. 이 매커니즘으로 반복해 정렬한다. 삽입 정렬의 특징 구현이 간단하다. 배열이 길어질수록 효율이 떨어진다. 선택 정렬이나 버블 정렬과 같은 O(n^..

버블 정렬(Bubble Sort)란 맨 왼쪽 원소부터 바로 이웃한 오른쪽 원소와 비교해가며 큰 수가 오른쪽으로 가도록 교환하는 정렬 방식입니다. 거품 정렬이라고도 하며 두 인접한 원소를 비교하는 것이 핵심입니다. 정렬 프로세스 1. 인접한 두 수의 대소를 비교한다. 2. 내림차순, 오름차순에 따라 두 수의 자리를 바꾼다. 3. 나머지 요소들도 동일한 매커니즘으로 정렬한다. 구현이 쉬워서 자주 사용된다. 하지만 조건이 맞는 상황이 주어질 때 매번 정렬하기 때문에 실행 속도를 느리게 할 수 있다는 단점이 있습니다. 예시 다섯 개의 숫자를 정렬한다고 예시를 들겠습니다. i 가 0 일 때 이중 for문에서 n-1번 비교, i 가 1일 때 이중 for문에서 n-2번 비교, ... i 가 3일 때 이중 for문에서..

선택 정렬(Selection Sort)이란 제자리 정렬 알고리즘 중 하나로 정렬되지 않은 데이터들 중에서 가장 작은 값을 추출해 가장 맨 앞으로 정렬해나가는 알고리즘입니다. 1. 배열 중 최소값을 찾습니다. 2. 최소값을 맨 앞으로 정렬합니다. (Swap) 3. 나머지 값들도 같은 매커니즘으로 정렬합니다. 알고리즘이 단순하고 사용할 수 있는 메모리가 제한적인 경우, 사용에 이점이 있으며, 구현이 간단하지만 비효율적인 알고리즘입니다. 선택 정렬 시간 복잡도 기준값과 비교값들 중 최소값을 찾기 위해 이중 for문이 필요합니다. - 첫 번째 회전 비교 횟수 : 1부터 (n-1) = n-1 - 두 번째 회전 비교 횟수 : 2부터 (n-1) = n-2 ... -> 최소값 찾기 : n-1, n-2, ... 2, 1..