[코딩테스트] 구현, 시뮬레이션과 완전 탐색

코딩테스트에서 말하는 구현 문제라는 것은,

풀이(알고리즘)를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제다.

 

-알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제

-실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제

-문자열을 특정 기준에 따라 끊어 처리하는 문제

-적절한 라이브러리를 찾아서 사용해야 하는 문제 ( 순열, 조합을 예로 들면 itertools를 사용해서 대응 가능하지만 이를 모르면 방대하게 구현해야 함)

 

2차원 공간, 행렬(Matrix)에서의 방향 벡터가 자주 활용된다.

 

#동,북,서,남 : 방향성을 명시해주기 위해서 리스트나 배열 형태로 나타낸다.

dx= [0,-1,0,1]#행

dy= [1,0,-1,0]#열

#현재 위치

x,y = 2,2

for i in range(4) :

    #다음 위치

    nx = x +dx[i]

    ny = y +dy[i]

    print(nx, ny)

 

 

문제1. 상하좌우

여행가 A가 L,R,U,D가 적힌 계획서에 따라 움직인다. 단, NxN 크기의 정사각형 공간을 벗어나면 무시한다.

최종으로 도착할 지점의 좌표(x,y)를 공백을 기준으로 구분하여 출력하자.

 

-> 일련의 명령에 따라서 개체를 차례대로 이동시키는 코딩테스트 시뮬레이션 유형으로도 분류 가능(시뮬레이션, 구현, 완전탐색이 유사한 점이 많아 사이트에 따라 다르게 부를 수 있으니 유의)

 

문제 2. 시각 문제

00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하시오.

 

-> 가능한 모든 시각의 경우를 하나씩 모두 세면서, 확인해야 하므로, 완전탐색(Brute forcing) 문제 유형이다. 가능한 경우의 수를 모두 검사해보는 탐색 방법이다. 파이썬에서 1초에 약 2천만번 처리가 가능하므로, 하루는 86,400초이기 때문에 지금 이 경우에는 1초 안에 충분히 처리할 수 있다.

 

문제 3. 왕실 나이트

8x8 좌표 평면에서 L자(두칸, 한칸) 형태로만 움직일 수 있는 나이트의 위치가 주어졌을 때, 나이트가 이동할 수 있는 경우의 수를 출력하라.

 

-> 이동 가능한 8가지 경로를 하나씩 확인하면서 각 위치로 이동이 가능한지 확인하면 된다. 리스트를 이용해서 8가지 방향에 대한 방향 벡터를 먼저 정의해둔 다음 문제를 풀자.

 

steps = [(-2,-1),(-1,2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]

 

 

문제4. 문자열 재정렬

알파벳 대문자와 숫자로 구성된 문자열이 입력될 경우,

모든 알파벳을 오름차순 정렬, 그 뒤에 모든 숫자를 더한 값을 이어서 출력하라.

 

-> 알고리즘에서 수는 10, 1000 같은 실제 수이고, 숫자는 0~9 사이의 한 글자를 의미한다.

 

코딩테스트 준비하기

2022.12.18 - [Data Science] - [코딩테스트] 코딩테스트 및 관련 알고리즘의 개요

2022.12.19 - [Data Science] - [코딩테스트] 파이썬 문법 기초 복습 : 자료형

2022.12.20 - [Data Science] - [코딩테스트] 파이썬 문법 기초 복습 : 입출력부터 자주 쓰이는 라이브러리까지

2022.12.23 - [Data Science] - [코딩테스트] 그리디 알고리즘(Greedy), 탐욕법

 

 

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC 

*내용에 대한 모든 저작권은 해당 영상의 원저작자에게 있습니다.