1

코딩 테스트 합격을 위한

2023년 연말 특강

영상은 차주 유투브에 업로드될 예정입니다.

https://www.youtube.com/channel/UCulplOST7XpLnc6xxNFEAoQ

2

3

• 이 책의 저자 박경록입니다.
• 코딩 테스트 외의 지식을 나누는 것을 좋아합니다.
• MBTI가 ESTJ 입니다.
• 게으른 개발자를 좋아합니다.

4

저는…

5

6

1. 이 책을 쓰게 된 이유

“친절한 책을 쓰고 싶었습니다.”

7

1. 이 책을 쓰게 된 이유

“선배의 머릿 속이 궁금했습니다.”

8

1. 이 책을 쓰게 된 이유

“다시 꺼낼 수 있는 책을 만들고 싶었습니다.”

9

10

2. 이 책의 특징과 장점, 대상 독자

• 파이썬의 기본 문법을 이해한 사람 대상으로 집필
• 파이썬 기본 문법이 약해도 충분히 공부할 수 있도록 지원
• 깃허브에 충분한 자료를 지원

11

기본적인 자료구조/알고리즘 코드

​

꼭 알아야 할 개념이 포함된 코드

(성능측정/자주실수하는 코드 등)

책에 있는 문제의 정답코드

2. 이 책의 특징과 장점, 대상 독자

• 그림을 충분히 사용
• 알고리즘, 입력값을 받고 원하는 출력값을 만드는 과정
• 이 과정을 충분히 도식화

12

2. 이 책의 특징과 장점, 대상 독자

• 바로 정답 코드를 해석하지 않았음
• 중요한 건 문제를 분석하고 해석하는 능력
• 데이터가 제어되는 과정
• 문제 분석, 설계할 수 있는 능력을 공부할 수 있도록 배려

13

2. 이 책의 특징과 장점, 대상 독자

• 알고리즘 및 자료구조 설명
• 연산의 흐름을 충분히 파악할 수 있도록 각 과정들을 상세히 설명
• 개념 설명
• 바로 기출 문제로 가지 않음, 중간 문제를 반드시 배치(저자 기출 문제)
• 개념을 충분히 익히면서 구현해볼 수 있도록 배려
• 실전 문제는 프로그래머스에서 검수한 문제를 다루고 있음
• 트렌드를 반영하고 있어 감각을 익히기 좋음

14

15

3. 코딩 테스트 마인드셋

• 조급하게 하지 말자
• 어차피 단기간에 할 수 없음
• 조급하면 소중한 시간만 낭비할 따름
• 최소한 3개월은 필요, 시간이 충분히 필요함을 인정하고 인내를 가지고 준비

16

3. 코딩 테스트 마인드셋

• 모든 알고리즘을 다 알아야 한다는 생각을 버리자
• 많이 알면 좋음(당연)
• but… 알고리즘은 끝이 없고, 공부 시간은 제한되어 있음
• 전략적으로 접근 ➝ 트렌드는 많이 바뀌지 않음 ➝ 빈출 알고리즘 위주로 공부

17

3. 코딩 테스트 마인드셋

• 사공이 많으면 배가 산으로 가죠
• 주변 친구의 말 너무 따르지 말 것
• 주관을 가지고 공부
• 대부분 나와 실력 차이가 그렇게 많이 나지 않음
• 목표를 명확히, 내가 할 것들에 집중, 꾸준히

18

3. 코딩 테스트 마인드셋

• 피드백 받기를 두려워 하지 말자
• 내가 공부한 내용을 많이 공개하자, 피드백을 많이 받자
• 질문을 많이 하자(질문 가이드)
• 질문을 정리하고 공유하는 건 귀찮다, 근데 공부가 원래 귀찮다(인정하자)
• 피드백을 위해 들이는 시간을 아까워 하지 말자
• 피드백을 통해 잃는 것보다 얻는 게 더 크다
• 질문/요청을 작성하면 본인이 한번 읽어보자

19

20

4. 2023 코딩 테스트 트렌드, 2024는?

• 코딩 테스트 경향은 바뀌지 않음
• 코딩 테스트는 개발자의 기본 능력을 평가하는 시험
• 특정 알고리즘을 알아야 풀 수 있는 문제 X
• 문제를 정확히 이해하고 요구사항을 빠짐없이 구현하는 문제 O

