마쏘's 개발 성장기

1. selection sort 선택 정렬

: 가장 작은 것을 선택해 차례대로 맨 앞의 데이터와 바꾸는 정렬 방법

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1,n):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        #print("sorting ... ",arr)
    return arr

''' output
sorting ...  [0, 5, 9, 7, 3, 1, 6, 2, 4, 8]
sorting ...  [0, 1, 9, 7, 3, 5, 6, 2, 4, 8]
sorting ...  [0, 1, 2, 7, 3, 5, 6, 9, 4, 8]
sorting ...  [0, 1, 2, 3, 7, 5, 6, 9, 4, 8]
sorting ...  [0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
sorting ...  [0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
sorting ...  [0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
sorting ...  [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
sorting ...  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sorting ...  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
'''

2. Insertion sort 삽입 정렬

: 특정한 값을 적절한 위치에 삽입하는 정렬 방법(그 위치 앞까지는 이미 정렬되어 있음)

def insertion_sort(arr):
    n = len(arr)
    for i in range(1,n):
        for j in range(i-1, -1, -1):
            if arr[j] > arr[j+1]: # 해당 데이터의 위치 자동 갱신 가능
                arr[j], arr[j+1] = arr[j+1], arr[j]
            else: 
                break
        #print("sorting ... ",arr)          
    return arr 

''' output
sorting ...  [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
sorting ...  [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
sorting ...  [0, 5, 7, 9, 3, 1, 6, 2, 4, 8]
sorting ...  [0, 3, 5, 7, 9, 1, 6, 2, 4, 8]
sorting ...  [0, 1, 3, 5, 7, 9, 6, 2, 4, 8]
sorting ...  [0, 1, 3, 5, 6, 7, 9, 2, 4, 8]
sorting ...  [0, 1, 2, 3, 5, 6, 7, 9, 4, 8]
sorting ...  [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
sorting ...  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
'''

나의 실수> 

j for문에서 j와 i를 사용하여 값을 비교했는데 이때 i로 인해 업데이트되는 값을 따라가지 못했는데 j+1을 통해 자동으로 값이 업데이트 되는 것을 알 수 있었다. 

3. quick sort 퀵 정렬

: pivot을 사용하여 왼쪽부터 pivot보다 큰 데이터를 찾고, 오른쪽부터 pivot보다 작은 데이터를 찾아 큰 데이터와 작은 데이터를 찾아 위치를 서로 교환하는 정렬 방법

: 작은 데이터와 큰 데이터를 찾았을 때 index가 엇갈린 경우에는 pivot과 찾은 작은 데이터(right index)와 교체한다

def quick_sort(pivot, end, arr):
    if pivot >= end:
        return    
    
    left, right = pivot + 1, end
    
    while left <= right:
        while left <= end and arr[pivot] >= arr[left]:
            left += 1
        while right > pivot and arr[pivot] <= arr[right]:
            right -= 1

        if left > right: # 두 값이 엇갈린 경우 작은 데이터(right)와 pivot 교체
            arr[pivot], arr[right] = arr[right], arr[pivot]
            #print("sorting ... "arr)
        else:
            arr[left], arr[right] = arr[right], arr[left]

    # 현재는 arr[right]에 pivot 값이 존재, pivot은 배열의 앞 부분을 의미
    quick_sort(pivot, right - 1, arr) 
    quick_sort(right + 1, end, arr)
    return arr

''' pivot이 바뀌는 과정
sorting ... [0, 1, 2, 4, 3, 5, 6, 9, 7, 8]
sorting ... [0, 1, 2, 4, 3, 5, 6, 9, 7, 8]
sorting ... [0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
sorting ... [0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
sorting ... [0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
sorting ... [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sorting ... [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
'''

나의 실수> while left <= right:을 생각하지 못했다.

또 배열을 slicing해서 넘기는 바보 같은 생각을 했다... merge할 거 아니면 start와 end idx로 재귀에서 arr을 수정하면 되는데, idx잘 계산해놓고 arr[:right-1], arr[right+1:] 이런 걸 넘기다니 정말 내가 왜 이렇게 짰었는지 도통 모를 일이다.

4. counting sort 계수 정렬

: 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담아 정렬하는 방법

def counting_sort(arr):
    count_arr = [0 for _ in range(max(arr)+1)]

    for val in arr:
        count_arr[val] += 1
    
    arr = []
    for i in range(len(count_arr)):
        while count_arr[i]:
            arr.append(i)
            count_arr[i] -= 1
            
    return arr

main 함수

def main():
    unsorted = [5,7,9,0,3,1,6,2,4,8]
    print("selection_sort",selection_sort(unsorted))
    
    unsorted = [7,5,9,0,3,1,6,2,4,8]
    print("insertion_sort", insertion_sort(unsorted))

    unsorted = [7,5,9,0,3,1,6,2,4,8]
    print("quick_sort", quick_sort(0, len(unsorted)-1, unsorted))
    
    unsorted = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
    print("counting_sort", counting_sort(unsorted))

