코딩 테스트 준비 (동빈나님의 이코테 강의 리뷰1)

어쩌다보니 인턴십을 준비하면서 코딩 테스트 일정이 잡히게 되었다.

나한테 주어진 시간은 3일밖에 없었기 때문에 어떻게 코딩 테스트를 준비할까하다가 티스토리에 글을 작성하면서 이코테 강의를 듣기로 했던 것이 기억이 나서, 적어도 알고리즘 유형이라도 알고 들어가자 ! 라는 마음으로 공부를 시작했다.

코딩 테스트의 결과는 이코테 강의 리뷰 마지막에 남기도록 하며, 3일동안 벼락치기 공부했던 것을 티스토리에 쓰려고 한다.

3일에 걸쳐서 했던 정도를 기록하도록 하겠다.

코딩 테스트 출제 경향 분석 및 파이썬 문법

시간 복잡도 (개인적으로 정말 중요하다고 생각되는 부분 중에 하나인 것 같다.)

• 빅오 표기법 (Big-O Notation) : 가장 빠르게 증가하는 항만을 고려하는 방법
  • O(1) : 상수 시간
  • O(logN) : 로그 시간
  • O(N) : 선형 시간 등

알고리즘 설계 Tip

• 연산 횟수가 5억을 넘어가는 경우 (일반 컴퓨터, CPU)
  • python 기준 5~15초 가량의 시간이 소요
  • 수행 시간은 통상적으로 1~5초 소요

알고리즘 설계할 때, 고려해야 할 점

• 가장 먼저 확인해야 하는 것은 시간 제한 (수행 시간 요구 사항)
  • 1초인 문제를 만났을 때?
    • 1000만 정도의 데이터를 O(N)으로 해결 가능

알고리즘 문제 해결 과정

• 지문 읽기 및 컴퓨터적 사고
• 요구사항 (복잡도) 분석
• 문제 해결을 위한 아이디어 찾기
• 소스코드 설계 및 코딩

파이썬 자료형