21

4. 2023 코딩 테스트 트렌드, 2024는?

• 탐색
• 단순한 반복 탐색 多
• DFS(스택, 재귀) / BFS / 백트래킹 多
• 대표 문제(풀어보면 좋음)(책에도 있음)
• 반복 탐색 문제 : 모의고사(문제 4, 정답코드)
• DFS 문제 : 네트워크(문제 43, 정답코드) , 전력망 둘로 나누기(문제 46, 정답코드)
• BFS 문제 : 경주로 건설(문제 45, 정답코드)
• 백트래킹 문제 : 스도쿠 퍼즐(문제 48,정답코드), 피로도(문제 49, 정답코드)

22

4. 2023 코딩 테스트 트렌드, 2024는?

• 시뮬레이션
• 특정 알고리즘 적용 X
• 이해한 대로 구현 O
• 좌표 / 배열 / 구현
• 대표 문제(풀어보면 좋음)(책에도 있음)
• 좌표 문제 : 캐릭터의 좌표(문제 69, 정답 코드)
• 배열 문제 : 배열 회전(문제 62, 정답 코드), 전치 행렬(문제 63, 정답 코드)
• 구현 문제 : 카펫(문제 67, 정답 코드), 점프와 순간이동(문제 68, 정답 코드)

23

4. 2023 코딩 테스트 트렌드, 2024는?

• 자료구조 응용
• 스택 / 큐 / 딕셔너리 / 우선순위 큐
• 포인트 : 동일한 동작을 하지만 성능이 다른 메서드 정리 필요
• 메서드 선택이 당락 결정
• 주요 메서드 : pop(0) vs popleft() , append() vs + 연산자, join() vs + 연산자
• 대표 문제(풀어보면 좋음)(책에도 있음)
• 스택 문제 : 짝지어 제거하기(문제 11, 정답 코드), 주식 가격(문제 12, 정답 코드)
• 큐 문제 : 요세푸스 문제(문제 15, 정답 코드), 기능 개발(문제 16, 정답 코드)
• 딕셔너리 문제 : 완주 하지 못한 선수(문제 20, 정답 코드), 오픈 채팅방(문제 22, 정답 코드)
• 우선순위 큐 문제 : 지형 이동(문제 61, 정답 코드)

24

4. 2023 코딩 테스트 트렌드, 2024는?

• 기타 알고리즘
• 고득점을 위해 필요한 알고리즘, but…
• 코딩 테스트에서 꼭 고득점을 노릴 필요는 없음
• 만약 더 공부해야 한다면…
• 최단 경로 / 트리 / 그리디 / 동적 계획법 등의 알고리즘
• 대표 문제(풀어보면 좋음)(책에도 있음)
• 최단 경로 문제 : 다익스트라 알고리즘(문제 40, 정답 코드), 배달(문제 44, 정답 코드)
• 그리디 문제 : 거스름돈 주기(문제 80, 정답 코드), 기지국 설치(문제 85, 정답 코드)
• 트리 문제 : 트리 순회(문제 26, 정답 코드), 예상 대진표(문제 28, 정답 코드)
• 동적 계획법 문제 : 2xn 타일링(문제 74, 정답 코드), 도둑질(문제 77, 정답 코드)

25

26

5. 자료구조 + 알고리즘 주요 개념 4가지

• 시간 복잡도^{time complexity}
• 코딩 테스트에서 왜 시간 복잡도가 중요한가?
• 시간 복잡도를 어떻게 측정할 것인가?(기본)
• 점근적 표기법
• 시간 복잡도를 코딩 테스트에 어떻게 적용할 것인가?(실전)
• 연산 횟수로 알고리즘 선택
• 입력값으로 알고리즘 선택

27

5. 자료구조 + 알고리즘 주요 개념 4가지

• DFS and BFS
• DFS와 BFS의 개념, 구현, 응용
• DFS와 BFS의 비교

28

5. 자료구조 + 알고리즘 주요 개념 4가지

• 다익스트라
• 최단 경로를 구한다는 것은 무엇인가?
• 다익스트라의 목적은 무엇인가?
• 다익스트라의 세부 동작
• 다익스트라의 한계
• 벨만-포드 알고리즘