main()

''' output
selection_sort [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
insertion_sort [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
quick_sort [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
counting_sort [0, 0, 1, 1, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9]
'''

해당 문제와 모범답안은 아래 포스트를 확인해주세요
masso.tistory.com/61?category=891816

문제 및 code

problem1. 거스름돈

def problem1(): # 거스름돈
  # 입력: 1260, 답:6 -> 500*2 + 100*2 + 50*1 + 10*1 
  coins = [500, 100, 50, 10]
  n = int(input("problem1: "))
  cnt = 0

  for coin in coins:
    cnt += n // coin
    n -= coin * (n // coin) # n %= coin

  print(cnt) 

모범 답안과의 비교>
- 파이썬에서 //: 몫을 반환하는 연산자. %: 나머지를 반환하는 연산자임을 상기시키자

- n을 남은 금액으로 갱신할 때 coin 개수와 coin 가격을 곱해 빼는 방법을 사용했는데, 나머지 연산자를 사용해

n %= coin으로 작성했다면 더 간결하고 빠른 코드였을 것이다.

problem2. 큰 수의 법칙

def problem2(): # 큰 수의 법칙
  # 5 8 3
  # 2 4 5 4 6
  # 답: 46 -> 6*3 + 5*1 + 6*3 + 5*1 
  # 5 8 5
  # 2 4 5 4 6
  # 답:47 -> 6*5 + 5*1 + 6*2
  n, m, k = map(int,input("problem2: ").split())
  arr = list(map(int,input().split()))

  arr.sort(reverse=True)
  sum = 0
  while m > 0:
    if m > k:
      sum += arr[0]*k
      m -= k
    else:
      sum += arr[0]*m
      m = 0

    if m >= 1:
      sum += arr[1]
      m -=1

  print(sum)

모범 답안과의 비교>

- list를 어떻게 정렬하냐에 따라 다를 수 있는데, 모범 답안에서는 오름차순으로 정렬하여 [n-1],[n-2] 값으로 제일 큰 값과 그 다음으로 큰 값을 구하였다.

- 반복되는 수열의 길이는 (K+1)이고 M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다.
  여기에 (K+1)*M은 first가 반복하는 횟수가 되고, M이 (K+1)로 나누어 떨어지지 않는 것을 고려했을 때,
  '가장 큰 수가 더해지는 횟수는 int(M/(K+1)) * K + M%(K+1)'

  따라서, 더한 값의 결과는 first * 구한 횟수 + second * (m - 구한 횟수)가 된다.

problem3. 숫자 카드 게임

  # 3 3
  # 3 1 2
  # 4 1 4
  # 2 2 2
  # 답: 2
  # 2 4
  # 7 3 1 8
  # 3 3 3 4
  # 답: 3
  n, m = map(int, input("problem3: ").split())
  cards = [list(map(int, input().split())) for _ in range(n)]
  # [[3, 1, 2], [4, 1, 4], [2, 2, 2]]
  # [[7, 3, 1, 8], [3, 3, 3, 4]]

  for i in range(n):
    cards[i].sort()
  cards.sort(reverse=True)
  print(cards[0][0])

모범 답안과의 비교>

- 행을 입력받을 때마다 해당 행의 min값을 찾고, 찾은 min값을 이전 min값과 비교하면서 더 큰 min값으로 result 변수를 갱신하는데 나는 그냥 sort를 박아버렸다지...?!

problem4. 1이 될 때까지

def problem4():  # 1이 될 때까지
  # 25 5
  # 답:5
  n, k = map(int, input("problem4: ").split())
  count = n % k + n // k
  print(count)

모범 답안과의 비교>

- n을 k로 나누고, 1을 빼고 나서 또 다시 k로 나눌 수 있는 경우가 생길 수 있는데, 빨리 풀고 싶은 마음에 그 경우를 고려하지 못해서 정말 간단한 코드가 나왔다...!- k로 나눌 수 있는 만큼 나누고
  1) n<k 라면 그만큼 1을 빼면 되기 때문에 break를 한다.   2) n>=k 라면 한 번 k를 더 나누고 이에 맞게 갱신하고 반복한다!

main 함수

def __main__():
  problem1()
  problem2()
  problem3()
  problem4()

__main__()

Ch6. 정렬

1. 기준에 따라 데이터를 정렬

  1-1. 정렬 알고리즘 개요

         - '정렬'
           : 데이터를 특정한 기준(오름차순 또는 내림차순)에 따라서 순서대로 나열하는 것이다.
           : 정렬 알고리즘으로 데이터를 정렬하고 나면 이진 탐색이 가능해진다.

  1-2. 선택 정렬

         - 매번 '가장 작은 것'을 '선택'한다는 의미에서 선택 정렬이다.

         - 다른 알고리즘들보다 비효율적이지만 가장 작은 데이터를 찾는 경우가 많으므로 소스 코드에 익숙해질 필요가 있다.

         - 소스 코드

arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(arr)):
  min_idx = i
  for j in range(i+1, len(arr)):
    if arr[min_idx] > arr[j]:
      min_idx = j
  arr[i], arr[min_idx] = arr[min_idx], arr[i] #swap

print(arr)

#include <stdio.h>
using namespace std;

int n = 10;
int arr[10] = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 };

void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
	return;
}

void select_sort(int* array) {
	for (int i = 0; i < n; i++) {
		int min_idx = i;
		for (int j = i + 1; j < n; j++) {
			if (array[min_idx] > array[j])		min_idx = j;
		}
		swap(&array[min_idx], &array[i]);
	}
}

int main() { // 선택 정렬
	select_sort(arr);
	for (int i = 0; i < n; i++) printf("%d ", arr[i]);
	printf("\n");
	return 0;
}

         - 시간 복잡도
           :  선택 정렬은 N-1번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해 비교 연산
              을 수행해야한다. // N + (N - 1) + (N - 2) + .... + 2

              따라서 시간 복잡도 O(N^2)가 걸린다.

  1-3. 삽입 정렬

         - 특정한 데이터를 적절한 위치에 '삽입'한다는 의미이다. 적절한 위치에 삽입되기 전에 그 앞까지의 데이터는 이미 정렬되
           어 있다고 가정한다.

         - 소스 코드

arr = [7,5,9,0,3,1,6,2,4,8]

for i in range(1,len(arr)):
  for j in range(i, 0, -1):
    if arr[j] < arr[j-1]:
      arr[j], arr[j-1] = arr[j-1], arr[j];
    else:
      break;

print(arr)

#include <stdio.h>
using namespace std;

int n = 10;
int arr[10] = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 };

void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
	return;
}

void insert_sort(int* array) {
	for (int i = 1; i < n; i++) {
		for (int j = i; j > 0; j--) {
			if (array[j - 1] > array[j])	swap(&array[j], &array[j - 1]);
			else break;
		}
	}
}

int main() { // 삽입 정렬
	insert_sort(arr);
	for (int i = 0; i < n; i++) printf("%d ", arr[i]);
	printf("\n");
	return 0;
}

         - 시간 복잡도

           : 선택 정렬과 마찬가지로 이중 for문이 사용되었기 때문에 O(N^2)의 시간 복잡도를 가진다. 그렇지만, 현재 리스트의
             데이터가 거의 정렬되어 있는 상태라면 best의 경우 O(N)의 시간 복잡도를 가진다.

             거의 정렬되어 있는 상태의 데이터가 들어온다면 다른 정렬 알고리즘들보다 삽입 정렬을 이용하는 것이 정답 확률을
             높일 수 있다.

  1-4. 퀵 정렬

         - 지금까지 배운 알고리즘들 중에 가장 많이 사용되는 알고리즘들이다. 비슷한 속도를 가지는 병합 정렬 알고리즘이 있지
            만 이 책에서는 나오지 않는다. 

         - 기준(pivot)을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

         - pivot을 설정하고 리스트를 분할하는 방법에 따라 여러 가지 방식으로 구분하는데 여기서는 가장 대표적인 분할 방식인
           호어 방식(hoare partition)을 기준으로 퀵 정렬을 설명한다.

           '호어 방식(hoare partition)'
            1) 리스트의 첫번째 데이터를 pivot으로 설정하고 왼쪽에서부터 pivot보다 큰 수를, 오른쪽에서부터 pivot보다 작은
                수를 작은 데이터를 찾아 찾은 두 데이터의 위치를 서로 교환해준다.

            2) 교환하여 pivot의 왼쪽에는 pivot보다 작은 데이터가 위치하고, pivot의 오른쪽에 있는 피벗보다 큰 데이터가 위치

                하게 되면(=partition or divide가 다 되면) 왼쪽 리스트와 오른쪽 리스트에서 각각 위 과정을 또 진행한다.

            3) 분할(divide) or 파티션(partition)된 현재 리스트의 원소가 1개일 때 퀵 정렬은 끝난다.

         - 소스 코드

arr = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(arr, start, end):
  if start >= end: # 원소가 하나일 때
    return
  pivot = start
  left = pivot + 1
  right = end

  while left <= right:
    # pivot보다 큰 것을 찾을 때까지 idx 증가
    while left <= end and arr[left] <= arr[pivot]:
      left += 1
    # pivot보다 작은 것을 찾을 때까지 idx 감소
    while right > start and arr[right] >= arr[pivot]:
      right -= 1
    
    if left > right: # 5 8 7 6 4
      # 엇갈렸다면 작은 arr[right]와 arr[pivot]를 교체
      arr[right], arr[pivot] = arr[pivot], arr[right]
    else:
      # 엇갈리지 않았을 때 작은 데이터와 큰 데이터 교체
      arr[left], arr[right] = arr[right], arr[left]

  quick_sort(arr, start, right - 1)
  quick_sort(arr, right + 1, end)

quick_sort(arr, 0, len(arr)-1)
print(arr)

파이썬의 장점을 살린 퀵 정렬

