희연's 개발 일기장

목차

• 꼭 필요한 자료구조 기초 124
• 탐색 알고리즘 DFS/BFS 134
• [실전 문제] 음료수 얼려 먹기 149
• [실전 문제] 미로 탈출 152

꼭 필요한 자료구조 기초

• 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 대표적인 그래프 탐색 알고리즘 : DFS(Depth First Search), BFS(Breadth First Search)
  • 스택, 큐, 재귀 함수 이해 필요

• 자료구조(Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조
  • 삽입(Push), 삭제(Pop)
  • 스택, 큐를 사용할 경우 삽입, 삭제 이외에도 overflow, underflow 고려 필요
    • 오버플로(Overflow) : 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 경우 발생
    • 언더플로(Underflow) : 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산 수행 시 발생

책에서는 파이썬으로 내용을 다루지만, 자바 기준으로 포스팅하겠습니다.

• 스택(Stack) 
  • 선입후출(First In Out), 후입선출(Last In Frirst Out)
  • stack.push() : 스택에 원소를 삽입한다.
  • stack.pop() : 스택의 맨 위의 원소를 삭제한다.
  • stack.peek() : 스택의 맨 위의 원소를 출력한다.
  • stack.size() : 스택의 크기 출력
  • stack.empty() : 스택이 비어있는지 확인
  • stack.contains() : 함수 안에 있는 인자 값이 스택에 포함되어 있는지 확인
  • stack.clear() : 스택에 있는 모든 데이터를 한 번에 삭제한다.

• 큐(Queue)
  • 선입선출(First In First Out)
  • queue.offer() : 큐에 원소를 삽입
  • queue.pool() : 큐에서 제일 처음(맨 앞)에 넣은 값을 삭제
  • queue.peek() : 값을 삭제하지 않고, 맨 앞의 값을 출력

• 재귀 함수(Recursive Function) 
  • 자기 자신을 다시 호출하는 함수
  • 프랙털(Fractal) 구조와 흡사 : 시에르핀스키 삼각형
  • 종료 조건을 꼭 명시해야 한다.
  • 재귀 함수는 내부적으로 스택 자료구조와 동일하다.
  • ex. factorial : 반복문보다 재귀 함수를 사용한 이점은?
    • 간결한 코드 = 점화식 사용

탐색 알고리즘 DFS/BFS

• 그래프 
  • 노드(Node) = 정점(Vertex)
  • 간선(Edge)
  • 그래프 표현 방식 2가지
    1. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계 표현
    2. 인접 리스트(Adjacency List) : (연결)리스트로 그래프의 연결 관계 표현

• 인접 행렬 vs 인접 리스트
  • 인접 행렬 : 모든 관계를 저장하기 때문에 노드 개수가 많을수록 메모리 낭비
  • 인접 리스트 : 연결된 정보만 저장하기 때문에 메모리 효율적, but 조회 속도 저하

• 그래프 탐색
  • 하나의 노드를 시작으로 다수의 노드를 방문하는 것
  • 두 노드가 간선으로 연결 = 두 노드는 인접하다(Adjacent)

• DFS(Depth-First Search) 깊이 우선 탐색
  • 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드 방문 후, 돌아가서 다른 경로 탐색
  • 데이터 개수가 N개일 경우 시간복잡도 : O(N)
  • 재귀함수 이용
    • 재귀 함수는 스택구조와 동일하지만, 실제로 스택을 사용하지는 않는다.(Stack Overflow)
  • 활용 문제
    • 백트래킹, 위상 정렬
      • 백트래킹 : 해를 찾는 도중, 찾는 해가 아닐 경우 되돌아가서 해를 찾는 방법
  • 동작 과정
    1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
    2. 스택의 최상단 노드에 방문하지 않은 인접 노드(white)가 있으면 그 인접 노드를 스택에 넣고 방문 처리(gray)를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. (방문하지 않은 노드가 여러 개일 경우 번호가 낮은 순서부터 처리)
    3. 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.
  • 노드의 탐색 순서(스택에 들어간 순서) 1->2->7->6->8->3->4->5

• BFS(Breadth First Search) 너비 우선 탐색
  • 가까운 노드부터 탐색하는 알고리즘
  • 시간복잡도 : O(N), 일반적인 경우 실제 수행 시간은 DFS보다 빠르다.
  • Queue 이용(선입 선출 방식)
  • 활용 문제
    • 최단 경로 찾기, 위상 정렬
  • 동작 과정
    1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
    2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 한다. (인접한 노드가 여러 개일 경우, 숫자가 작은 노드부터 먼저 큐에 삽입)
    3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
  • 노드의 탐색 순서(큐에 들어간 순서) 1->2->3->8->7->4->5->6

• DFS vs BFS 방식 비교

• 1차원 배열과 2차원 배열은 그래프의 형태로 바꿔서 생각할 수 있다. (단, 상하좌우로만 이동하는 경우)
• DFS, BFS는 배열로 풀이 가능

실전 문제 (1)

• 음료수 얼려 먹기

• 문제 요약
  • N X M 크기의 얼음 틀
  • 구멍 0, 칸막이 존재 1 
  • 상하좌우로 붙어 있는 경우 연결되어(두 노드가 간선으로 연결) 있는 것으로 간주
  • 생성되는 아이스크림 개수 구하기
  • 위의 문제의 출력 값은 3

• 문제 해설
  • 그래프에서 묶음을 찾아주는 프로그램은 어떻게 작성? -> DFS 사용
    1. 특정한 지점의 주변 상하좌우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점 방문
    2. 방문한 지점에서 다시 상하좌우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문 가능
    3. 1~2번의 과정을 모든 노드에 반복하여 방문하지 않은 지점의 수를 센다.

실전 문제(2)

• 미로 탈출

• 문제 요약
  • N X M 크기의 미로
  • 현재 위치(1, 1)
  • 출구 위치(N, M)
  • 괴물이 있는 부분 0, 괴물이 없는 부분 1
  • 최소 이동 칸의 개수 구하기(시작, 마지막 칸 포함)

• 문제 해설
  • 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드 탐색. 최단 거리 -> BFS 사용
  • (1, 1) 부터 모든 노드의 값을 거리 정보로 넣는다.
  • 특정 노드에 방문할 때 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다.

<참고> DFS와 BFS 시간 복잡도
인접 행렬 : O(N^2)
인접 리스트 : O(N+E)

목차

• 아이디어를 코드로 바꾸는 구현
• [실전 문제] 왕실의 나이트
• [실전 문제] 게임 개발

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

• 구현(Implementation)
  • 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
  • 생각해낸 문제의 풀이 방법을 프로그래밍 언어로 정확히 구현해야 하기 때문에, 언어의 문법을 정확히 알고 있어야 한다.
  • 문제를 잘 읽고 요구사항에 어긋나지 않도록 맞춘다.
  • 이 책에서는 완전 탐색, 시뮬레이션 유형을 '구현' 유형으로 묶어서 다루고 있다.
    • 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
    • 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 ex. 상하좌우

• 구현 시에 고려해야 하는 메모리 제약 사항
  • 예를 들어 int 자료형의 표현 범위는 -2.147,483,648 ~ 2,147,438,647 이며, 이 범위를 어긋나는 큰 수는 처리할 수 없다.
  • long long과 같은 자료형을 사용해야 하지만 9,223,372,036,854,775,807보다 큰 수를 처리할 수 없다.
  • 이보다 더 큰 BigInteger 클래스르 구현하거나 이용해야 하지만, 자바의 경우 표준 라이브러리로 지원을 한다. 하지만 라이브러리를 사용하지 못하는 경우도 있다. 
  • 코딩테스트에서 long long 보다 더 큰 정수를 처리하는 문제는 잘 출제되지 않는다.
  • 파이썬은 직접 자료형을 지정할 필요가 없다고 한다.....

• 자바에서의 리스트 크기(추가 예정)
  • 대체로 코딩 테스트에서는 128~512MB 메모리 제한
  • 복잡한 최적화를 요구하는 문제를 거의 나오지 않는다.
• 채점 환경
  • 시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도는 O(NlongN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다.
• 구현에 접근하는 방법
  • C/C++, 자바로 문제를 풀 경우 구현 유형의 문제는 더 어렵다.
  • 문자열을 처리하거나 큰 정수를 처리하는 문제에서는 파이썬이 더 유용하다.
  • API 개발 문제 또한 구현 유형과 유사한데, 파이썬은 매우 간결하고 직관적인 코드의 라이브러리를 사용할 수 있어 유리하다.

예제1 - 상하좌우

• N X N 크기의 정사각형 공간
• 가장 왼쪽 위 (1, 1) 가장 오른쪽 아래 (N, N)
• 상, 하, 좌, 우 방향으로 이동 가능 -> L 왼쪽, R 오른쪽, U 위로, D 아래로
• 공간에서 벗어나는 움직임은 무시한다. ex. (1, 1)에서 L 혹은 U 는 무시

• 문제 해설
  • 연산 횟수 = 이동 횟수
  • 이동 횟수가 N번일 경우 시간 복잡도 O(N) -> 넉넉한 편

예제2 - 시각

• 정수 N이 입력되면, 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램 구하기
• 00시 00분 03초, 00시 13분 30초

• 문제 해설
  • 모든 시각의 경우를 하나씩 모두 세는 문제 -> 완전 탐색
  • 하루는 86,400초 -> 모든 경우의 수는 86,400가지 밖에 존재하지 않는다.
  • 완전 탐색 알고리즘은 탐색해야 하는 전체 데이터 개수가 100만 개 이하일 경우 가능
  • 이 문제에서는 매 시각을 문자열로 바꾼 후에 1초씩 늘리면서 3이 포함되었는지 탐색한다. 

실전 문제 (1) 

• 왕실의 나이트

• 문제 요약
  • 8 X 8 체스판
  • L자 형태로만 이동 가능하고, 체스판 밖으로 나가지 못한다.
  • 2가지 경우로만 이동
    • 수평으로 두 칸 이동 후 수직으로 한 칸 이동
    • 수직으로 두 칸 이동 후 수평으로 한 칸 이동
  • c2에서 이동할 수 있는 경우의 수는 6가지
  • 입력에서 받은 위치에서 이동할 수 있는 경우의 수를 출력해라

• 문제 해결
  • 상하좌우 문제와 유사
    
  • 평면을 벗어나지 않고, 2가지 경로로 움직일 수 있다.
  • 이동 경로를 steps 변수에 넣으면 2가지 규칙에 따라서
  • (-2, -1), (-1,-2), (2,-1), (2,1), (1,2), (-1,2), (-2,1) 가 나온다.
  • 이 후에 평면 이내에 존재하는지 확인하고, 이 과정은 반복문으로 처리한다.

실전 문제 (2) 

• 게임 개발
  •  

• 문제 요약
  • N X M 크기의 공간
  • 동서남북으로 이동 가능
  • 현재 위치 1 X 1
  • 맵의 각 칸은 (A, B) -> A : 북쪽으로부터 떨어진 칸의 개수 / B :  서쪽으로부터 떨어진 개수
  • 북쪽 0, 동쪽 1, 남쪽 2, 서쪽 3
  • 이동 경로
    • 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다.
    • 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
    • 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.
  • 캐릭터가 방문한 칸의 수를 출력하는 프로그램

• 문제 해결
  • 시뮬레이션 문제
  • 일반적으로 방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적
  • 북쪽을 바라보고 있고, 북쪽으로 이동하기 위해 x와 y좌표를 각각 dx[0], dy[0]만큼 더한다. => 현재 위치에서 (-1,0) 이동
  • 이처럼 반복문 코드를 작성하여 모든 방향을 차례대로 확인한다.

목차

• 당장 좋은 것만 선택하는 그리디
• [실전문제] 큰 수의 법칙
• [실전문제] 숫자 카드 게임
• [실전문제] 1이 될 때까지

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

• 그리디 알고리즘
  • 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘
  • 현재 상황에서 지금 당장 좋은 것만 고르는 방법 -> 최적의 해가 아닌 경우가 많다.
  • 나중에 미칠 영향에 대해서는 고려하지 않는다.
  • 그리디 알고리즘은 코딩테스트에서 정렬 알고리즘과 짝을 이뤄 출제되는 경우가 많다.
    • 가장 큰 순서대로, 가장 작은 순서대로 등
    • 거스름돈
      • 500원, 100원, 50원, 10원 동전이 있을 경우 손님에게 거슬러줘야 하는 동전의 최소 개수
      • 해결 방법 : 가장 큰 화폐 단위부터 돈을 거슬러 준다.
      • 화폐의 종류만큼 반복 수행 -> 화폐의 종류가 K일 경우 -> 시간 복잡도 O(K)
      • 큰 단위가 항상 작은 단위의 배수 형태이므로, 최적의 해를 보장 가능
  • 코딩테스트 문제를 보고, 유형 파악이 어려울 경우 그리디 알고리즘으로 해결법을 찾아보고, 방법을 찾을 수 없으면 DP나 그래프 알고리즘 등으로 문제 해결 방법을 찾아본다.

실전문제 (1)

• 큰 수의 법칙

• 문제 요약
  • 다양한 수로 이루어진 배열이 주어질 때 수들을 M번 더하여 가장 큰 수를 만든다.
  • 특정한 인덱스가 연속 K번을 초과하면 안된다.
  • 2, 4, 5, 4, 6으로 이루어진 배열일 경우 M이 8이고, K가 3일 경우
  • 6 + 6 + 6 + (3연속X) 5 + 6 + 6 + 6 + (3연속X) + 5 = 46
  • 3, 4, 3, 4, 3으로 이루어질 경우 4 + 4 + 4 + 4 + 4 + 4 가능

• 문제 해설
  
  • 입력 값 중에서 가장 큰 수와 두 번째로 큰 수만 저장한다.
  • 가장 큰 수를 K 번 더하고, 두 번째 큰 수를 한 번 더하는 연산 반복
  • M의 크기가 100억처럼 커질 경우, 시간 초과
  • 예시로 가장 큰 수 6, 두 번째로 큰 수 5, M이 8, K가 3이면 반복되는 수열이 존재한다 (6+6+6+5)*2
  • 이러한 문제에서 가장 먼저 반복되는 수열에 대해서 파악하는 것이 중요
  • 반복되는 수열의 길이 = K+1
  • M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수
  • 반복 횟수에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 된다.

<가장 큰 수가 더해지는 횟수> int (M / (K+1)) * K + M & (K+1) 

실전 문제 (2)

• 숫자 카드 게임

• 문제 요약
  • 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장 뽑기
  • N X M 개의 카드
  • 먼저 뽑으려는 카드가 포함된 행 선택
  • 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드 뽑기
  • 행을 선택할 때, 가장 숫자가 낮은 카드를 뽑는 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있는 전략 세우기
  • 1, 2번째 행을 선택하는 경우 최종적으로 뽑는 카드 1
  • 3번째 행을 선택하는 경우 최종적으로 뽑는 카드 2
  • 따라서 세번째 행을 선택 후 숫자 2가 쓰인 카드를 뽑는 것이 정답

• 문제 해설
  • 각 행마다 가장 작은 수를 찾은 뒤, 그 수 중에서 가장 큰 수를 찾는다.

Collections.max(list); // 리스트에서 최대 값을 출력
Collections.min(list); // 리스트에서 최소 값을 출력

실전 문제 (3)

• 1이 될 때까지

• 문제 요약
  • 어떤 수 N이 1이 될 때까지 아래의 과정 중 하나를 반복적으로 수행
  • 두 번째 연산은 N이 K으로 나누어 떨어질 때만 선택 가능
    1. N에서 1을 뺀다.
    2. N을 K로 나눈다.
  • N 17, K 4일 경우, 1번 과정 수행 시 N은 16 
  • 2번 과정을 두 번 수행 시 N은 1
  • 결과적으로 전체 과정 실행 횟수 3

• 문제 해설
  • 주어진 N에 대하여 '최대한 큰 수로 나누기'를 수행