29

5. 자료구조 + 알고리즘 주요 개념 4가지

시간 복잡도

왜 코딩 테스트에서 시간 복잡도가 중요할까?

30

5. 자료구조 + 알고리즘 주요 개념 4가지

• 코딩테스트에서 합격하려면 “정확성”뿐 아니라 “효율성”까지 만족해야 함, 시간복잡도는 “효율성”을 측정하는 수단
• “정확성”은 각 입력값에 대해 실행한 코드와 테스트 케이스의 출력값을 비교해서 일치하는지 확인
• “효율성”은 출제자가 의도하는 시간복잡도 내로 코드가 수행되는지 확인

​

31

기준 수행시간

코드제출

수행시간 측정

비교

기준 수행시간에 각 언어마다 정한 상수를 곱한 시간 이내로 수행되는지 확인

5. 자료구조 + 알고리즘 주요 개념 4가지

시간 복잡도

어떻게 측정할 것인가?

32

5. 자료구조 + 알고리즘 주요 개념 4가지

• 성능은 “연산 횟수”를 기준으로 측정

​

33

코드 실행

입력

출력

코드 실행하는 동안 연산횟수를 측정

5. 자료구조 + 알고리즘 주요 개념 4가지

• 성능은 “연산 횟수”를 기준으로 측정 - 간단한 예시(순차탐색으로 배열 원소 찾기)

​

34

1

4

2

3

7

8

9

5

배열 원소에 내가 원하는 값이 있는지 탐색

연산횟수 측정

어느정도 연산이 소요되는지는 알수있다. 하지만 그래서 성능이 정확히 어떻다는 것인가?

5. 자료구조 + 알고리즘 주요 개념 4가지

• 시간 복잡도는 “연산 횟수”를 기준으로 성능을 일반화 함
• 세부적인 “연산 횟수”를 모두 표기하는 것보다 “영향을 가장 많이 끼치는 상한”을 표시(점근적 표기법의 Big-O 표기법)

​

35

연산횟수는 n^2 + 3n + 5

n^2

3n

1. n이 커질수록 차수는 의미없음
2. n이 커질수록 3n과 5는 무시할 수 있음

즉 n^2이 절대적으로 많은 영향을 미침

​

​

시간 복잡도는 Big-O 표기로 O(n^2)가 됨

5. 자료구조 + 알고리즘 주요 개념 4가지

• 진짜 “영향을 끼치는 부분”만 표시해도 문제 없을까?

​

36

x좌표가 다름을 유의

전체 그래프

복잡도 O(nlogn 미만 그래프)

5. 자료구조 + 알고리즘 주요 개념 4가지

• 빅오 표기법을 연습해 봅시다.

​

37

선형탐색,O(x)

행렬곱셈O(x^2)

부분 집합,O(2^x)

트리탐색, O(logx)

5. 자료구조 + 알고리즘 주요 개념 4가지

시간 복잡도

어떻게 사용할 것인가?

38

5. 자료구조 + 알고리즘 주요 개념 4가지

• 문제에 주어지는 입력값으로 사용할 수 있는 알고리즘 추정 가능
• 입력값은 많은 힌트를 제공 함. 하지만 시간복잡도를 알아야 이 힌트를 활용할 수 있음.

​

39

O(N^2) 알고리즘으로 풀면 통과하지 못하겠구나!

정답 코드

복잡한 알고리즘을 생각하지 않고, 그냥 구현하면 되겠구나!

정답 코드

5. 자료구조 + 알고리즘 주요 개념 4가지

• 책에 있는 각 자료구조/알고리즘의 시간복잡도를 정리하는게 최우선 입니다!
• 동일한 동작을 하는데 성능이 다른 메서드도 정리가 필요합니다!
• 문제 입력값 분석시 여유 있게 초당 연산횟수를 1,000만 ~ 3,000만 이라고 생각하면 됩니다.

40

5. 자료구조 + 알고리즘 주요 개념 4가지

DFS와 BFS

왜 코딩테스트에 많이 나오는가?

41

5. 자료구조 + 알고리즘 주요 개념 4가지