arr = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(arr):
  if len(arr) <= 1: return arr

  pivot = arr[0]
  tail = arr[1:] # pivot을 제외한 list
  
  left_side = [x for x in tail if x <= pivot]
  right_side = [x for x in tail if x > pivot]

  return quick_sort(left_side) + [pivot] + quick_sort(right_side)

sorted_arr = quick_sort(arr)
print(sorted_arr)

#include <stdio.h>
using namespace std;

int n = 10;
int arr[10] = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 };

void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
	return;
}

void quick_sort(int* array, int start, int end) {
	if(start >= end) return;
	int pivot = start;
	int left = start + 1;
	int right = end;

	while(left <= right){
		// pivot보다 큰 데이터를 찾을 때까지 반복
		while(left <= end && array[left] <= array[pivot]) left++;
		// pivot보다 작은 데이터를 찾을 때까지 반복
		while(right > start && array[pivot] <= array[right]) right--;
		
		if(left > right) swap(&array[pivot], &array[right]);
		else swap(&array[left], &array[right]);
	}

	quick_sort(arr, start, right - 1);
	quick_sort(arr, right + 1, end);
}

int main() { // 퀵 정렬
	quick_sort(arr, 0, n-1);
	for (int i = 0; i < n; i++) printf("%d ", arr[i]);
	printf("\n");
	return 0;
}

         - 시간 복잡도

           : 퀵 정렬은 평균적으로 O(NlogN)의 시간 복잡도를 가진다. (증명이 필요한데 코딩테스트와 관련 없으므로 넘어간다)
             평균 시간 복잡도는O(NlogN)이지만, 최악의 경우(이미 데이터가 정렬되어 있는 경우) O(N^2)이다.

             실제로 정렬 라이브러리에는 피벗값을 설정하는 추가적인 로직이 있기에 최악의 경우에도 O(NlogN)를 보장한다.

  1-5. 계수 정렬

         - 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 
           '데이터의 크기 범위가 제한되어 양의 정수 형태로 표현할 수 있을 때'만 사용할 수 있다.

            ex) 0 이상 100 이하인 성적 데이터

         - 계수 정렬보다 조금 느리지만 처리할 수 있는 정수의 크기는 더 큰 기수 정렬(radix sort)가 있다.

           계수 정렬과 기수 정렬은 현존하는 알고리즘 중에 제일 빠르다.

         - 소스 코드

arr = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]

count = [0] * (max(arr)+1)

for i in range(len(arr)):
  count[arr[i]] += 1

for i in range(len(count)):
  for j in range(count[i]):
    print(i, end=' ') # 띄어쓰기를 구분으로 설정

#include <stdio.h>
#define MAX_VALUE 9

using namespace std;

int n = 15;
int arr[15] = { 7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2 };
int arrCnt[MAX_VALUE + 1];

int main() { // 계수 정렬
	for (int i = 0; i < n; i++) {
		arrCnt[arr[i]] += 1;
	}
	for (int i = 0; i <= MAX_VALUE; i++) {
		for (int j = 0; j < arrCnt[i]; j++) {
			printf("%d ", i);
		}
	}
	printf("\n");
	return 0;
}

         - 시간 복잡도

           : 모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때,
             계수 정렬의 시간 복잡도는 O(N+K)이다.
             (앞에서부터 데이터를 확인하면서 적절한 인덱스의 값을 증가시킬 뿐만 아니라, 추후 인덱스에 해당하는 값들을
              확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문)

         - 공간 복잡도

           : 리스트의 크기가 적절하고, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다. 왜냐하면 데이터가 0과 999,999
             단 두 개가 존재한다고 가정했을 때 리스트이 크기가 100만 개가 되도록 설정해야하기 때문이다.

           : 일반적인 코딩 테스트의 시스템 환경에서는 메모리 공간상의 제약과 입출력 시간 문제로 입력되는 데이터의 개수를     
             1000만개 이상으로 설정하기 어렵기 때문에 1000만 개 미만으로 출제될 것이다.

  1-6. 파이썬의 정렬 라이브러리

         - 파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. 퀵 정렬과 방식이 비슷한 병합 정렬로 만들어졌는데,

           병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다.

         - sorted() 함수는 list나 dictionary 자료형 등을 입력받아 정렬된 결과를 리스트 자료형으로 반환한다.

         - 소스 코드

arr = [7,5,9,0,3,1,6,2,4,8]

# sorted() 함수 사용하기
result = sorted(arr)
print(result)

# 리스트 객체의 내장 함수 sort() 사용하기
arr.sort()
print(arr)

# sorted()나 sort()를 이용할 때
# key를 사용하여 정렬 할 수 있다
arr = [('바나나',2), ('사과',5),('당근',3)]

def setting(data):
  return data[1]

result = sorted(arr, key=setting)
print(result)

#include <stdio.h>
#include <algorithm>

using namespace std;

int n = 10;
int arr[10] = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 };

