흰연
2022. 1. 17. 19:36
2022. 1. 17. 19:36
목차
- 아이디어를 코드로 바꾸는 구현
- [실전 문제] 왕실의 나이트
- [실전 문제] 게임 개발
아이디어를 코드로 바꾸는 구현
- 구현(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)
a1에서는 c2, b3으로 이동
- 문제 요약
- 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) 이동
- 이처럼 반복문 코드를 작성하여 모든 방향을 차례대로 확인한다.