• 코딩테스트는 “알고리즘 지식 평가”가 목적이 아닌, “문제 해결 능력”을 평가하는 시험
• “DFS와 BFS”는 기본적인 자료구조 지식만 있으면 구현할 수 있는 알고리즘이면서, 문제 분석이 제대로 되지 않으면 실수하는 경우가 많아서 시험에 적합

​

42

스택

큐

def a():

a()

재귀

먼저 공부하기

DFS와 BFS중 어떤걸 사용할 것인가?

- 최단경로를 찾는 문제는 BFS

- 백트레킹이 필요한 문제는 DFS

문제 분석하기

5. 자료구조 + 알고리즘 주요 개념 4가지

DFS와 BFS

반드시 알아야 할 사전지식

43

5. 자료구조 + 알고리즘 주요 개념 4가지

• 사진 지식 공부하기 - 스택과 큐

​

44

스택

FILO

코드

푸시

푸시

푸시

팝

팝

팝

큐

FIFO

코드

푸시

푸시

푸시

팝

팝

팝

5. 자료구조 + 알고리즘 주요 개념 4가지

• 사진 지식 공부하기 - 함수호출흐름 및 재귀함수

​

① functionA 호출

② functionB 호출

③ functionB 다음으로 감

함수호출 흐름

재귀함수

재귀호출

종료조건

5. 자료구조 + 알고리즘 주요 개념 4가지

DFS와 BFS

DFS 알고리즘

46

5. 자료구조 + 알고리즘 주요 개념 4가지

• DFS(깊이우선탐색)
• 시작 노드를 정합니다.
• 더 이상 탐색할 노드가 없을 때 까지 갑니다.
• 더 이상 탐색할 노드가 없으면 최근에 방문할 노드로 되돌아가서 가지 않은 노드로 탐색을 계속 합니다.(백트래킹)

​

백트래킹

백트래킹

탐색할 노드가 없을 때까지 감

5. 자료구조 + 알고리즘 주요 개념 4가지

• DFS(깊이우선탐색) 구현하기
• DFS의 핵심인 백트래킹 부터 봅시다.
• 백트래킹을 어떻게 구현해야 할까요? -> 스택을 활용 -> 콜스택 자체가 스택이므로 재귀를 활용!

스택을 활용한 DFS 예시코드 재귀를 활용한 DFS 예시코드

​

A

B

D

A

B

D

D

A

B

B

최근 방문 노드

최근 방문 노드

5. 자료구조 + 알고리즘 주요 개념 4가지

• DFS(깊이우선탐색) 구현하기
• DFS를 재귀로 구현해봅시다
• 시작노드를 정하고, 아직 방문하지 않은 노드를 탐색하는 과정을 재귀적으로 반복합니다.
• 더이상 방문할 노드가 없다면, 최근방문한 노드를 방문해서 위 과정을 반복합니다.

​

​

그래프로 나타내면

1번 노드를 시작으로 DFS

방문

인정한 노드가 있을 경우 해당 노드를 dfs(재귀)

5. 자료구조 + 알고리즘 주요 개념 4가지

• DFS(깊이우선탐색) 실제동작(cont’d 1/4)

​

​

​

5. 자료구조 + 알고리즘 주요 개념 4가지

• DFS(깊이우선탐색) 실제동작(cont’d 2/4)

​

​

5. 자료구조 + 알고리즘 주요 개념 4가지

• DFS(깊이우선탐색) 실제동작(cont’d 3/4)

​

​

5. 자료구조 + 알고리즘 주요 개념 4가지

• DFS(깊이우선탐색) 실제동작(cont’d 4/4)

​

​

5. 자료구조 + 알고리즘 주요 개념 4가지

DFS와 BFS

BFS 알고리즘

54

5. 자료구조 + 알고리즘 주요 개념 4가지

• BFS(너비우선탐색)
• 시작 노드를 정합니다.
• 방문한 노드와 인접한 노드를 방문합니다.
• 각 방문한 노드의 인접한 노드를 모두 방문하고, 이를 반복합니다.

​

5. 자료구조 + 알고리즘 주요 개념 4가지

