이것저것 개발 블로그

https://www.acmicpc.net/problem/20207

문제)

풀이)

구현 문제인데 직사각형을 표현하는 방법을 어떻게 표현해야 할지 고민이 많았다. 결국 해결 못해서 이것저것 검색해봄..ㅎ

직사각형은 row, col을 구해야하므로 이를 생각해야 한다.

row는 어떤 날짜에 일정이 몇 개가 있는지에 따라 다르다. 이것은 문제에 있는 그림을 보면 이해하기 쉬울 것이다.

따라서 row를 구하기 위해 일정을 schedule이라는 일차원 배열에 저장한다. 여기에서 가장 큰 것이 row가 될 것이다.

col은 schedule에 저장한 값이 0이 아닌 것들이 연속된 개수이다. 따라서 schedule의 값을 확인하여 col 값을 구한다.

schedule 값이 0이라면 직사각형 하나가 만들어진 것이므로 row * col 값을 정답에 저장해준다.

이때, 만약 schedule의 맨 마지막 index인 365에서 0이 아닌 값이 존재한다면 정답에 row*col 값을 저장해 줄 수 없다.

따라서 이에 해당하는 조건을 달아 해결해준다.

소스코드)

n = int(input())
schedule = [0] * 366
for i in range(n):
    start, end = map(int, input().split())
    for j in range(start, end+1):
        schedule[j] += 1

row = 0
col = 0
answer = 0
for i in range(1, len(schedule)):
    if schedule[i] != 0:
        col += 1
        row = max(row, schedule[i])
    else:
        answer += row * col
        row = 0
        col = 0
    # 만약 맨 마지막에 일정이 존재한다면 정답에 업데이트가 되지 않는다. 따라서 새로운 if문 생성
    if i == len(schedule)-1:
        answer += row * col
print(answer)

"이것이 코딩테스트다" 책 문제 _ 구현 문제

문제)

OO이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.

맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다.

캐릭터의 움직임을 설정하기 위해 정해놓은 매뉴얼은 이러하다.

1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.
2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

OO이는 위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다. 매뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

입력조건

• 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다. (3<=N,M<=50)
• 둘째 줄에 게임 캐릭터가 잇는 칸의 좌표 (A, B)와 바라보는 방향 d가 각각 서로 공백으로 구분하여 주어진다. 방향 d의 값으로는 다음과 같이 4가지가 존재한다.
  • 0: 북  1: 동  2: 남  3: 서
• 셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다로 되어있다.
  • 0: 육지 1: 바다
• 처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지이다.

출력조건

• 첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.

풀이)

이 문제는 전형적인 시뮬레이션 문제다!

내 풀이: #틀렸으니 주의!#

N, M = map(int, input().split())
x, y, now_direction = map(int, input().split())
full_map = []
for _ in range(N):
    detail_map = list(map(int, input().split()))
    full_map.append(detail_map)

# 반시계 방향이므로 북 서 남 동
direction = [0, 3, 2, 1]
# 순서대로 북, 서, 남, 동
moving = [[-1, 0], [0, -1], [1, 0], [0, 1]]
count = 1
next_direction = -1
turn_count = 0
full_map[x][y] = 2   # 처음 시작점은 방문했다고 함


for index, dir in enumerate(direction):
    if now_direction == dir:
        next_direction = direction[(index + 1) % 4]
        next_x = x + moving[(index + 1) % 4][0]
        next_y = y + moving[(index + 1) % 4][1]

        # 안 가본 육지면
        if full_map[next_x][next_y] == 0:
            now_direction = next_direction
            x = next_x
            y = next_y
            full_map[x][y] = 2  # 간 곳은 2로 표시
            count += 1
            turn_count = 0

        # 가보거나(2) 바다면
        elif turn_count < 4 and (full_map[next_x][next_y] == 2 or full_map[next_x][next_y] == 1):
            now_direction = next_direction
            turn_count += 1
            continue

        # 다 돌아봤는데 가본 칸일 때(turn_count = 4) 후진
        else:
            x = x - moving[index][0]
            y = y - moving[index][0]
            count += 1

print(count)

# 문제: 북으로 시작 안하면 망함.
# while문 사용해야함.

이 문제는 다시 풀어도 틀렸던 문제다. 다음에 다시 또 풀어봐야지!!

왼쪽으로 방향을 틀 때 어떻게 잡아야 할지 헷갈렸고, 전체 맵에서 방문한 육지를 어떻게 표현하고 조건에 따라 어떻게 이동할지 잘 정리를 못했다. 그리고 마지막으로 캐릭터를 이동시키는걸 어떻게 구현해야 하나 고민이 컸다. 이게 가장 중요한거지만ㅎㅎ