int main() { 
	sort(arr, arr + n);
	for (int i = 0; i < n; i++) printf("%d ", arr[i]);
	printf("\n");
	return 0;
}

         - 시간 복잡도

           : 정확하게 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용하기에 항상 최악의

             경우에도 O(NlogN)을 보장한다.

           : 따라서 문제를 풀 때 별도의 요구가 없다면 단순히 정렬해야하는 상황에는 기본 정렬 라이브러리를 사용하고,
             데이터 범위가 한정되어 있으며 더 빠르게 동작해야할 때는 계수 정렬을 사용하자.

  1-7. 코딩 테스트에서 정렬 알고리즘이 사용되는 경우
        1) 정렬 라이브러리로 풀 수 있는 문제
           : 단순히 정렬 기법을 알고 있는지 물어보는 문제

        2) 정렬 알고리즘의 원리에 대해서 물어보는 문제

           : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 풀 수 있는 문제

        3) 더 빠른 정렬이 필요한 문제

           : 퀵 정렬 기반의 정렬 기법으로 문제를 풀 수 없으며 계수 정렬 등 다른 정렬 알고리즘을 이용하거나 문제에서 기존에
             알려진 알고리즘의 구조적인 개선을 고쳐야 풀 수 있는 문제

2. 위에서 아래로

   - 문제

   - 문제 해결

     : 수의 개수가 500개 이하로 매우 적고, 모든 수는 1 이상 100,000 이하의 자연수로 어떤 정렬 알고리즘을 사용해도

       문제를 해결할 수 있다. 여기서는 가장 편한 파이썬의 기본 라이브러리를 이용하는 것이 효과적이다.

   - 소스 코드

n = int(input())

arr = []
for i in range(n):
  arr.append(int(input()))

arr = sorted(arr, reverse=True)

for i in arr:
  print(i,end=' ')

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

int N = 0;
vector<int> v;

bool compare(int a, int b){
	return a > b;
}

int main() { 
	scanf("%d", &N);
	for (int i = 0; i < N; i++){
		int x = 0;
		scanf("%d", &x);
		v.push_back(x);
	}
	sort(v.begin(), v.end(), compare);

	for (int i = 0; i < N; i++) printf("%d ", v[i]);
	printf("\n");
	return 0;
}

3. 성적이 낮은 순서로 학생 출력하기

   - 문제

   - 문제 해결

    : 학생의 정보가 최대 100,000개까지 입력될 수 있으므로 최악의 경우 O(NlogN)을 보장하는 알고리즘을 이용하거나
      O(N)을 보장하는 계수 정렬을 이용하면 된다.

    : 그뿐만 아니라 입력되는 데이터는 학생의 이름과 정수지만 출력할 때는 학생의 이름만 출력하면 되기 때문에
      학생 정보(점수, 이름)으로 묶은 뒤에 점수를 기준으로 수행해야 한다. 따라서 이런 경우에도 -> 파이썬 기본 정렬 library

   - 소스 코드

n = int(input())

list_info = []
for i in range(n):
  data = input().split()
  list_info.append((data[0], int(data[1])))
  
def setting(student):
  return student[1]
list_info = sorted(list_info, key=setting)

for student in list_info:
  print(student[0], end=' ')

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

class Student {
	public:
		string name;
		int score;
		Student(string name, int score) {
			this->name = name;
			this->score = score;
		}
		bool operator < (Student &other) {
			return this->score < other.score;
		}
};

int N;
vector<Student> v;

int main() { 
	cin >> N;
	// scanf로 문자열을 받으려면 char[30] str 이런 형식이어야 한다.
	for (int i = 0; i < N; i++){
		string name; 
		int score;
		cin >> name >> score;
		v.push_back(Student(name, score));
	}
	sort(v.begin(), v.end());

	for (int i = 0; i < N; i++) {
		cout << v[i].name << " ";
	}
	cout << endl;
	return 0;
}

4. 두 배열의 원소 교체

   - 문제

   - 문제 해결

    : 기본 아이디어는 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체를 하는 것이다.

      (단, 배열 A에서 가장 작은 원소가 배열 B에 있는 가장 큰 원소보다 작을 때에만 교체를 해야한다)

    : 배열 A의 원소를 오름차순으로 정렬하고, 배열 B의 원소를 내림차순으로 설정한다. 두 배열의 원소를 가장 첫 번째 인덱스
      부터 차례대로 비교하면서 A의 원소가 B의 원소보다 작을 때 교체를 수행한다.

    : 두 배열의 원소가 100,000개 까지 입력될 수 있으므로 O(NlogN)을 보장하는 정렬 알고리즘을 이용해야 한다.

   - 소스 코드

n, k = map(int,input().split())
arrA = list(map(int,input().split()))
arrB = list(map(int,input().split()))

arrA.sort()
arrB.sort(reverse=True)

for i in range(k):
  if arrA[i] < arrB[i]:
    arrA[i], arrB[i] = arrB[i], arrA[i]
  else: 
    break;

print(sum(arrA))

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N, K;
vector<int> a, b;

bool compare(int x, int y) {
	return x > y;
}