• BFS(너비우선탐색) 구현하기
• BFS의 핵심인 인접한 노드를 모두 방문하는 걸 봅시다.
• 인정합 노드를 방문하는 동작은-> 큐를 활용 하면 됩니다.

큐를 활용한 BFS 예시코드

​

B

C

B

D

B

E

D

E

B와 인접

C

C

D

D

E

E

5. 자료구조 + 알고리즘 주요 개념 4가지

• BFS(너비우선탐색) 구현하기
• BFS를 재귀로 구현해봅시다
• 시작노드를 큐에 넣고 방문 처리합니다.
• 큐에에 노드를 하나꺼내고 방문X 한 노드중 인접한 노드를 방문처리하고 푸시합니다. 이를 반복합니다.

​

​

그래프로 표현하면

1번 노드를 시작으로 BFS

방문

인접한 노드를 모드 순회하며, 방문 X 한 경우 방문처리하고 푸시

5. 자료구조 + 알고리즘 주요 개념 4가지

• BFS(너비우선탐색) 실제동작(cont’d 1/2)

​

​

​

5. 자료구조 + 알고리즘 주요 개념 4가지

• BFS(너비우선탐색) 실제동작(cont’d 2/2)

​

​

​

5. 자료구조 + 알고리즘 주요 개념 4가지

DFS와 BFS

DFS vs BFS

60

5. 자료구조 + 알고리즘 주요 개념 4가지

• DFS(깊이우선탐색) vs BFS(너비우선탐색)
• DFS만 백트래킹이 있다.
• BFS가 찾은 해는 시작노드와 가장 가까운 해 라는 것이 보장 된다. (최단 경로)
• BFS는 인접한 노드를 모두 큐에 담는 방식이다(메모리를 더 많이 사용함)

​

해

해

BFS가 찾는해

DFS가 찾는해

앞

뒤

앞

뒤

앞

뒤

2개 동전 앞뒤 모든 경우 확인-백트래킹

해가 2개있는 경우 DFS vs BFS

5. 자료구조 + 알고리즘 주요 개념 4가지

다익스트라 알고리즘

최단경로란 무엇인가?

62

5. 자료구조 + 알고리즘 주요 개념 4가지

• 최단경로란 무엇인가?
• 출발지 부터 목적지 까지 가는데 필요한 가중치의 합이 최소인 경로

63

A

C

B

E

D

2

5

6

8

4

1

2

4

왼쪽 그래프는 이렇게 해석 할수 있다

​

- A에서 D까지 최단 경로는 {A, E, C, D}이다.

- A에서 D까지 최단 경로 길이는 11이다.

- A에서 D까지 최단 경로로 갈때 C의 직전

노드는 E이다.

- A에서 C까지 최단 경로는 {A,E,C}이다.

- A에서 D까지 최단 경로는

A에서 C까지 최단 경로에 C에서 D까지

가중치를 더한 것과 같다.

​

5. 자료구조 + 알고리즘 주요 개념 4가지

• 최단경로 구하기전 고민할 것(과정을 어떻게 표기할 것인가?)
• 효율적으로 구하기 위해 그래프에 아래와 같이 (최단경로길이/최단경로)를 표기

64

A

D

B

C

20

15

900

50

현재까지 구한, 최단경로의 길이

최단 경로를 구성하는 직전 노드

최단경로를 구하기 위해 초기화!

5. 자료구조 + 알고리즘 주요 개념 4가지

다익스트라 알고리즘

최단경로를 어떻게 구할 것인가?

65

5. 자료구조 + 알고리즘 주요 개념 4가지

• 최단경로를 실제 구해보자(어떻게 구할 것인가? 1/2)
• 최단경로 배열에서 길이가 최소인 정점은 추후 갱신될 여지가 없음
• 이를 “거치는 노드”로 정의
• 현재까지 구한 최단경로의 길이와, 거치는 노드를 통한 최단경로를 비교해서 최소로 갱신

​

66

A

F

B

C

20

15

900

50

현재 최단경로 배열에서 길이가 최소,”거치는 노드”

-> 거치는 노드를 통한 경로를 체크하는게 최선(그리디적 선택)

각 최단경로는 “거치는 노드”보다 적을수 없음

-> 조합해도 “거치는 노드”보다 적어질수 없음

