[Python] 코딩테스트 (1)

코딩테스트 정복 시작 :

학습 계획, 코테 유용한 팁, Python 유용한 모듈과 함수

1. 코딩테스트 준비

1.1. 준비 목적

• 문제 해결력 지속 및 향상
  • 코딩테스트를 준비하는 가장 큰 이유다.
  • 코딩테스트 문제를 푸는 과정에서 문제 해결을 위한 로직 구성, 로직 구현 능력이 향상됨을 체감했다.
  • 그래서 이런 방향으로 머리를 지속적으로 활용해야 함을 느꼈다.
  • 이틀 이상 쉬면 로직 구현 능력이 금방 굳어버리기 때문에 꾸준히 해야 한다.
  • 또한, 다른 사람들의 코드와 비교하면서 해결을 위한 관점을 넓힐 수 있다.
• 취업 및 경진대회 준비
  • 코딩테스트를 실시하는 생각보다 기업이 많기 때문에 취업준비생으로서 생각치 못한 기회를 얻을 수 있다.
  • 또한, 현대 알고리즘 경진대회 수상을 목표로 하고 준비하고 있다.

1.2. 준비 방법

코딩테스트를 준비한다면 다음과 같은 순서로 학습하면 효율적으로 완벽하게 준비할 수 있다.

1) 정석 방법

• 1단계 : Python 기초 100제
  • 코드업에서 제공하는 100제로 Python의 기본기와 문자열 등을 학습 가능하다.
• 2단계 : 핵심 알고리즘 많이 풀기
  • 그리디 50문제
  • DFS/BFS 50문제
  • 동적 프로그래밍 50문제
  • 다익스트라 20문제
• 3단계 : 기출 문제 풀기
  • 삼성전자 SW 코딩테스트 기출문제 (백준)
  • 카카오 코딩테스트 기출문제 (프로그래머스)
• 4단계 : 심화 학습
  • 중급 DP, 그래프, 문자열
  • 세그먼트 트리(인덱스 트리, 합 트리, 최대최소, k번째, 리라벨링)
  • MST(크루스칼, 프림, 벨만포드)
  • LCA, 네트워크 플로우

2) 나만의 방법

• 1단계 : 멀티잇 코딩테스트 러닝클래스 수료

  • Python의 기본기는 어느 정도 알고 있기 때문에 기초 100제는 넘어간다.
  • 멀티캠퍼스 수강생에게 제공하는 프로그램으로 어떤 문제들을 풀면 좋은지 가이드를 받기 위해 신청했다.
  • 총 30문제로 구성되어 있다.

• 2단계 : 핵심 알고리즘 풀기

  • 경진대회 준비를 빨리 시행해야 하기 때문에 핵심 알고리즘을 빠르게 풀어본다.
    • 그리디 5문제
    • DFS/BFS 5문제
    • 동적 프로그래밍 5문제
    • 다익스트라 5문제

• 3단계 : 현대 모비스 알고리즘 경진대회 대비

  • 6월 30일 대회에 대비해서 일시적으로 해당 단계을 시행한다.

  • 현대 코딩 플랫폼(Softeer)의 level 3 이상 문제를 최소 5문제 푼다.

  • 22년도 현대 모비스 알고리즘 경진대회 기출문제를 푼다.

• 위 과정은 6월 달까지의 계획이고, 그 이후 계획은 추후 세울 예정

2. 코딩 테스트 꿀팁

2.1. 디버깅을 습관화하자!

• 코드 2-3줄 작성 시마다 print()로 출력해서 눈으로 확인
  • 코드 작성 다 하고나서 실행 시 오류 발생하면 오류 찾기가 어렵다.
  • 디버깅을 통해 데이터 입력, 이동 등이 잘 이루어졌는지 확인한다.

2.2. 문제에 답이 있다!

• 완전 탐색 가능 여부 파악
  • 제한 조건 N의 범위(개수) 파악한다.
  • 모든 계산이 1억 번 이내 가능하다면 완전 탐색이 가능하다.
    • 1억 번 이내면 3~5초 계산 소요 (100000000)
  • 1억 번 이내 가능하지 않다면 다른 방법을 추천한다.
• Simulation = 조건 정리
  • 최근 코딩 테스트 동향은 구현 문제가 많다.
  • 조건이 많기 때문에 조건을 잘 정리해서 반영했는지 관건이다.
    • 일반적으로 탐색적 알고리즘을 요구하기도 하지만 해결 방법이나 구조가 자유로움
  • 최초의 조건부터 마지막 조건까지 꼼꼼히 챙겨야 한다.
• 그리디 구별

  • 그리디 알고리즘과 DP 구별하는 것이 중요한데, 이는 직접 많이 풀어봐야 알 수 있다.

    • 그리디 : 현재 상태에서 최고의 선택을 하는 것, 다음 번 상태를 고려하지 않고 영향을 주지 않는다.
    • DP : 현재 상태에서 다음 번 상태를 고려한다.

  • 대표 문제

    • 최소 동전 개수 구하기 : 큰 액수의 동전이 이전 단계의 동전보다 배수일 경우 그리디로 최적해 보장
    • 가방 문제 : 물건을 나눠서 가방을 넣을 수 있다면 그리디로 최적해 보장

    • 회의실 문제 : 하나의 회의실에 여러 개의 회의가 열려야 한다면, 회의가 끝나는 대로 배정하면 그리디로 최적해 보장

    • 최소 신장 트리 : 매 정점에서 가장 작은 가중치를 가진 간선을 선택하여 연결하면 최소 신장 트리 구현을 보장