int main() { 
	cin >> N >> K;
    
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        a.push_back(x);
    }
    
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        b.push_back(x);
    }
   
    sort(a.begin(), a.end()); // 배열 A는 오름차순 정렬 수행
    sort(b.begin(), b.end(), compare); // 배열 B는 내림차순 정렬 수행

    for (int i = 0; i < K; i++) {
        if (a[i] < b[i]) swap(a[i], b[i]);
        else break;
    }
    
    long long result = 0;
    for (int i = 0; i < N; i++) {
        result += a[i];
    }
    cout << result << endl;
	return 0;
}

Ch5. DFS/BFS

1. 꼭 필요한 자료구조 기초

    - '탐색'
      : 많은 양의 데이터 중 원하는 데이터를 찾는 과정으로 대표적인 알고리즘으로 DFS, BFS가 있다.

    - '자료구조'

      : 데이터를 표현하고 관리하고 처리하기 위한 구조

        - 오버플로(overflow) : 특정한 자료구조에 수용할 수 있는 데이터가 가득 찬 상태에서 삽입 연산을 수행할 때 발생

        - 언더플로(underflow) : 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할 깨 발생

    1-1. 스택

          - 선입후출 FILO or 후입선출 LIFO 구조

    1-2. 큐

          - FIFO 구조

          - deque 자료구조를 활용하자. 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에

            비해 효율적이고 queue 라이브러리를 사용하는 것보다 더 간단하다.

    1-3. 재귀 함수

          - 자기 자신을 다시 호출하는 함수

          - 보통 파이썬 인터프리터는 호출 횟수 제한이 있다.

          - '재귀 함수의 종료 조건'이 꼭 필요하다.

          - 내부적으로 스택 자료구조와 동일하다. 따라서 스택 자료구조를 사용해야 하는 많은 알고리즘은 재귀 함수를 이용하여
            간편하게 구현될 수 있다.

          - 재귀함수가 수학의 점화식(재귀식)을 그대로 옮겼기 때문에 재귀 함수의 코드가 더 간결하다.

            * 수학의 점화식 : 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미한다.

2. 탐색 알고리즘 DFS/BFS

    2-1. DFS

          - 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

          - 스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다.

          - '그래프'
            : 프로그래밍에서 크게 2가지 방식으로 표현할 수 있는데 1) 인접 행렬, 2) 인접 리스트이다.

              1) 인접 행렬(Adjacency Matrix) :  2차원 배열로 그래프의 연결 관계를 표현하는 방식

                 - 연결이 되어 있지 않은 노드끼리는 비용이 무한으로 999999999 등의 큰 값으로 초기화한다.

              2) 인접 리스트(Adjacency List) : list로 그래프의 연결 관계를 표현하는 방식
                 - 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.

              3)인접 행렬 vs 인접 리스트

                 : 메모리 측면에서는 인접 행렬이 낭비되고, 속도 측면에서는 인접 리스트가 느리다.

    2-2. BFS

          - 너비 우선 탐색이라고 부르며, 가까운 노드부터 탐색하는 알고리즘이다.

          - 큐를 이용하면 선입선출이 되기에 자연스럽게 가까운 노드부터 탐색을 할 수 있다.

    2-3. DFS vs BFS
          - 둘 다 탐색을 수행하는데 O(N)의 시간이 소요된다. 컴퓨터 시스템의 특성상 DFS보다 BFS가 좀 빠르다.

3. 음료수 얼려 먹기

   - 문제

   - 문제 해결

     : 0인 지점에서 주변 상하좌우를 DFS로 방문하면 된다.

   - 소스 코드

n, m = map(int, input().split())

ice_box = []
for i in range(n):
  ice_box.append(list(map(int,input())))

def dfs(x, y):
  if x <= -1 or x >= n or y <= -1 or y >= m:
    return False
  
  if ice_box[x][y] == 0:
    ice_box[x][y] = 1
    dfs(x-1,y)
    dfs(x,y+1)
    dfs(x+1,y)
    dfs(x,y-1)
    return True
  return False

result = 0
for i in range(n):
  for j in range(m):
    if dfs(i,j) == True:
      result += 1

print(result)

#include <stdio.h>
using namespace std;

int N, M;
int ice_box[1000][1000];

bool dfs(int x, int y){
	if(x <= -1 || x >= N || y <= -1 || y >= M)
		return false;
	if(ice_box[x][y] == 0){
		ice_box[x][y] = 1;
		dfs(x - 1, y);
		dfs(x, y + 1);
		dfs(x + 1, y);
		dfs(x, y - 1);
		return true;
	}
	return false;
}

int main() {
    scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			scanf("%1d", &ice_box[i][j]);
	}
	int result = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if(dfs(i,j) == true)
				result += 1;
		}
	}
	printf("%d\n", result);
    return 0;
}

4. 미로 탈출

   - 문제

   - 문제 해결

     : 시작 지점에서 가장 가까운 노드를 차례대로 탐색하는 BFS로 풀면 된다.

   - 소스 코드

