[항해99 취업 리부트 코스 학습일지] 시뮬레이션 무한 뺑뺑이 돌기

시뮬레이션 중...

오늘 드디어 시뮬레이션과 완전 탐색에 들어갔다.

진짜 시뮬레이션 세상에서 제일 싫어하는 유형이다.

어디가 틀렸는지 디버깅하기도 쉽지 않고 무엇보다 문제가 너무 길어져서 집중 안 하면 놓치는 부분이 많다.

오늘 풀집중해서 문제 풀어봤는데 8문제 중에서 7문제 풀었다.

마지막 문제까지 가니까 문제도 안 읽히고 그래서 그냥 포기,,

주말에 풀어봐야지 ㅎ

---

0. TIL (2024.06.12)

📚오늘 진행한 문제 리스트

1. 백준 1251 단어 나누기 (실버 5) ✔️

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

풀이⬇️

# 백준 1251 단어 나누기 - 실버 5

# 단어를 3개로 끊고 분리된 단어를 뒤집어서 다시 결합한 단어의 사전순 제일 빠른 단어 출력
# 우선 끊을 부분을 combinations 를 통해 정한 뒤, S를 끊을 부분 기준으로 슬라이싱을 한다.
# 그 다음, 슬라이싱 된 단어를 뒤집어 다시 결합하고 이를 기존에 저장한 단어와 비교해서 사전순 빠르면 갱신한다.

# 31120/52
import sys
from itertools import combinations
input = sys.stdin.readline


def flip_the_word(S):
    result = 'z'
    for _, second, third in combinations(range(len(S)), 3):
        target = ''.join([S[:second][::-1], S[second:third][::-1], S[third:][::-1]])
        result = target if result > target else result
    return result


def main():
    S = input().strip()
    return print(flip_the_word(S))


main()

 

2. 백준 4673 셀프 넘버 (실버 5) ✔️

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

풀이⬇️

# 백준 4673 셀프 넘버 - 실버 5

# 0 < N <= 10000 인 숫자 범위의 셀프 넘버 찾기
# N의 범위가 10000까지라서 그냥 함수 적용한 숫자 만들고 계산해도 될 듯
# 10000까지의 집합 - 함수를 적용한 숫자의 집합 = 셀프 넘버

# 32148/48
import sys
input = sys.stdin.readline


def create_nums(N):
    nums_set = set()
    for num in range(1, N):
        tmp, s_num = num, str(num)
        for j in range(len(s_num)):
            tmp += int(s_num[j])
        nums_set.add(tmp)
    return nums_set


def main():
    N = 10000
    original_nums = set([i for i in range(1, N)])
    created_nums = create_nums(N)
    return print('\n'.join(map(str, sorted(original_nums - created_nums))))


main()

 

3. 백준 1063 킹 (실버 3) ✔️

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

풀이⬇️

# 백준 1063 킹 - 실버 3

# 체스판의 돌과 킹의 이동한 뒤 좌표를 묻는 문제
# 주어지는 좌표가 A1, B2와 같은 방식이므로 이를 (x, y) 형식으로 바꾼다.
# 각 command 별로 이동하는 칸을 dict에 저장 -> 입력 받은 command를 순회하면서 좌표 수정
# 킹을 움직이려고 할 때, 범위를 벗어나면 다음 command 실행
# 킹이 범위 안에 있는데 돌이 진행 방향에 있다? 돌도 같이 진행 방향으로 움직임
# 이 때, 돌이 범위 밖으로 나가게 되어도 다음 command 실행
# 최종적으로 움직인 킹과 돌의 좌표를 원래 형태(A1, B2)로 변경 후 출력

# 31120/44
import sys

input = sys.stdin.readline

dict_to_change_the_original = {'A': 1, 'B': 2, 'C': 3, 'D': 4, 'E': 5, 'F': 6, 'G': 7, 'H': 8}
dict_to_reverse_the_changed = {1: 'A', 2: 'B', 3: 'C', 4: 'D', 5: 'E', 6: 'F', 7: 'G', 8: 'H'}
direction = {
    'R': (1, 0),
    'L': (-1, 0),
    'B': (0, -1),
    'T': (0, 1),
    'RT': (1, 1),
    'LT': (-1, 1),
    'RB': (1, -1),
    'LB': (-1, -1)
}


def change_coord_from_original(original):
    alpha, num = original[0], original[1]
    return dict_to_change_the_original[alpha], int(num)


def change_coord_from_changed(changed):
    row, col = changed[0], changed[1]
    return f'{dict_to_reverse_the_changed[row]}{col}'