#정답 풀이#

N, M = map(int, input().split())
# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * M for _ in range(N)]
x, y, direction = map(int, input().split())
d[x][y] = 1 # 현재 좌표 방문 처리

# 전체 맵
array = []
for i in range(N):
    array.append(list(map(int, input().split())))

# 북, 동, 남, 서 방향 정의
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 왼쪽으로 회전
def turn_left():
    global direction
    direction -= 1
    if direction == -1:
        direction = 3

# 시뮬레이션
count = 1
turn_time = 0
while True:
    # 왼쪽으로 회전
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]

    # 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동
    if d[nx][ny] == 0 and array[nx][ny] == 0:
        d[nx][ny] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
        continue
    # 회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
    else:
        turn_time += 1
    # 네 방향 모두 갈 수 없는 경우
    if turn_time == 4:
        nx = x - dx[direction]
        ny = y - dy[direction]
        # 뒤로 갈 수 있으면 이동
        if array[nx][ny] == 0:
            x = nx
            y = ny
        # 뒤가 바다로 막힌 경우
        else:
            break
        turn_time = 0

print(count)

나는 반시계 방향으로 방향이 전환되니 방향 자체를 '북, 서, 남, 동'으로 해결하려 했는데 꼭 그럴 필요는 없었다.(그래서 index 이용하려 했지...) 오히려 문제에 나와있는대로 작성 후 if문 처리하면 쉽더라...;;

그리고 전체 맵을 array로, 방문했는지 체크하는 용도로 d를 만드는 것이 조건으로 체크하기 더 편했다. 다음에는 이렇게 이용해봐야지!

while문 내에서 왼쪽으로 회전한 이후(매뉴얼 1번) 크게 두 가지 케이스로 나눴다.

1. 가보지 않은 칸 존재
2. 가보지 않은 칸 존재하지 않음

특히 2번을 수행한 후 네 방향을 다 돌았는지 체크하기 위해 turn_time을 증가시킨다.(매뉴얼 2번)

만약 turn_time이 4일경우 네 면을 다 돌았는데도 불구하고 갈 수 없는 경우이므로 매뉴얼 3번에 해당한다. 따라서 이 경우는 전체 맵에서 뒤쪽 방향이 육지인지 확인 후 돌아가고 while문을 통해 매뉴얼 1번으로 다시 돌아간다! 만약 뒤가 바다라면 break를 통해 빠져나온다!

그리고 x, y 좌표를 변경하는 법!

이 부분이 항상 나는 헷갈리는 것 같다. 일단 이동을 하기 위해 각 방향별로 이동거리인 dx, dy를 생성해준다. 이때 좌표가 북과 서에서 떨어진 방향이므로 +, - 주의해야 한다!

다음 좌표인 nx, ny를 dx, dy를 이용하여 만들어준다. 이때 index는 현재 방향인 direction으로 이용하면 아주 편리하다. 

그리고 이동한다면 x, y를 nx, ny 값으로 변경해 주면 끝!

"이것이 코딩테스트다" 책 문제 _ 구현 문제

문제)

왕실 정원은 체스판과 같은 8x8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.

1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

이처럼 8x8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성ㅏ시오.

이때 왕실 정원에서 행 위치를 표현할 때는 1부터 8, 열 위치를 표현할 때는 a부터 h로 표현한다.

입력 조건

• 첫째 줄에 8x8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과 행으로 이루어진다.

출력 조건

• 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오

풀이)

행은 숫자로 받지만 열은 문자로 받으므로 아스키 코드를 이용해서 숫자로 만들어준다.

문제에서 이동할 수 있는 방법은 크게 2가지 였지만 수평으로 양 옆 이동, 수직으로 위 아래 이동을 모두 다 합하면 각 가짓수마다 4가지 이동 경우의 수가 나온다. 총 8가지 이므로 이것을 moving이라는 2차원 list로 저장해준다.

주어진 위치에서 모든 moving에 대하여 next_row, next_col에 각각 다음 행, 다음 열 위치를 저장해준다.

그리고 다음 위치가 8x8 체스판에서 벗어나는지만 확인해주고 count를 늘려주면 완료된다.

이 문제는 시뮬레이션 문제로 볼 수 있겠다.(주어진 이동 방법이 있으므로)

location = input()
row = int(location[1])
col = ord(location[0])-ord('a')+1
moving = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]]
count = 0
for move in moving:
    #next = [row, col] + move
    next_row = row + move[0]
    next_col = col + move[1]
    if next_row >= 1 and next_row <= 8 and next_col >= 1 and next_col <= 8:
        count += 1
print(count)

