희연's 개발 일기장

목차

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

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

• 구현(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에 대하여 '최대한 큰 수로 나누기'를 수행