from collections import deque

n, m = map(int, input().split())
miro = []
for i in range(n):
  miro.append(list(map(int, input())))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def bfs(x,y):
  que = deque()
  que.append((x,y))
  
  while que:
    x, y = que.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if nx < 0 or nx >= n or ny < 0 or ny >= m:
        continue
      if miro[nx][ny] == 0: continue
      elif miro[nx][ny] == 1:
        miro[nx][ny] = miro[x][y] + 1
        que.append((nx,ny))
  return miro[n-1][m-1]

print(bfs(0,0))

#include <stdio.h>
#include <queue>
using namespace std;

int N, M;
int miro[201][201];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int bfs(int x, int y){
	queue<pair<int, int>> que;
	que.push({x, y});

	while(!que.empty()){
		int x = que.front().first;
		int y = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if(miro[nx][ny] == 0) continue;
			if(miro[nx][ny] == 1) {
				miro[nx][ny] = miro[x][y] + 1;
				que.push({nx, ny});
			}
		}
	}
	return miro[N-1][M-1];
}

int main() {
    scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			scanf("%1d", &miro[i][j]);
	}
	printf("%d\n", bfs(0,0));
    return 0;
}

Ch4. 구현 implementation

1. 아이디어를 코드로 바꾸는 구현

      1-1. 피지컬로 승부하기

             - '코딩 테스트에서 구현이란?'

                : 머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.
                  그렇기 때문에 대부분 구현을 별도의 유형으로 다루지 않지만, 코딩 테스트에서는 자주 출제가 된다.

             - '피지컬이 좋다'
               : 프로그래밍 문법을 정확하게 숙지하고, 라이브러리 사용 경험이 풍부하며, 코드 작성 속도(타자)가 빠를 때 

             - '구현 유형의 문제'
               : 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제
                 (알고리즘은 설계했는데 구현이 먼저 풀 수 있는 문제가 없을 때 푸는 것이 좋다)

                  1) 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

                  2) 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형             

      1-2. 구현 시 고려해야 할 메모리 제약 사항

             - '변수의 표현 범위'

                1) C/C++/Java
                    : int형, long long형, BigInteger 순으로 자료형의 표현 범위에 주의해야한다.

                2) Python
                    :  직접 자료형을 지정할 필요가 없고 매우 큰 수의 연산 또한 지원하므로 주의하지 않아도 된다.

             - '파이썬에서 리스트 크기'

                 : 파이썬에서 리스트를 이용할 때 코딩 테스트의 메모리 제한을 고려해야 한다. (그러나, 드물다)

      1-3. 채점 환경

             - 시간 제한이 1초이고, 데이터의 개수가 100만개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN)이내의

               알고리즘을 이용하여 풀어야 한다. N = 1,000,000(100만) -> NlogN = 약 20,000,000(2000만번)

               (제출한 코드가 1초에 2000만번의 연산을 수행한다고 가정하면 크게 무리가 없다)

             - 따라서 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤 이 문제를 어느 정도의 시간 복잡도의

               알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 한다.

      1-4. 구현 문제에 접근하는 방법

             - 특징
               1) 문제의 길이가 길지만, 고차원적인 사고력을 요구하지 않기 때문에 문법에 익숙하다면 오히려 쉽게 풀 수 있다.

               2) 문자열을 처리하거나 큰 정수를 처리하는 구현 문제가 나올 때는 C/C++/Java보다 Python이 쉬울 수 있다.

      1-5. 상하좌우

             - 문제

             - 문제 해결
                : 요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례하게 된다. 이동 횟수가 N번인 경우 시간 복잡도 O(N)이다.
                  일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에서 simulation 유형으로 분류되며 구현이 중요한 문제다.

             - 소스 코드

      1-6. 시각

             - 문제

             - 문제 해결

               : 00시 00분 00초 ~ 23시 59분 59초까지의 모든 경우의 수는 86,400가지(24*60*60초)이다.

                 경우의 수가 100,000가지도 되지 않기 때문에 시간 제한 2초 안에 문제를 해결할 수 있다.

                 가능한 경우의 수를 모두 검사하는 방법으로 완전 탐색 유형이다.

                 일반적으로 탐색해야할 전체 데이터의 개수가 100만개 이하일 때 완전 탐색을 사용하면 적절하다.

             - 소스 코드

2. 왕실의 나이트

    - 문제

    - 문제 해결

       : 나이트가 위치한 곳을 문자열과 숫자의 조합이 아니라 같은 행과 열 형태로 들어올 수도 있었다. (예외처리 필요)

         이 문제는 나이트가 이동할 수 있는 경로를 하나씩 확인하여 이동하면서 결과를 확인하면 된다. 

         나이트가 이동할 수 있는 경로는 2가지이다.

          1) 수평으로 두 칸 이동 후 수직으로 한 칸 이동

          2) 수직으로 두 칸 이동 후 수평으로 한 칸 이동