5. 자료구조 + 알고리즘 주요 개념 4가지

• 최단경로를 실제 구해보자(어떻게 구할 것인가? 2/2)
• 최단경로 배열에서 길이가 최소인 정점은 추후 갱신될 여지가 없음
• 이를 “거치는 노드”로 정의
• 현재까지 구한 최단경로의 길이와, 거치는 노드를 통한 최단경로를 비교해서 최소로 갱신

​

67

A

D

B

C

20

15

900

50

5. 자료구조 + 알고리즘 주요 개념 4가지

• 최단경로를 실제 구해보자(실제 구하는 과정 1/3)
• 현재 시작노드로 부터 최단 거리의 노드는 “A”이므로 이를 거치는 노드로 선정
• 거치는 노드를 통해 {B,D} 최단경로 정보 갱신

​

68

A

D

B

C

20

15

900

50

① 현재까지 구한 최단거리중 “A”가 최소

② A가 “거치는 노드”가 됨

INF > (0 + 15)

INF > (0 + 20)

5. 자료구조 + 알고리즘 주요 개념 4가지

• 최단경로를 실제 구해보자(실제 구하는 과정 2/3)
• 현재 시작노드로 부터 최단 거리의 노드는 “B”이므로 이를 거치는 노드로 선정
• 거치는 노드를 통해 {B,D} 최단경로 정보 갱신

​

69

A

D

B

C

20

15

900

50

① 현재까지 구한 최단거리중 “B”가 최소

② A가 “거치는 노드”가 됨

* “A”를 거치는건 이미 했으므로 제외

INF > (15 + 900)

5. 자료구조 + 알고리즘 주요 개념 4가지

• 최단경로를 실제 구해보자(실제 구하는 과정 3/3)
• 이전과 같이 반복하면 최종적으로 아래와 같은 테이블이 완성 됨
• 시작 노드부터 모든 노드까지 최단 경로 및 길이가 구해짐

​

70

A

D

B

C

20

15

900

50

D <- C <- A

C <- A

B <- A

A <- A

5. 자료구조 + 알고리즘 주요 개념 4가지

• 다익스트라는 언제설명하죠? -> 지금 까지 한게 “다익스트라 알고리즘” 입니다. 특징을 정리해봅시다.
• 시작노드에서 모든 노드까지 최단경로 및 길이를 구함
• 매번 아직 선택하지 않은 노드에서 “거치는 노드”를 선택 후, 갱신할 최단경로가 있는지 확인하는 방식(그리디적 선택)
• “직전 노드” 과 “현재 노드가 동일할 때까지 계속 이어 가면 “최단 경로”를 알 수 있음

​

71

A

D

B

C

20

15

900

50

D <- C <- A

C <- A

B <- A

A <- A

5. 자료구조 + 알고리즘 주요 개념 4가지

다익스트라 알고리즘

다익스트라를 사용할때 주의할 점

72

5. 자료구조 + 알고리즘 주요 개념 4가지

• 다익스트라의 한계
• 음의 가중치가 있는 경우, 순간 선택이 최선이라고 보장 할수 없음
• 음의 가중치가 있을 경우, “밸만 포드 알고리즘”으로 풀이

​

​

73

A

B

C

8

-500

4

D

10

맨 처음 거치는 노드는 “C”이고 이때 경로길이는 4임

하지만 추후 “C”까지 가는 더 짧은 경로가 발생 함

5. 자료구조 + 알고리즘 주요 개념 4가지

• 이제 정리가 되었으니, 조금 더 복잡한 그래프를 가지고 해볼까요?(1/7)
• 시작노드의 최소비용은 0, 직전노드는 시작노드로 설정

​

74

5. 자료구조 + 알고리즘 주요 개념 4가지

• 이제 정리가 되었으니, 조금 더 복잡한 그래프를 가지고 해볼까요?(2/7)
• 거치는 노드 “A”를 통해 최단경로 갱신

​

75

5. 자료구조 + 알고리즘 주요 개념 4가지

• 이제 정리가 되었으니, 조금 더 복잡한 그래프를 가지고 해볼까요?(3/7)
• 거치는 노드 “E”를 통해 최단경로 갱신

​

76

5. 자료구조 + 알고리즘 주요 개념 4가지

