WEEK 03 알고리즘 TIL(4월3일 목요일)

9:00 ~
시험을 치기 전에 복습을 하고, 시험에 쳤다.

13:00 ~ 14:00
4주차 발제를 진행했다.

14:00 ~ 15:00
코치님들과 함께 티타임을 했다. 이후 친 시험에 대해서 코드리뷰를 진행했습니다.

[추가] 1번 1338 바닥 장식

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

# 같은 행일때 같게 치면 근처(왼,우) 스캔해서 같은 값이면 하나로 치면 될 것 같음
# 순회하면서 같은거 나오면 한개로치고 아니면 따로 셈
import sys

input = sys.stdin.readline

# 방 바닥의 세로 크기 N, 가로 크기 M
N,M = map(int, input().split())
graph = [] 	# 2차원 리스트의 맵 정보 저장할 공간
for _ in range(N):
    graph.append(list(input()))

# -나무
count = 0
for i in range(N):
    a = ''
    for j in range(M):
        if graph[i][j] == '-':   # -일시
            if graph[i][j] != a:
                count += 1
        a = graph[i][j]   # 만약에 -이면 같은 걸로 계산, 다른게 나오면 상단에 if에 따라 다른 걸로 계산

# ㅣ나무
for j in range(M):
    a = ''
    for i in range(N):
        if graph[i][j] == '|':  # |일시
            if graph[i][j] != a:
                count += 1
        a = graph[i][j]
        

print(count)

[추가] 2번 2667 단지번호붙이기

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

# 0으로 분리된 단지의 수를 뽑고, 단지의 집의 개수를 오름차순으로 출력해야한다.
from collections import deque
import sys

input = sys.stdin.readline

dx = [-1, 1, 0, 0]  # 상, 하 이동
dy = [0, 0, -1, 1]  # 좌, 우 이동
    
def BFS(start_x, start_y, graph, visited):
    visited[start_x][start_y] = True  # 방문 처리
    # visited로 중복 방문을 방지
    queue = deque([(start_x, start_y)])  # (현재 위치 x, y, 이동 거리(1씩이동))
    count = 1  # 내집

    while queue:  # 큐가 빌때까지 실행
        x, y = queue.popleft()  # 현재 위치 꺼내기

        for i in range(4):  # 상하좌우 이동
            nx = x + dx[i]  # 현재 x에서 dx만큼 이동
            ny = y + dy[i]  # 현재 y에서 dy만큼 이동

            # 범위를 벗어나지 않고 방문하지 않은 길(1)인 경우 이동
            if 0 <= nx < N and 0 <= ny < N:   # 입력된 N, M에 따라 범위를 벗어나지 않게 한다.
                if graph[nx][ny] == 1 and not visited[nx][ny]:    # 방문하지 않았고 1인 지역이면
                    visited[nx][ny] =True  # 방문 기록 추가
                    queue.append((nx, ny))  # 이동 거리 증가하여 추가
                    count += 1  # 단지내 개수 증가

    return count  # 총 단지 크기 반환

# 입력 처리
N = int(input())
graph = [list(map(int, list(input().strip()))) for _ in range(N)]  # 미로 정보 (숫자로 변환)
visited = [[False] * N for _ in range(N)]  # 방문 여부 저장
complex_counts = []  # 단지별 집 개수 저장

for i in range(N):
    for j in range(N):
        if graph[i][j] == 1 and not visited[i][j]:  # 집이 있고 방문하지 않은 경우
            complex_counts.append(BFS(i, j, graph, visited))  # BFS 실행 후 단지 크기 저장
            
# 결과 출력
complex_counts.sort()  # 단지 크기 오름차순 정렬
print(len(complex_counts))  # 총 단지 수 출력
for count in complex_counts:
    print(count)  # 각 단지 크기 출력

[추가] 3번 18405 경쟁적 전염

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

from collections import deque
import sys

input = sys.stdin.readline

# 방향 벡터 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 입력 처리
N, K = map(int, input().split())  # 시험관 크기 (N x N) 및 바이러스 종류 개수
graph = []  # 시험관 정보를 저장할 리스트
virus_list = []  # (바이러스 번호, 행, 열, 시간)을 저장할 리스트

# 시험관 정보 입력 받기
for i in range(N):
    row = list(map(int, input().split()))
    graph.append(row)
    for j in range(N):
        if row[j] != 0:  # 바이러스가 있는 경우
            virus_list.append((row[j], i, j, 0))  # (바이러스 종류, x, y, 시간) 저장

# 낮은 번호의 바이러스가 먼저 확산되도록 정렬
virus_list.sort()

# 큐에 초기 바이러스 정보 삽입
queue = deque(virus_list)

# S초 후 확인할 위치 (X, Y)
S, X, Y = map(int, input().split())

# BFS 실행
while queue:
    virus, x, y, time = queue.popleft()

    # S초가 지나면 종료
    if time == S:
        break

    # 상하좌우 이동하며 전파
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        # 범위를 벗어나지 않고, 아직 감염되지 않은 경우 (0인 경우)
        if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 0:
            graph[nx][ny] = virus  # 바이러스 전파
            queue.append((virus, nx, ny, time + 1))  # 시간 증가하여 큐에 추가

# 결과 출력 (X, Y는 1-based index이므로 0-based로 변환)
print(graph[X-1][Y-1])

해당 문제는 다 풀진 않았는데, 올려두긴 하겠다.

+++ 추가적으로 시험이 끝나고 전부터 예정이었던 턱걸이 이벤트를 했다. 분위기 환기도 되고 좋은 이벤트인 것 같다.

이렇게 3주차가 마무리되었다. WEEK 03 공부 종료. 4월 3일 20:00.
4주차는 동적 프로그래밍, 그리디 알고리즘을 배워보는 시간을 가져보겠다.
또한 컴퓨터 시스템은 3장 프로그램의 기계 수준 표현을 학습할 것이다.