가능한 움직임을 (x,y) 나타내면 (-1, -2), (1, -2), (-1, 2), (1, 2), (-2, -1), (2, -1), (-2, 1), (2, 1)로 8가지의 경우가 나온다.

상하좌우와 비슷한 문제지만 이동방향을 dx,dy를 사용하느냐,
특정 방향 값을 지정하여 방향을 설정하느냐 2가지 모두 자주 사용되므로 참고!

    - 소스 코드

3. 게임 개발

    - 문제 

    - 문제 해결

      :  문제가 길고 문제를 바르게 이해하여 소스 코드로 옮기는 과정이 간단하지 않기 때문에 반복적인 숙달이 필요하다.

    - 소스 코드

n, m = map(int, input().split())
visit = [[0] * m for _ in range(n)]

x, y, direction = map(int, input().split())
visit[x][y] = 1

arr = []
for i in range(n):
  arr.append(list(map(int, input().split())))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def turn_left():
  global direction
  direction -= 1
  if direction == -1:
    direction = 3

count = 1;
turn_time = 0
while True:
  turn_left()
  nx = x + dx[direction]
  ny = y + dy[direction]

  if visit[nx][ny] == 0 and arr[nx][ny] == 0:
    visit[nx][ny] = 1
    x = nx
    y = ny
    count += 1
    turn_time = 0
    continue
  else:
    turn_time += 1
  
  if turn_time == 4:
    nx = x - dx[direction]
    ny = y - dy[direction]
    if arr[nx][ny] == 0:
      x = nx
      y = ny
    else:
      break
    turn_time = 0

print(count)

#include <stdio.h>
using namespace std;

int N, M, x, y, dir;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int arr[51][51];
int visit[51][51];

void turn_left() {
    dir -= 1;
    if (dir == -1) dir = 3;
}

int main() {
    scanf("%d %d", &N, &M);
    scanf("%d %d %d", &x, &y, &dir);
    visit[x][y] = 1;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
            scanf("%d", &arr[i][j]);
    }
    int count = 1;
    int turn_cnt = 0;
    while (true) {
        turn_left();
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (visit[nx][ny] == 0 && arr[nx][ny] == 0) {
            visit[nx][ny] = 1;
            x = nx; y = ny;
            count += 1; turn_cnt = 0;
            continue;
        }
        else turn_cnt += 1;

        if (turn_cnt == 4) {
            nx = x - dx[dir];
            ny = y - dy[dir];
            if (arr[nx][ny] == 0) {
                x = nx; y = ny;
            }
            else break;
            turn_cnt = 0;
        }
    }

    printf("%d", count);
    return 0;
}

Ch3. 그리디 greedy

1. 당장 좋은 것만 선택하는 그리디

    - 현재 상황에서 당장 좋은 것만을 골라 현재의 선택이 나중에 미칠 영향은 고려하지 않는 방법

    - 보통 코딩 테스트에서 출제되는 유형은 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

      특정한 문제를 만났을 때, 그리디로 문제를 풀 수 있을지 파악할 수 있어야 한다.

   - 기준에 따라 좋은 것을 선택하는 알고리즘이기에 기준을 제시해주고, 정렬 알고리즘과 함께 짝을 이루어 출제된다.

      1-1. 예제 거스름돈

             - 문제

             - 소스 코드

             - 정당성
               : 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 조합해 다른 해가 나올 수 X 

                 때문에 화폐이 단위가 무작위로 주어졌을 때에 그리디 알고리즘으로 해결할 수 없다.

      1-2. 그리디 알고리즘의 정당성

             - 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없는 가능성이 다분하다.

               따라서, 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토할 수 있어야 한다.

               Tip. 그리디 -> 다이나믹, 그래프 알고리즘

2. 큰 수의 법칙

    - 문제

    - 문제 해결

       : 가장 큰 수와 두번째로 큰 수를 저장한다. 연속으로 더할 수 있는 횟수는 최대 K번이므로

         '가장 큰 수를 K번 더하고, 두 번째로 큰수를 한 번 더하는 연산'을 반복하면 된다.

    - 소스 코드 1(python, M이 10,000 이하일 때)

    - 소스 코드 2(python, M이 100억 이상일 때)

       : 반복되는 수열 first와 second가 더해질 때 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있다.

         반복되는 수열의 길이는 (K+1)이고 M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다.
         여기에 (K+1)*M은 first가 반복하는 횟수가 되고, M이 (K+1)로 나누어 떨어지지 않는 것을 고려했을 때,

         '가장 큰 수가 더해지는 횟수는 int(M/(K+1)) * K + M%(K+1)'

    - 소스 코드 3(c++, M이 100억 이상일 때)

3. 숫자 카드 게임

    - 문제

    - 문제 해결

       : 각 행마다 가장 작은 수를 찾은 뒤에 작은 수들 중에서 가장 큰 수를 찾는 것이다.

    - 소스 코드

4. 1이 될 때까지

    - 문제

    - 문제 해결

       : 주어진 n에 대하여 최대한 많이 나누기 연산을 수행하면 된다.

    - 소스 코드