def cal_coord(king, stone, command):
    cur_x, cur_y = king
    st_x, st_y = stone
    for c in command:
        dx, dy = direction[c]
        if 1 <= cur_x + dx <= 8 and 1 <= cur_y + dy <= 8:
            if cur_x + dx == st_x and cur_y + dy == st_y:
                if 1 <= st_x + dx <= 8 and 1 <= st_y + dy <= 8:
                    st_x, st_y = st_x + dx, st_y + dy
                else:
                    continue
            cur_x, cur_y = cur_x + dx, cur_y + dy
    return [change_coord_from_changed((cur_x, cur_y)), change_coord_from_changed((st_x, st_y))]


def main():
    inp = input().strip().split()
    king, stone, N = change_coord_from_original(inp[0]), change_coord_from_original(inp[1]), int(inp[2])
    command = [input().strip() for _ in range(N)]
    return print('\n'.join(cal_coord(king, stone, command)))


main()

 

4. 백준 1182 부분수열의 합 (실버 2) ✔️

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

풀이⬇️

# 백준 1182 부분수열의 합 - 실버 2

# 부분수열의 합이 S와 일치하면 cnt 증가

# 31120/252
import sys
from itertools import combinations
input = sys.stdin.readline


def count_partial_sequence(N, S, arr):
    cnt = 0
    for i in range(1, N + 1):
        for c in combinations(arr, i):
            if sum(c) == S:
                cnt += 1
    return cnt


def main():
    N, S = map(int, input().split())
    arr = list(map(int, input().split()))
    return print(count_partial_sequence(N, S, arr))


main()

 

5. 백준 16918 봄버맨 (실버 1) ✔️

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

풀이⬇️

# 백준 16918 봄버맨 - 실버 1

# 시간마다 변경되는 격자의 모양을 리턴하는 문제
# 구현해야하는 기능마다 컴포넌트로 분리했고 폭탄이 폭발할 때, 3초 이상 지난 폭탄이 같이 사라지는 경우가 있다.
# bfs로 근처 3초 이상 경과된 폭탄 찾아서 같이 터트려 준다.

# 34308/2576
import sys
from collections import deque
input = sys.stdin.readline


def init(R, C, grid):
    for i in range(R):
        for j in range(C):
            grid[i][j] = 0 if grid[i][j] == '.' else 1


def update_bombs_time(grid):
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] != 0:
                grid[i][j] += 1


def install_bombs(grid):
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 0:
                grid[i][j] = 1


def explode_bombs(grid):
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] >= 3:
                check_and_explode(grid, i, j)


def check_and_explode(grid, i, j):
    dy, dx = [-1, 0, 1, 0], [0, 1, 0, -1]
    q = deque([(i, j)])
    grid[i][j] = 0
    while q:
        y, x = q.popleft()
        for d in range(4):
            ny, nx = y + dy[d], x + dx[d]
            if 0 <= ny < len(grid) and 0 <= nx < len(grid[0]):
                if grid[ny][nx] >= 3:
                    q.append((ny, nx))
                grid[ny][nx] = 0


def convert(grid, R, C):
    for i in range(R):
        for j in range(C):
            grid[i][j] = '.' if grid[i][j] == 0 else 'O'


def run(N, grid):
    cnt = 1
    # 처음 폭탄 설치하는 것 이외에는 짝수 초에는 업데이트와 설치만, 홀수 초에는 폭발까지 같이 일어남
    # 홀수, 짝수 초 -> 시간 경과 업데이트, 빈 공간 폭탄 설치
    # 홀수 초 -> 폭발
    while cnt < N:
        cnt += 1
        # 1. 0이 아닌 곳 시간 업데이트
        update_bombs_time(grid)
        # 2. 폭탄 설치
        install_bombs(grid)
        if cnt % 2 == 1:
            # 3. 폭발
            explode_bombs(grid)
        if cnt == N:
            return


def main():
    R, C, N = map(int, input().split())
    grid = [[x for x in input().strip()] for _ in range(R)]
    init(R, C, grid)
    run(N, grid)
    convert(grid, R, C)
    return print('\n'.join(''.join(map(str, g)) for g in grid))


main()

 

6. 백준 11559 Puyo Puyo (골드 4) ✔️

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

풀이⬇️

# 백준 11559 Puyo Puyo - 골드 4

# 뿌요뿌요 게임 구현
# 1. 같은 뿌요 연결되어 있는거 찾기 -> bfs로 탐색
# 2. 찾았을 때 4개 이상이라면 삭제 작업 진행
# 3. 뿌요가 사라지고 나서 그 자리 기준으로 위에 다른 뿌요가 있는지 탐색 -> 있다면 이동
# 4. 착지 후에 다시 탐색해서 연결되어 있으면 삭제 후 cnt += 1
# 한 번 터지고 나서, 다른 색깔도 탐색해서 붙어 있는지 확인하고 있으면 또 터지게 작업