코드를 작성하다가 실수한 부분이 있었는데, list + list를 할 경우엔 list가 합쳐진 결과가 나온다.(ex: [1, 1] + [0, -1] = [1, 1, 0, -1])

각 요소가 더해진 결과가 나오지 않는다는 점!!! 기억하자!!!

"이것이 코딩테스트다" 책 문제 _ 구현 문제

문제)

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성해라.

입력 조건

• 첫째 줄에 정수 N이 입력된다.(0 <= N <= 23)

출력 조건

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

풀이)

모든 시각의 경우의 수를 세면 가능한 문제다. 즉, 이 문제는 완전 탐색 문제이다.

시간, 분, 초를 3중 반복문을 이용하여 3이 존재하는지 확인한다.

3이 존재하는지 확인하는 방법을 생각했을 때 int로는 확인하기 어려우므로 string으로 바꾸어서 시, 분, 초를 합친 후 3이 존재하는지 확인한다. 

예를 들어 03시 11분 05초의 경우 string으로 바꾸어 합치면 '3115'이므로 count 한다. (0을 꼭 포함해서 넣을 필요는 없으니까!)

N = int(input())
num = range(60)
count = 0
for i in range(N+1):
    for j in num:
        for k in num:
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)

"이것이 코딩테스트다" 책 문제 _ 구현 문제

문제)

사람 A는 N x N 크기의 정사각형 공간위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이고, 가장 오른쪽 아래 좌표는 (N, N)이다. A는 상, 하, 좌, 우 방향으로 이동할 수 있고, 시작 좌표는 항상 (1, 1)이다.

이때 A가 이동할 계획이 적힌 계획서가 있는데, 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 이 문자의 의미는 다음과 같다.

• L: 왼쪽으로 한 칸 이동
• R: 오른쪽으로 한 칸 이동
• U: 위쪽으로 한 칸 이동
• D: 아래쪽으로 한 칸 이동

이때 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1, 1) 위치에서 L 혹은 U를 만나면 무시된다.

입력 조건

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 <= N <= 100)
• 둘째 줄에 A가 이동할 계획서 내용이 주어진다. (1 <= 이동횟수 <= 100)

출력 조건

• 첫째 줄에 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.

풀이)

1. 내 풀이

이 문제는 x, y 좌표만 계산을 해 주면 간단한 문제이다.

이때 주의할 점은 L, R은 y 좌표에 영향을, U, D는 x 좌표에 영향을 준다는 것이다. (일반적인 좌표평면이 아니라서 그렇다.)

따라서 반복문을 이용하여 계획서 내 L, R, U, D 각각에서 이동할 수 있는 조건에 해당하면 x, y좌표가 이동하도록 조건문을 작성했다.

N = int(input())
moving = input().split()

x = 1
y = 1

for i in moving:
    if y < N and i == 'R':
        y += 1
    elif y > 1 and i == 'L':
        y -= 1
    elif x > 1 and i == 'U':
        x -= 1
    elif x < N and i == 'D':
        x += 1

print(x, y)

2. 답지 풀이

이 문제는 구현 문제에서 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션에 해당한다. 

또한 연산 횟수가 이동 횟수에 비례하게 되어서 시간 복잡도가 O(N)이므로(이때, N은 이동 횟수) 시간 복잡도는 넉넉한 편이다.

N = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

# 이동 계획 확인
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > N or ny > N:
        continue
    # 이동 수행
    x, y = nx, ny

print(x, y)

문제를 푸는 알고리즘은 내가 풀었던 방식과 같다. 하지만 풀이에선 L, R, U, D에 따른 이동 거리를 dx, dy로 만들어 주었고 nx, ny라는 변수에 이동한 좌표를 저장해 주었다. 공간을 벗어나지 않을 땐 nx, ny를 x, y로 갱신해주고, 공간을 벗어나는 경우에는 x, y를 갱신하지 않음으로써 예외처리를 해 주었다.

구현 종류

1. 완전 탐색

모든 경우의 수를 다 계산하는 방법

2. 시뮬레이션

문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행하는 방법

파이썬에서 int형 데이터의 개수에 따른 메모리 사용량

데이터 개수(리스트 길이) 1,000 당 메모리 약 4KB

=> 즉, 데이터 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한 확인 필요!!

파이썬에서 채점 시 시간 제한 고려

1초에 2,000만 번의 연산 정도를 한다면 실행 시간 제한에 안정적

만약, 시간 제한이 1초, 데이터의 개수가 100만 개라면 시간 복잡도 O(NlogN) 이내의 알고리즘으로 해결해야함

=> 문제를 풀 때 시간 제한과 데이터의 개수를 확인해야함!