• 이제 정리가 되었으니, 조금 더 복잡한 그래프를 가지고 해볼까요?(4/7)
• 거치는 노드 “C”를 통해 최단경로 갱신

​

77

5. 자료구조 + 알고리즘 주요 개념 4가지

• 이제 정리가 되었으니, 조금 더 복잡한 그래프를 가지고 해볼까요?(5/7)
• 거치는 노드 “B”를 통해 최단경로 갱신(갱신할 경로 없음)

​

78

5. 자료구조 + 알고리즘 주요 개념 4가지

• 이제 정리가 되었으니, 조금 더 복잡한 그래프를 가지고 해볼까요?(6/7)
• 거치는 노드 “D”를 통해 최단경로 갱신(갱신할 경로 없음)

​

79

5. 자료구조 + 알고리즘 주요 개념 4가지

• 이제 정리가 되었으니, 조금 더 복잡한 그래프를 가지고 해볼까요?(7/7)
• 시작노드 “A”에서 각 노드에 대한 최단경로 및 길이가 구해짐

​

80

81

6. 코딩 테스트 주요 문제 풀이 2가지

실전문제 #1 - 짝지어 제거하기

문제 분석

82

6. 코딩 테스트 주요 문제 풀이 2가지

83

5분간 생각해봐요

6. 코딩 테스트 주요 문제 풀이 2가지

84

① 알파벳 2개가 붙은 짝 찾음

② 둘을 제거

③ 나머지 문자열 붙임

시간복잡도가 O((len(s)^2)일 경우 시간초과

쓸데 없는 고민은 최대한 줄일수 있음(숫자,특수문자,대문자 고려할 필요가 없음)

6. 코딩 테스트 주요 문제 풀이 2가지

• 문제 분석
• 문제 요약
• 소문자로 주어진 문자열의 인접한 문자를 삭제해가면서, 문자열이 전부 삭제가능한지 확인
• 사용할 알고리즘
• 문자 삭제 후, 가장 최근의 문자로 돌아가서 다시 탐색하므로 ‘스택”을 활용
• 중요한 조건
• 입력값이 최대 100만이므로 O(N^2)알고리즘 사용시 TLE 가능 O(NlogN) 내 알고리즘 고려
• Only 소문자 이므로, 다른 문자가 들어오는건 고려하지 않음

​

85

6. 코딩 테스트 주요 문제 풀이 2가지

실전문제 #1 - 짝지어 제거하기

문제 풀이

86

6. 코딩 테스트 주요 문제 풀이 2가지

• 문제 접근하기(일단 도식화 해봅니다)

​

87

b

a

a

b

a

a

아래 1)과 2)를 붙인다

1) 없어지는 문자열 이전 문자 중, 가장 최근 문자 ‘b’

2) 없어지는 문자열 바로 다음 문자 ‘b’

b

b

a

a

​

1) 없어지는 문자열 이전 문자가 없으므로, 없어지는 문자열 이후 문자 ‘a’ 부터 시작

a

a

1) 없어지는 문자열 이전 문자가 없으므로, 없어지는 문자열 이후 문자 ‘b’ 부터 시작

6. 코딩 테스트 주요 문제 풀이 2가지

• 문제 접근하기(어떻게 구현할지 고민 해봅시다)
• 중간 문자열이 삭제된 후 처리를 어떻게 할 것인가?(1 / 3)
• copy-move 방식은 사람에게 쉬우나, 컴퓨터가 수행시 연산횟수가 많아짐

​

88

뒤에 있는 문자열을 그대로 붙이면 .. copy-move가 됩니다. O(N^2), TLE 가능성 존재

b

a

a

x

…..

a

0

1

2

3

N

6. 코딩 테스트 주요 문제 풀이 2가지

• 문제 접근하기(어떻게 구현할지 고민 해봅시다)
• 중간 문자열이 삭제된 후 처리를 어떻게 할 것인가?(2 / 3)
• 삭제 시, 이전 문자만 알면 됨(전체 문자열을 매번 제어할 필요가 없음)

​

89

copy-move 하지 않고 중간 문제열 삭제 후 “b”와 비교할수 있으면 됨