# 34148/64
import sys
from collections import deque
input = sys.stdin.readline

R, C = 12, 6


def start_the_game(field):
    combo = 0
    is_over = True
    while is_over:
        flag = False

        for i in range(R):
            if all(e == '.' for row in field for e in row):
                break
            for j in range(C):
                if field[i][j] != '.':
                    coordinates = bfs(field, (i, j))
                    if len(coordinates) >= 4:
                        flag = True
                        delete_puyo(field, coordinates)
        if flag:
            move_down(field)
            combo += 1
        else:
            is_over = False
    return combo


def bfs(field, start):
    dy, dx = [-1, 0, 1, 0], [0, 1, 0, -1]
    visited = [[False] * C for _ in range(R)]
    puyo_coord = set()
    q = deque([start])
    puyo_coord.add(start)
    visited[start[0]][start[1]] = True
    while q:
        y, x = q.popleft()
        for d in range(4):
            ny, nx = y + dy[d], x + dx[d]
            if 0 <= ny < R and 0 <= nx < C and not visited[ny][nx] and field[ny][nx] == field[y][x]:
                q.append((ny, nx))
                visited[ny][nx] = True
                puyo_coord.add((ny, nx))
    return puyo_coord


def delete_puyo(field, coord):
    for y, x in coord:
        field[y][x] = '.'


def move_down(field):
    for j in range(C):
        empty_idx = R-1
        for i in range(R-1, -1, -1):
            if field[i][j] != '.':
                if empty_idx > i:
                    field[empty_idx][j] = field[i][j]
                    field[i][j] = '.'
                empty_idx -= 1


def main():
    field = [[x for x in input().strip()] for _ in range(R)]
    return print(start_the_game(field))


main()

 

7. 백준 2573 빙산 (골드 4) ✔️

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

풀이⬇️

# 백준 2573 빙산 - 골드 4

# 빙산은 바닷물이 많이 접할수록 더 빨리 줄어든다 -> 빙산 탐색하면서 바닷물 접한거에 따라 높이 조절
# 빙산 두 덩어리 이상으로 분리되는 최초의 시간 구하기 -> 빙산 구역 탐색

# 34164/3616

import sys
from collections import deque
input = sys.stdin.readline

dy, dx = [-1, 0, 1, 0], [0, 1, 0, -1]

N, M = map(int, input().split())
iceberg = [list(map(int, input().split())) for _ in range(N)]


def four_way_search(y, x, melting):
    cnt = 0
    for d in range(4):
        ny, nx = y + dy[d], x + dx[d]
        if not melting[ny][nx] and iceberg[ny][nx] == 0:
            cnt += 1
    return cnt


def melt_an_iceberg():
    flag = False
    melting = [[False] * M for _ in range(N)]

    for i in range(1, N - 1):
        for j in range(1, M - 1):
            if iceberg[i][j] > 0:
                melting[i][j], flag = True, True
                cnt = four_way_search(i, j, melting)
                if iceberg[i][j] > cnt:
                    iceberg[i][j] -= cnt
                else:
                    iceberg[i][j] = 0
    return flag


def bfs(visited, start):
    q = deque([start])
    visited[start[0]][start[1]] = True
    while q:
        y, x = q.popleft()
        for d in range(4):
            ny, nx = y + dy[d], x + dx[d]
            if 0 <= ny < N and 0 <= nx < M and iceberg[ny][nx] > 0 and not visited[ny][nx]:
                q.append((ny, nx))
                visited[ny][nx] = True


def count_iceberg_area():
    visited = [[False] * M for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(M):
            if iceberg[i][j] > 0 and not visited[i][j]:
                bfs(visited, (i, j))
                cnt += 1
    return cnt


def count_years():
    year, cnt = 0, 0
    flag = True
    while flag:
        cnt = count_iceberg_area()
        if cnt >= 2:
            return year

        if not melt_an_iceberg():
            flag = False
        year += 1
    return 0


def main():
    return print(count_years())


main()

 

8. 백준 14890 경사로 (골드 3) ❌

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

풀이⬇️

푸는 중~

---

📝오늘자 질문

1. 오늘 진행된 강의에서 학습한 내용은 무엇인가요

• 시뮬레이션, 완전 탐색

 

2. 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?

• 시뮬레이션 문제 풀 때, 각 기능별로 함수화 시키기 (재사용성 및 가독성의 증가)

---

* 항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

https://hanghae99.spartacodingclub.kr/reboot

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지