우주의 IT 소행성

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

n, m = map(int, input().split())
a = [list(input()) for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
location = []

for i in range(n):
    for j in range(m):
        if a[i][j] == 'o':
            location.append((i, j))

x1, y1 = location[0]
x2, y2 = location[1]


def go(x1, y1, x2, y2, count):
    is_fall = [False, False] # 동전이 떨어졌는지 여부 파악

    # 버튼을 10번 넘게 누른 경우
    if count == 11:
        return -1

    if (x1 < 0 or x1 >= n or y1 < 0 or y1 >= m):
        is_fall[0] = True
    if (x2 < 0 or x2 >= n or y2 < 0 or y2 >= m):
        is_fall[1] = True

    if is_fall[0] and is_fall[1]:  # 둘 다 떨어진 경우 (불가능)
        return -1

    if is_fall[0] or is_fall[1]:  # 하나만 떨어진 경우 (정답)
        return count

    ans = -1
    for i in range(4):
        nx1, ny1 = x1 + dx[i], y1 + dy[i]
        nx2, ny2 = x2 + dx[i], y2 + dy[i]

        # 이동할 칸이 벽이라면 이동하지 않는걸로
        if 0 <= nx1 < n and 0 <= ny1 < m and a[nx1][ny1] == '#':
            nx1, ny1 = x1, y1
        if 0 <= nx2 < n and 0 <= ny2 < m and a[nx2][ny2] == '#':
            nx2, ny2 = x2, y2

        # 다음 칸으로 진행시켰는데
        temp = go(nx1, ny1, nx2, ny2, count + 1)
        if temp == -1:  # -1 받았다면 무시
            continue
        if ans == -1 or ans > temp:  # -1이 아니라면(정답이라면)
            ans = temp
    return ans

print(go(x1, y1, x2, y2, 0))

네 개의 버튼 (상하좌우)를 통해 두 동전을 동시에 이동시키는데

1. 동전이 벽에 가로 막히면 제자리

2. 동전 하나가 떨어지면 정답

3. 동전 2개가 동시에 떨어지는건 불가능

4. 버튼을 10번이상 사용하면 무효

라는 4가지 조건을 지키며 재귀함수를 통해서 풀어주었다

2021.12.22 -> 2021.01.19

골드 3 -> 골드 2

걸린 시간 : 29일

푼 문제 : 84문제

레이팅 변화 : 1103 > 1251 (148 증가)

순위 변화 : 8,932등 (상위 20.85%) -> 7,142 (상위 15.37%)

중점으로 공부했던 부분

1. 시간 복잡도

2. 수학 알고리즘

3. 브루트 포스 알고리즘 (재귀, 순열, 비트마스크)

4. 다이나믹 프로그래밍 (1차원, LCS, Row major matrix..)

5. 큐, 그래프, BFS, DFS

앞으로 공부해야 할 부분

1. 구현

2. 유니온 파인드

3. 이분 탐색

4. SQL

5. 웹

그 외 : 자표 압축, 라인스위핑, 상호배타적집합, 팬윅트리...등등

2022년 1월 17일(월)을 기점으로 sw마에스트로 13기 모집이 시작되었다.

열심히 자소서도 쓰고, 프로그래밍 공부도 하고 있긴 한데 하루에 열시간 씩 알바하고 들어와서

코딩하고 있으니 남들보다 절대적인 공부시간도 적고. 정신적으로 많이 휘청거린다

그래도 해야만 한다. 난 할 수 있다. 아니 해야만 한다.

지금까지 약 40~50일 정도 커밋을 유지하고 있는데, 어느새 진취적인 공부보다는

피곤한 날에는 커밋 채우기에 급급한 보여주기식 공부를 했던 것 같아 많이 반성이 된다.

나는 왜 공부하는가? 정신이 번쩍 들었다. 내 인생에 지금은 다시 오지 않는다. 다음번 이란 없다.

이번이 마지막인 것 처럼. 오늘이 마지막 인 것 처럼 해보자!! 힘내자!!

다이나믹 프로그래밍, 메모이제이션을 사용하여 풀어야 하는 문제이다.

2xN 직사각형을 1x2, 2x1, 2x2 타일로 채우는 경우의 수를 구를 2X(최대 1000)까지 구한다.

즉 반복되는 작업을 한다 -> 수열이 형성된다 라는 점을 기억해야한다.

1*2 -> A

2*1 -> B

2*2 -> C

라고 생각해보자

1) N이 1일 때

- B 한가지만 들어갈 수 있다.

- F(1) = 1

2) N이 2일 때

- AA, BB, C

- F(2) = 3

3) N이 3일 때

- AAB, BAA, CB, BC, BBB

- F(3) = 5

4) N이 4일 때

- AAAA, BBBB, AABB, BBAA, BAAB, AAA, CAA, BBC, CBB, BCB, CC 

- F(4) = 11

이 떄, N이 4 이상일 경우, F(N) = F(N - 1) + (F(N - 2) * 2)

의 일반항을 도출할 수 있고 이를 메모이제이션하여 출력해주면 된다.

문제의 반복성과 규칙성을 찾아내 일반항을 도출하는 것

-> 다이나믹 프로그래밍으로 해결할 수 있다.

from collections import deque
n = int(input())
matrix = [(list(map(int, input().split()))) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

queue = deque()
queue.append((0, 0))

while queue:
    x, y = queue.popleft()
    visited[x][y] = True
    jump_size = matrix[x][y]
    dx = [0, jump_size]
    dy = [jump_size, 0]

    for i in range(2):
        nx = dx[i] + x
        ny = dy[i] + y

        if n <= nx or n <= ny:
            continue
        if jump_size == 0:
            continue
        if jump_size == -1:
            print("HaruHaru")
            exit(0)
        if not visited[nx][ny]:
            queue.append((nx, ny))
            visited[nx][ny] = True

print("Hing")

https://universe-lee.tistory.com/34

점프왕 쩰리 (small)의 다음편 large이다. 주어진 맵의 크기가 2에서 64로 올라가는데,

이를 메모리나 시간 초과 없이 푸는게 관건이다.

따라서 bfs시에 이미 갔던 길을 계속해서 가게 된다면 결국 도착 하기 전에 시간초과나 메모리 낭비가 생길것이니

이미 갔던 길을 표시하여, 아 여기는 안 갈래! 하면 되는것이다.

visited 라는 리스트를 만들고, bfs시마다 현재 좌표에 일종의 flag를 꽂는다 (방문, 미방문)

나중에 queue에 새로운 위치를 넣을 때 이미 방문한 위치라면 (visited == True) 재 방문하지 않는다.,

from collections import deque
n = int(input())
matrix = [(list(map(int, input().split()))) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

queue = deque()
queue.append((0, 0))

while queue:
    x, y = queue.popleft()
    visited[x][y] = True
    jump_size = matrix[x][y]
    dx = [0, jump_size]
    dy = [jump_size, 0]

    for i in range(2):
        nx = dx[i] + x
        ny = dy[i] + y

        if n <= nx or n <= ny:
            continue
        if jump_size == 0:
            continue
        if jump_size == -1:
            print("HaruHaru")
            exit(0)
        if not visited[nx][ny]:
            queue.append((nx, ny))
            visited[nx][ny] = True

print("Hing")