• 정수형 : 1,2,3
• 실수형 : 소수점이 붙은 모든 숫자
  • 5.0도 실수형
  • 1e9와 같은 지수 표현 방식은 실수형으로 표현됨
  • 도달할 수 없는 노드에 대한 최단 거리를 INF로 설정
  • 정수형 데이터로 넣어야 한다면, int를 사용해서 넣기
  • 10진수 체계에서 0.3+0.6=0.9라고 정확하게 계산이 되지만, 컴퓨터가 사용하는 2진수 체계에선 0.3+0.6=0.899999와 같이 미세한 오차를 만들 수 있다.
    • 따라서, round() 함수를 이용하여 n번째 자리까지 반올림하여 표시하도록 진행
  • 파이썬에서 나누기 연산자의 결과 → 실수형
  • 나머지 연산자(%), 몫 연산자(//), 거듭 제곱 연산자(**)
    • ^는 거듭 제곱 아니라는 것을 유의
• 리스트 자료형 : 데이터를 연속적으로 담아 처리하기 위한 자료형
  • []로 초기화, 쉼표(,)로 원소 구분
  • index 값을 괄호에 넣고, 인덱스는 0부터 시작
  • 리스트 컴프리헨션 : 리스트를 초기화하는 방법 중 하나
    • 대괄호 안에 조건문과 반복문을 적용하여 리스트를 초기화
    • ex. x = [t for t in range(10)]
    • 리스트 컴프리헨션은 2차원 리스트를 초기화할 때 효과적으로 사용할 수 있다.
      • 특히, N x M 크기의 2차원 리스트를 한 번에 초기화 해야 할 때, 매우 유용하다.
      • ex. [[0] * m for _ in range(n)] (O) / [[0] * m] * n (X)
  • 여러 메서드 사용하기
    • append / sort / reverse / insert / count / remove
    • remove 같은 경우, 여러 값이 있을 때 하나의 값만 제거한다.
• 문자열 자료형 (”, ‘)
  • 덧셈을 이용하면 Concatenate (연결) 된다. 곱할 경우, 여러번 반복된다.
  • 문자열은 특정 인덱스의 값을 변경할 수 없다. 즉, a[3]=’c’ 이런 식으로 변경하는 것이 불가능
• tuple 자료형
  • 한 번 선언된 값을 변경할 수 없다.
  • 리스트는 대괄호, tuple은 소괄호를 이용한다. 또한 리스트보다 공간 효율적이다.
  • 서로 다른 성질의 데이터를 묶어서 관리해야 할 때, 자주 사용한다.
    • 최단 경로 알고리즘 (비용, 노드 번호)의 형태로 튜플 자료형을 사용하거나 학생 번호와 성적 등을 관리할 때도 사용한다.
  • 또한, hashing의 키 값으로 사용해야 할 때와 메모리를 효율적으로 사용해야 할 때 사용한다.
• Dictionary (사전) 자료형
  • key, value 값의 쌍을 데이터로 가지는 자료형이다.
  • 데이터 조회 및 수정에 있어서 O(1)의 시간 복잡도를 가진다.
  • key, value를 따로 추출할 수 있다. 또한 이를 llist로 바꿀 수 있다.
• 집합 자료형
  • 중복을 허용하지 않고, 순서가 없다.
  • set() 함수를 이용하며 중괄호로 초기화 가능하다.
  • 집합 연산자를 이용할 수 있다.

기본 입출력에 관한 내용

모든 프로그램은 적절한 입출력 양식을 가지고 있으며, 프로그램 동작의 첫 번째 단계는 데이터를 입력 받거나 생성하는 것이다.

• input() : 한 줄의 문자열을 입력 받는 함수이다.
• map() : 리스트의 모든 원소에 각각 특정한 함수를 적용할 때, 사용한다.
  • ex. data = list(map(int,input().split())
• 사용자로부터 입력을 최대한 빠르게 받아야 하는 경우
  • sys.stdin.readline() 메서드를 활용
  • 이 때, 엔터 이후는 줄 바꿈 기호가 입력되므로 rstrip() 메서드를 함께 사용한다.
• 출력할 때, print를 사용하며 줄바꿈을 하고 싶지 않으면 end를 사용한다.
• f를 사용하여 중괄호 안에 변수명을 기입하여 문자열과 정수를 함께 넣을 수 있다.

조건문과 반복문

• pass를 이용하여 디버깅 과정을 실행할 수 있다.
  • 조건문의 형태만 만들어 놓고, 조건문을 처리하는 부분은 나중에 작성하고 싶을 때.
• while문
  • 무한 반복문이 될 수 있다.
• continue 키워드를 통해, 반복문에서 남은 코드 실행을 건너 뛰고 다음 반복을 진행할 수 있다.
• 즉시 탈출하고자 할 때, break 문을 사용할 수 있다.

함수

• 함수란, 특정한 작업을 하나의 단위로 묶어 놓은 것을 의미하며 불필요한 반복 작업을 막을 수 있다.
  • def 함수명(매개변수) : ~ return 반환 값
• global 함수를 이용하여 함수 바깥에 선언된 함수를 이용할 수 있다.

람다 표현식 : 함수를 간단하게 작성할 수 있으며, 특정한 기능을 수행하는 함수를 한 줄에 작성할 수 있다.

• (lambda 매개변수 : 수행하는 식) 으로 진행할 수 있다.
  • ex. print((lambda a,b : a+b)(3,7))
• 여러 개의 리스트에 적용할 수 있다.
  • list1, list2가 잇다면?
  • map(lambda a,b:a+b, list1, list2) 이런 식으로 가능

표준 라이브러리

• 내장 함수 → 기본적인 함수 (import 없이 사용 가능)
• itertools : 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 기능
  • 순열과 조합 라이브러리 → 코딩테스트에 자주 사용됨
• heapq : heap 자료 구조를 제공 (개인적으로 이런 라이브러리가 있다는 것을 처음 알게 되었다.)
  • 우선 순위 큐 기능을 구현
• bisect : 이진 탐색 기능을 제공
• collections : 덱(deque), 카운터(Counter)
• math : 필수적인 수학적 기능을 제공
  • 팩토리얼, 제곱근, 최대공약수(GCD), pi 등의 상수 포함

내장 함수

• sum / min / max
• eval : 문자열로 표현된 수학 식의 결과를 실수형으로 반환
• sorted : key들을 기준으로 tuple 자료형 정리 가능하다.

순열과 조합

• itertools 사용
• 순열은 순서를 고려하며, 조합은 순서를 고려하지 않는다.
• from itertools import permutation (순열) / combination (조합) / product (중복 순열) / combinations_with_replacement (중복 조합)

Counter

• 등장 횟수를 세는 기능을 제공한다.
• 리스트와 같이 반복 가능한 객체가 주어졌을 때, 내부 원소가 얼마나 등장했는지 알려준다.

math

• 최대 공약수를 구해야 할 때, gcd() 함수를 이용할 수 있다.
• 최소 공배수는 a*b // math.gcd(a,b)로 구할 수 있다.

그리디 알고리즘

이 부분도 굉장히 중요한 부분이다.

어느정도 수업을 들으면서 감은 잡혀있는 상황이었지만 단 한번도 코드로 구현해본 적은 없었다.

 

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미하므로, 단순히 가장 좋은 것을 반복적으로 선택해도 최적의 해를 구할 수 있는 지를 검토하는 ‘정당성 분석’이 가장 중요하다.

그리디 알고리즘으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있도록 문제 출제

거스름돈 문제가 왜 그리디 알고리즘 문제인가? (500,100,50,10원으로 돈을 거슬러 주는 문제)

⇒ 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위가 배수이므로, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

즉, 이것이 정당한지 검토하는 것이 굉장히 중요하다.

N이 1이 될 때까지?

a,b = map(int,input().split())
cnt = 0

while a//b!=1:
  if a%b==0:
    cnt+=1
    a=a//b
  else:
    a=a-1
    cnt+=1

print(cnt+1)

 

이건 나의 답변이고, 동빈나님의 이코테 강의에서의 답변은 다음과 같다.

n,k = map(int,input().split())
result = 0

while True:
	target = (n//k) * k
	result += (n-target)
	n = target

	if n<k:
		break

	result +=1
	n //= k

result += (n-1)
print(result)

repl.it으로 실행해본 결과, 내 코드는 26과 3을 입력했을 때 running time이 굉장히 오래 걸리는 반면, 동빈나님의 코드는 바로 해결이 된다.

첫째 문자열에서 만들 수 있는 가장 큰 수 고르기

S = input()
S = [int(S[i]) for i in range(len(S))]

result = 0

for i in range(len(S)):
  if S[i]==0 or result==0:
    result += S[i]
  else:
    result *= S[i]

print(result)

마찬가지로 이게 나의 답변이고, 동빈나님의 코드는 아래에 있다.

data = input()
result = int(data[0])

for i in range(1,len(data)):
	num = int(data[i])
	if num<=1 or result<=1:
		result+=num
	else:
		result*=num

print(result

 

구현

구현

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.

problem → thinking → solution

문제에서 요구하는 내용이 구현이 어렵거나 구현에 초점이 맞춰진 문제를 구현 문제라고 한다.

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아서 사용해야 하는 문제

행렬 문제 (위치 확인) + 방향 벡터 자주 활용됨

상하좌우로 이동해서 좌표를 구하는 문제

n = int(input())
x,y = 1,1
plans = input().split()

dx = [0,0,-1,1]
dy = [-1,1,0,0]
move_types = ['L','R','U','D']

for plan in plans:
  for i in range(len(move_types)):
    if plan == move_types[i]:
      nx = x + dx[i]
      ny = y + dy[i]

  if nx < 1 or ny < 1 or nx > n or ny > n :
    continue

  x,y = nx, ny

print(x,y)

matrix 형태로 진행이 되는 것이므로, 우리가 일반적으로 euclidean 좌표계에서 사용하는 좌표를 생각해서 up, down 등의 dx, dy를 설정해주면 안된다.

00시 00분 00초 → N시 59분 59초까지 3이 하나라도 등장하는 경우의 수

가능한 모든 시각의 경우의 수 : 86,400

따라서, 완전 탐색 (모든 경우의 수를 다 검사해보는 방법) 문제 유형을 사용하여 진행할 수 있다.

h = int(input())

count = 0 
for i in range(h+1):
  for j in range(60):
    for k in range(60):
      if '3' in str(i) + str(j) + str(k):
        count+=1

print(count)

그래프 탐색 알고리즘 (DFS/BFS)

탐색이란, 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.

대표적인 그래프 탐색 알고리즘으로 DFS, BFS가 있다.

코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 한다.

2가지 자료 구조를 숙지하고 넘어가자.

• 스택 자료구조란, 먼저 들어온 데이터가 나중에 나가는 형식의 자료구조이다. (선입후출)
  • 입구와 출구가 동일한 형태라고 이해하기
  • 삽입과 삭제로 수행 가능하며, append / pop으로 구성할 수 있다.
  • 출력할 때, stack[::-1]을 이용하여 출력 순서를 확인할 수 있으며, stack을 이용하여 입력 순서를 확인할 수 있다.
• 큐 자료구조란, 먼저 들어온 데이터가 먼저 나가는 형식의 자료구조이다. (선입선출)
  • 입구와 출구가 모두 뚫려 있는 터널과 같은 형태
  • append와 popleft를 사용할 수 있으며, queue의 경우에는 list로도 구현이 가능하지만 collections 라이브러리의 deque를 사용하는 것이 훨씬 더 시간 복잡도를 낮출 수 있다.
    • list를 이용할 경우, 원소를 꺼내고 원소의 위치를 재정렬하는 과정에서 연산이 수행되므로 시간 복잡도 올라감

from collections import deque
queue = deque()
queue.append(5)
queue.popleft()

print(queue) #먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 출력

 

재귀 함수(recursive function)란, 자기 자신을 다시 호출하는 함수를 의미한다. → 무한히 어떠한 동작을 반복 수행할 수 있다.

• 재귀 함수를 문제 풀이에서 사용할 때, 종료 조건을 반드시 명시해야 한다. → 그렇지 않으면 함수가 무한히 호출됨.
  • 종료 조건을 포함한 재귀 함수

def a(i):
	if i==100: # 종료 조건
		return
	print(i)
	a(i+1)

a(1)

• 팩토리얼을 구현한 재귀함수도 가능
• 최대공약수 계산하는 ‘유클리드 호제법’
  • 유클리드 호제법이란?
  • 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 했을 때, A와 B의 최대 공약수는 B와 R의 최대공약수와 같다.

def gcd(a,b):
	if a%b ==0:
		return b
	else:
		return gcd(b,a%b)

print(gcd(192,162))

• 재귀 함수를 통해 복잡한 알고리즘을 간결하게 작성할 수 있다.
• 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다. → 즉, 반복문을 재귀 함수로 간편하게 작성할 수 있다는 의미
• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임이 쌓인다.
  • 따라서, 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.

DFS (Depth-First Search)

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

DFS는 스택 자료구조 (혹은 재귀 함수)를 이용하며 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입 → 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리를 한다.
   1. 방문 하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

코드로 살펴보자.

def dfs(graph,v,visited):
  visited[v] = True # 방문 처리
  print(v,end=' ') # 방문 노드 출력
  for i in graph[v]: # 인접 노드 탐색
    if not visited[i]: # 방문하지 않은 노드 탐색
      dfs(graph,i,visited) # 재귀함수 호출


# graph는 보통 1부터 시작하는 경우가 많기 때문에 index 0에 해당하는
# 요소에는 빈 리스트를 할당해서 진행
graph = [[],[2,3,8],[1,7],[1,4,5], etc.]

visited = [False] * 9 # 방문 처리를 하지 않았으면 False
dfs(graph,1,visited)

BFS (Breadth-First Search)

BFS는 너비 우선 탐색이라고 부르며 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘을 의미한다.

BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤에, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

from collections import deque

def bfs(graph, start, visited):
  queue = deque([start]) # 시작 노드 입력
  visited[start] = True # 방문 처리
  while queue:
    vertex = queue.popleft()
    print(vertex, end=' ')
    for i in graph[vertex]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True

graph = [[],[2,3,8],[1,7],[1,4,5],etc]
visited = [False] * 9
bfs(graph, 1, visited)

• 재귀 함수 형태가 아니며, deque 라이브러리를 그대로 사용함.

탐색 문제 예제1

음료수 얼려 먹기 문제 (DFS 활용)

칸막이가 존재하면 1, 존재하지 않으면 0으로 두고 음료수를 부어서 얼렸을 때, 총 몇 개의 아이스크림이 나오는가?

1. 특정한 지점의 주변 상,하,좌,우를 모두 다 살펴본 뒤에 0이면서도 아직 방문하지 않은 지점을 방문
2. 방문한 지점에서 다시 상하좌우를 살펴보고, 방문을 진행하는 과정을 반복하면 연결된 모든 지점을 방문할 수 있다.
3. 1~2번 과정을 반복하며 방문하지 않은 지점의 수를 카운트

답변

def dfs(x,y):
	# 주어진 범위는 0~n-1, 0~m-1까지이므로.
  if x<= -1 or x>= n or y<=-1 or y>=m:
    return False

  if graph[x][y] == 0: # 아직 방문하지 않았을 경우
    graph[x][y] = 1 # 방문 처리
    dfs(x-1,y) # 상하좌우로 탐색하며 방문 처리
    dfs(x,y-1)
    dfs(x+1,y)
    dfs(x,y+1)
    return True # 모든 곳을 방문하고 더 이상 방문한 곳이 없을 경우
  return False # 아직 더 방문할 곳이 남았을 경우 -> False


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

graph = []
for i in range(n):
  graph.append(list(map(int,input()))) # 2차원 배열 받기

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

print(result)

탐색 문제 예제2

미로 탈출 문제 (BFS)

NxM 크기의 직사각형 형태의 미로에 갇혀있으며, 괴물이 있는 부분은 0으로 표시되어 있음. → 1으로 표시된 곳만 갈 수 있다.

도착 지점은 (N,M)이다.

• 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다.

from collections import deque

def bfs(x,y):
  queue = deque()
  queue.append((x,y)) # queue에 방문처리를 위해 x,y 좌표 대입

  while queue: # queue가 비어 있을 때까지 반복
    x,y = queue.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

			# 0이면 벽이므로 이 또한 무시
	    if graph[nx][ny] == 0:
	      continue
			
      # 해당 노드를 처음 방문할 경우, 최단 거리 기록 
	    if graph[nx][ny] == 1:
	      graph[nx][ny] = graph[x][y] + 1
	      queue.append((nx,ny))
    
  return graph[n-1][m-1]

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

# 상하좌우 방향 벡터 정의
dx = [-1,1,0,0]
dy = [0,0,-1,1]

print(bfs(0,0))

 

정렬 알고리즘

정렬이란, 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다.

문제 상황에 따라 적절한 정렬 알고리즘을 사용해야 한다.

선택 정렬

선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해서 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. → 전체 데이터가 정렬된다.

이중 반복문을 통해 선택 정렬을 구현할 수 있다.

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

for i in range(len(array)):
  min_index = i
  for j in range(i+1, len(array)):
    if array[min_index] > array[j]:
      min_index = j
  array[i], array[min_index] = array[min_index], array[i]

print(array) # 0~9까지 차례대로 정리됨

선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.

따라서, 빅오 표기법으로 $O(N^2)$이다.

삽입 정렬

삽입 정렬

처리 되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.

• 현재 처리하는 데이터가 7이라면, 다음 숫자인 5의 기준에서 왼쪽 / 오른쪽, 즉 2가지의 경우밖에 없다.
• 처리하는 데이터를 가지고 다른 데이터를 기준으로 어느 위치 (왼쪽, 오른쪽)로 가야할 지 설정

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

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

이중 반복문이므로, 시간 복잡도는 $O(N^2)$이다.

하지만, 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. → $O(N)$

퀵 정렬

퀵 정렬

기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. → 일반적으로 대부분의 언어 정렬 라이브러리의 근간이 될 정도로 많이 사용한다.

퀵 정렬을 수행할 때, 첫 번째 데이터를 기준 데이터 (pivot)로 설정한다.

Pivot값을 기준으로, 왼쪽부터는 더 큰 값, 오른쪽부터는 더 작은 값을 가지는 수를 찾아서 위치를 바꿔주고, 만약 이 위치가 서로 엇갈릴 경우 pivot과 해당 위치의 작은 값과 위치를 바꾸어 divide (분할)한다.

이상적인 경우, 분할이 절반씩 일어난다면 전체 연산 횟수, 즉 시간 복잡도는 $O(NlogN)$을 기대할 수 있다.

하지만 최악의 경우, $O(N^2)$의 시간 복잡도를 가진다.

표준 라이브러리를 사용하면, 기본적으로 $O(NlogN)$의 시간 복잡도를 보장할 수 있다.

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

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

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

여기서 파이썬의 장점을 살린 방식으로 코딩을 할 수 있다!

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

def quick_sort(array):
  if len(array) <= 1:
    return array
  pivot = array[0]
  tail = array[1:] # pivot 값만 제외하고 나머지 모두 tail로.

# 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)

print(quick_sort(array))

계수 정렬

특정한 조건이 부합할 때만 사용할 수 있으나, 매우 빠르게 동작하는 정렬 알고리즘이다.

• 계수 정렬은 데이터의 크기 범위가 제한되어 있어서 정수 형태로 표현할 수 있을 때, 사용 가능하다.
• 데이터 개수가 N, 최댓값이 K라고 해도 수행 시간은 $O(N+K)$가 최대.

각각의 데이터 (인덱스)가 몇 번 등장했는지 카운트하고 작은 인덱스부터 카운트 수만큼 반복해서 출력하는 방식으로 정렬한다.

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

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

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

for i in range(len(count)):
  for j in range(count[i]):
    print(i, end=" ")

동일한 값을 가지는 데이터가 여러 개 등장할 때, 효과적으로 사용할 수 있다. ⇒ 성적의 경우, 100점을 맞은 학생이 여러 명일 때, 계수 정렬이 효과적일 수 있다.

정렬 알고리즘 예제1

예제 : 두 배열의 원소 교체 문제

• 내 답변

N, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

A.sort()
B.sort(reverse=True)

for i in range(K):
  if A[i] < B[i]:
    A[i],B[i] = B[i], A[i]
  else:
    continue

print(sum(A))

• 동빈나님의 답변

N, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

A.sort()
B.sort(reverse=True)

for i in range(K):
  if A[i] < B[i]:
    A[i],B[i] = B[i], A[i]
  else:
    break

print(sum(A))

더 이상 바꿀 수 없으므로 continue 대신 break를 넣어야 한다.

 

마치며

1일차를 마치며,, 정말 많은 것들을 깨달은 하루였다.

사실 학부생으로 수업도 듣고 과제나 플젝도 하면서 학회 활동과 인턴 활동까지 병행하는 상황에서 코딩 테스트를 위한 시간을 많이 투자하긴 정말 어려웠다. 그럼에도 불구하고, 이만큼 해냈다는 사실이 너무 뿌듯했다.

코딩 테스트에 대한 부담감은 시작하기 전, 애초에 준비하기 전부터도 엄청 가득했었던 지라 이번에 코딩 테스트때문에 떨어진다고 하더라도 내가 어느 점이 부족하고 어떻게 해나가야 할지, 내 인생에서 또 하나의 기록될만한 포인트인 것은 확실해서 일단 열심히 준비하면서라도 정진해보자는 것이 내 의지이자 생각이다.

 

그리고 이전부터 파이썬을 계속 다뤄와서인지 모르겠지만 문법 자체를 이해하는 것은 하나도 어렵지 않았다. 2학년 2학기에 들었던 자료구조 수업을 열심히 들어서인지 알고리즘 설명을 알아듣는 것 또한 어렵지 않았다.

자세하게 들어가보면 또 달라질 수 있겠지만, 코딩 테스트가 마냥 버겁기만 한 것은 아니란 생각이 들었다. 조금만 더 준비를 꾸준히 한다면 코딩 테스트로 발목 잡힐 일이 있을까..? 싶은 생각이다.

그래도 .. 일단 이런 잡생각은 떨쳐두고 열심히 해보자!