• 간선 비용에 따른 최단 거리 보장

  • 간선 비용이 동일할 때 : BFS
  • 간선 비용이 다를 때 : 다익스트라, MST 등

3. Python 장점

Python은 완성된 자료구조와 활용성 높은 내장함수를 제공하기 때문에 Python으로 코딩테스트를 준비하면 훨씬 수월하다.

3.1. 자료구조

1) deque

• 리스트 대신에 사용할 수 있는 자료형으로 양방향 큐

• 데이터 추가하거나 제거할 때 리스트보다 효율적

  • 리스트는 리스트 길이인 O(N) 만큼 시간 소요
    • 리스트 길이가 1억 이상일 때 arr[0] 과 같이 간단한 출력도 꽤 오래 걸림
  • deque는 O(1) 만큼 시간 소요

# 자료 생성
from collections import deque
q = deque()

# 값 2 추가
q.append(2)
q.appendleft(2)

# 인덱스 2의 값 제거
q.pop(2)
q.popleft(2)

# 배열 추가
q.extend([1, 2])
q.extendleft([1, 2])

# 제거
q.remove(2)

# 회전
q.rotate(1)

2) heapq

• 리스트를 우선순위 큐처럼 사용할 수 있는 모듈
• 기본은 0번 인덱스의 값이 항상 최소값으로 저장되는 최소 힙이고 우선순위 규칙을 정해줄 수 있음
• heap[0]은 항상 배열의 가장 작은 값

# 자료 생성
import heaqp
lst = list()

# 값 추가
heapq.heappush(lst, 1)

# 값 제거
heapq.heappop(lst, 1)

# heapq 로 변환
heapq.heapify(lst)

# Max Heap 생성
heap = list()
nums = [1, 3, 5, 0, 10, 9]
for num in nums:
  heapq.heappush(heap, (-num, num))

3) defaultdict

• 딕셔너리와 동일한 구조로 만드는 서브 클래스
• 작동 방식은 동일하지만, 초기 자료형 설정 가능
• 사용
  • 그래프 연결 관계 만들 때
  • 키의 개수를 셀 때
  • 리스트/집합 정리할 때

# 자료형 리스트로 고정된 딕셔너리 생성
from collections import defaultdict
dic = defaultdict(list)

# 양방향 그래프 선언
s, e = 1, 2
dic[1].append(2)
dic[2].append(1)

# 모든 원소 확인
dic.items()

# 모든 키 확인
dic.keys()

3.2. 내장함수

1) map

• 여러 개의 데이터를 한 번에 다른 형태로 변환할 때 사용
• map(적용할 함수, iterable 객체)
  • iterable 객체 : 순회 가능한 자료형 객체로 리스트, 집합 등
• 내장 함수, 사용자 정의 함수 등 다양한 함수 적용 가능
• 반환 시 map 객체로 반환
  • 리스트, 튜플 등으로 형 변환 필요

def minus(num):
    return num - 1

lst = [10, 9, 8, 7, 6]
mapped = list(map(minus, lst))
print(mapped)

---
[9, 8, 7, 6, 5]

2) zip

• 여러 개의 데이터를 하나로 묶거나 탐색할 때 사용
  • 리스트의 extend, append는 1000만 개 이상에서 사용을 지양하는데 이 때 zip 사용
• zip(iterable 객체1, 객체2, 객체3, ...)
• 묶으려는 객체들의 길이가 서로 다르더라도 사용 가능
  • 단, 객체들 중 최소 길이로 반환
• 반환 시 zip 객체로 반환
  • 리스트로 형 변환 가능
  • 묶는 객체가 2개면 딕셔너리로 형 변환 가능

a = [5, 3, 2]
b = ['Lily', 'Emily', 'Tom']

for i in zip(a, b):
    print(i)
print(dict(zip(a, b)))

---
(5, 'Lily')
(3, 'Emily')
(2, 'Tom')
{5: 'Lily', 3: 'Emily', 2: 'Tom'}

3) lambda

• 무명 함수로, 사용자 함수를 선언할 필요 없이 일시적으로 필요할 때 사용
• lambda(매개변수1, 매개변수2, ... : 기능)(값1, 값2, ...)
• 주로 정수 반환, T/F 반환
• map, filter, sort 함수와 함께 많이 사용
  • filter(조건/규칙, iterable 객체)
  • sort(key=정렬 기준)
  • 다중 조건 정렬 문제에 많이 활용

# 일반 사용
lambda(x, y : x+y)(10, 20)

# filter : 0부터 10까지 중 6보다 큰 숫자만 추출
result = list(filter(lambda x: x>6, range(10)))
print(result)

# sort : 점수가 높은 사람 순서대로 정렬 (점수가 동일하면 이름 순 정렬)
result = [["tony", 70], ["alice", 90], ["lily", 90], ["james", 100]]
result.sort(key=lambda x: (-x[1], x[0]))
print(result)

---
[7, 8, 9]
[["james", 100], ["alice", 90], ["lily", 90], ["tony", 70]]