공부 : 동빈나 유튜브 <2. 그리디 & 구현 >+ 책 < 이것이 취업을 위한 코딩테스트다 >
구현(Implementation) : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
- 흔히 알고리즘 대회에서는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭
완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행
예제 4 - 1 상하좌우
#여행가 A가 N*N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.
#일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로도 분류됨
직접 작성한 코드에서 수정할 부분
- (답안) if문-elif문으로 반복되는 부분을 list로 만들어 간단하게 작성 가능
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']
x, y = 1, 1
for direction in move:
for i in range(len(move_types)):
if direction == move_types[i]:
nx = x + dx[i]
ny = y + dy[i]
#공간을 벗어나는 경우 무시
if nx < 1 or ny < 1 or ny > n or ny > n:
continue
x, y = nx, ny
print(x, y)
예제 4 - 2 시각
# 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수 구하기
직접 작성한 코드에서 수정할 부분
- 이 문제는 3중 for문을 돌리면 모든 경우가 86400가지로 경우의 수가 작은 편이라 완전탐색 가능
- (답안)문자열과 in을 사용해 간단하게 확인 가능
for i in range(N + 1):
for j in range(60):
for k in range(60):
if '3' in str(i)+str(j)+str(k):
cnt += 1
#if i % 10 == 3 or j // 10 == 3 or j % 10 == 3 or k // 10 == 3 or k % 10 == 3:
# cnt += 1
실전 문제 - 왕실의 나이트
# 나이트는 이동을 L모양으로 한다.
# 나이트가 이동할 수 있는 경우의 수 출력
직접 작성한 코드
- 움직일 수 있는 좌표값을 미리 리스트에 넣어둔다.- 숫자값도 리스트로 저장- 입력받은 좌표는 모두 숫자로 변경한다.
y_s, x_s = list(input())
y_s = ord(y_s) - ord('a') + 1
x_s = int(x_s)
move = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2), (1, 2)]
numList = [i for i in range(1, 8+1)]
result = 0
for x, y in move:
if x_s + x in numList and y_s + y in numList:
result += 1
print(result)
실전 문제 - 문자열 재정렬
# 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤
# 그 뒤에 모든 숫자를 더한 값을 이어서 출력
직접 작성한 코드에서 수정할 부분
- 만약 숫자가 아무것도 입력되지 않았다면 0을 출력하면 안되는데 출력한다. (수정필요)
- 답안에서 참고할 부분 --> join을 써서 리스트를 문자열로 변환하여 출력
alpha.sort()
if sum != 0:
alpha.append(str(sum))
print(''.join(alpha))
실전 문제 - 게임 개발
<입력>
4 4
1 1 0
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1
- 처음에 문제에 대한 이해를 잘못 해서 수정
- 네 방향 모두 갈 수 없는 경우 뒤쪽 방향으로 이동한다는 것을 잘못 이해
- 실제 서있는 방향에서 뒤로 갈 수 있다면 이동한다는 것을 의미
- 뒤로 이동 후 1단계로 돌아간다는 것을 구현하지 않아서 다시 수정
- 입력 예시가 2개 실행해봐서 맞았는지 확신할 수 없음
# 게임 개발
# N * M 크기의 직사각형 / 각각의 칸은 육지 또는 바다 / 캐릭터는 동서남북 중 한 곳을 바라봄
# 맵의 각 칸 (A, B) / A: 북쪽으로부터 떨어진 칸 개수, B: 서쪽으로부터 멀어진 칸의 개수
# 바다로 되어있는 공간은 갈 수 없다.
# 0 : 북쪽, 1 : 동쪽, 2 : 남쪽, 3 : 서쪽
move = [(-1, 0), (0, 1), (1, 0), (0, -1)]
def visited_map(game_map, x, y, direction, visited, cnt):
count = 0
while True:
while count < 4:
print(x, y, direction)
count += 1
direction = (direction + 3) % 4 # 왼쪽 방향
dx = move[direction][0]
dy = move[direction][1]
try:
if visited[x + dx][y + dy] is False: # 왼쪽방향 안가봤으면
visited[x + dx][y + dy] = True
cnt += 1
x = x + dx
y = y + dy
count = 0
except:
continue
try:
if visited[x - dx][y - dy] is True:
if game_map[x - dx][y - dy] == 1:
break
else:
x = x - dx
y = y - dy
count = 0
except:
break
return cnt
N, M = map(int, input().split())
print(N, M)
firstX, firstY, direction = map(int, input().split())
print(firstX, firstY, direction)
cnt = 1
game_map = []
visited = []
for i in range(N):
game_map.append(list(map(int, input().split())))
visited.append([bool(int(x)) for x in game_map[i]]) # 외우자
visited[firstX][firstY] = True
print(visited_map(game_map, firstX, firstY, direction, visited, cnt))
'study > 알고리즘' 카테고리의 다른 글
[알고리즘/프로그래머스] 스택/큐 - 기능개발, 프린터 (0) | 2021.11.23 |
---|---|
[알고리즘 / Oracle] 프로그래머스 - 입양 시각 구하기(1) (3) | 2021.11.19 |
[알고리즘] DFS/BFS - 백준 1260번/2606번 (0) | 2021.11.09 |
[알고리즘] DFS/BFS (4) | 2021.11.08 |
[알고리즘] 이진탐색 (0) | 2021.11.04 |