-> 삭제되기 전 “가장 최근” 문자열을 알면 됨, LIFO 방식의 스택이 적절함

​

b

a

a

x

…..

a

0

1

2

3

N

b

a

같지 않으면 push

b

a

a

같으면 pop

b

x

같지 않으면 push

스택을 활용하도록 개선(Copy move가 없음)

문자열을 전부 순회했을때 스택에 문자가 남아있으면 처리가 완료됨

6. 코딩 테스트 주요 문제 풀이 2가지

• 실제 코드

5. 자료구조 + 알고리즘 주요 개념 4가지

실전문제 #2 - 게임 맵 최단 거리

문제 분석

91

6. 코딩 테스트 주요 문제 풀이 2가지

92

5분간 생각해봐요

6. 코딩 테스트 주요 문제 풀이 2가지

93

DFS가 아닌 BFS를 써야 한다

대각선으로는 움직일 수 없다

맵을 벗어날수 없으므로 불가능

도착할 수 없는 경우도 입력에 주어짐

이게 더 빨리 도착하는데?

이러는 순간 망합니다!

6. 코딩 테스트 주요 문제 풀이 2가지

n*m하면 최대 칸이 10,000개 까지 될수 있음

성능을 크게 고민하지 않고 탐색 알고리즘으로 접근 가능

사실 당연한 얘기 입니다. 단순히 미로 크기인데 다를 수 없다는게 이상합니다.

너무 시간은 뺐기지 않되, 뭘 의미하나 한번 고민해보는 정도면 됩니다.

배열은 (0,0) 시작하므로 헷갈리지 않도록 중요 표시해두면 좋음

6. 코딩 테스트 주요 문제 풀이 2가지

• 문제 분석
• 문제 요약
• 시작점에서 종료지점까지 이동 할때, 최단거리
• 사용할 알고리즘
• 최단 거리를 구해야 하므로 “BFS” 알고리즘을 사용
• 중요한 조건
• 8방향이 아닌 4방향으로만 이동 가능
• 맵 밖으로 벗어날 수 없음
• 도착지점이 없는 미로가 있을수 있음(이 미로가 없다는 제약사항 없음)

​

95

6. 코딩 테스트 주요 문제 풀이 2가지

실전문제 #2 - 게임 맵 최단 거리

문제 풀이

96

6. 코딩 테스트 주요 문제 풀이 2가지

• 미로 찾는 과정을 도식화 해봅시다.
• BFS와 유사함

97

상하좌우 이동을 그래프로 표현

맵 밖을 벗어나면 더이상 탐색하지 않음

맵 밖을 벗어나면 더이상 탐색하지 않음

하

상

상

좌

좌

우

우

하

굳이 돌아가는 걸 체크할 필요 없음(이미 방문여부 체크 필요)

…

…

…

…

…

6. 코딩 테스트 주요 문제 풀이 2가지

• 도식화 한 과정을 표현하기 위해 필요한 것을 정리해 봅시다.(BFS를 하되, 최단거리를 저장하면서 함)
• 이미 방문한 노드인지 확인할 수 있어야 함(distance)
• 현재 위치를 몇번의 이동으로 확는지 확인할 수 있어야 함(distance)
• 상하좌우 이동 가능해야 함

maps

distance

현재 방문하지 않았으면 X

방문 했으면 시작점부터 현재 위치까지 거리

move

6. 코딩 테스트 주요 문제 풀이 2가지

• 실제 코드

Q&A

• 문제를 풀때 시간관리는 어떻게 하나요?
• 코딩 테스트 언어 선택은 어떻게 해야 하나요?
• 문제를 풀 때 어떤알고리즘을 활용해야 하는지 빠르게 접근하는 방법을 알 수 있을까요?
• 알고리즘 처음 시작부터 지금까지 고난에서 대처한 마음가짐이 궁금합니다.
• 코딩테스트와 면접에 대한 공부 방식이 조금 달라야 할까요?
• ​

​

100

저자와 소통하기

• 저자가 직접 답변하는 오픈채팅방
• 책과 같이 공부할 수 있는 코드자료
• 코딩 테스트 합격자 되기 - 파이썬 편 구매하기
• 저자가 직접 관리하는 커뮤니티 공간(네이버 카페)

101