Krafton_jungle 5기 18일차 TIL - 알고리즘 문제풀이, CSAPP

백준 문제풀이

1. 1388 바닥장식

import sys
input = sys.stdin.readline


n, m = map(int, input().split())

plate = []
for i in range(n):
    row = input().rstrip()
    plate.append(row)

count = 0

# 가로 타일 탐색
for i in range(n):
    flag = False
    for j in range(m):
        if plate[i][j] == "-" and flag == False:
            flag = True
            count += 1
        elif flag == True and plate[i][j] == "|":
            flag = False

for i in range(m):
    flag = False
    for j in range(n):
        if plate[j][i] == "|" and flag == False:
            flag = True
            count += 1
        elif flag == True and plate[j][i] == "-":
            flag = False

print(count)

전에 한번 풀었던 경험이 있어서 전체 배열을 순회하는 방식으로 풀었음

 

2. 2667 단지 번호 붙이기

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

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

def bfs(y,x):
    queue = deque()
    queue.append((y,x))
    visited[y][x] = 1
    count = 1
    while queue:
        y,x = queue.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < n and 0 <= nx < n and visited[ny][nx] == -1 and plate[ny][nx] == "1":
                queue.append((ny, nx))
                count += 1
                visited[ny][nx] = 1
    result.append(count)


n = int(input())

plate = []

visited = [[-1] * n for _ in range(n)]
result = []

for i in range(n):
    row = input().rstrip()
    plate.append(row)

for i in range(n):
    for j in range(n):
        # 만약 가구가 존재하고 아직 방문하지 않았으면
        if plate[i][j] == "1" and visited[i][j] == -1:
            bfs(i,j)

result.sort()
print(len(result))
for i in result:
    print(i)

간단한 BFS 문제.

탈출에서 사용한 방법을 참고해서 탐색함

 

3. 18405 경쟁적 전염

import sys
from collections import deque
input = sys.stdin.readline
n, k = map(int, input().split())

plate = []
virus = []
visited = [[-1] * n for _ in range(n)]

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

# 바이러스
for i in range(n):
    row = list(map(int, input().split()))
    plate.append(row)
    # 바이러스의 종류 수집
    for j in range(n):
        if plate[i][j] != 0:
            # 바이러스의 종류, Y좌표, X좌표 가져오기
            virus.append((i,j,plate[i][j]))

# 바이러스의 크기에 따라서 정렬
virus.sort(key=lambda x : x[2])
virus = deque(virus)

# S초 뒤에 (Y,X 뒤에 존재하는 바이러스 구하기)
S, Y, X = map(int, input().split())

count = 0

while count != S:
    result_queue = deque()
    while virus:
        # 현재 대기열에 있는 오름차순으로 정렬된 바이러스를 추출
        cur_y, cur_x, cur_virus = virus.popleft()
        # 방문처리
        visited[cur_y][cur_x] = 1
        # 4방향 탐색
        for i in range(4):
            ny = cur_y + dy[i]
            nx = cur_x + dx[i]
            # 만약 바이러스가 범위를 벗어나지 않고, plate가 전염되지 않았다면
            if 0 <= ny < n and 0 <= nx < n and plate[ny][nx] == 0:
                # 전염시키고 대기열에 추가
                plate[ny][nx] = cur_virus
                result_queue.append((ny, nx, cur_virus))
    # 1 사이클이 종료되면
    # 바이러스 사이클 초기화
    virus = result_queue
    count += 1

print(plate[Y-1][X-1])

sub queue를 선언해줘서 내가 원하는 만큼만 사이클을 돌려줬음

 

CS:APP

3. 프로그램의 기계수준 표현

컴퓨터란?	데이터 처리, 메모리 관리, 저장장치 제어, 네트워크 통신을 명령하는 기계어 코드를 실행
GCC 컴파일러	소스 코드를 컴파일하여 기계어로 변환해서 실행 가능한 인스트럭션을 만들어냄.
어셈블리 코드	기계어 명령을 사람이 이해하기 쉬운 형태로 표현한 저 수준 프로그래밍 언어 어셈블리 코드를 알지 못해도 코딩을 할 수 있지만, 최적화적인 측면에서 결국 어셈블리어를 이해해야 최적화가 가능 또한 보안 관련 이슈를 다루기 위해서도 필요함.

 

프로그램의 인코딩

역 어셈블러로 인해 해석할 수 있게 된 바이너리 코드

인코딩 과정	C 전처리기가 #include로 명시된 파일을 코드에 삽입해주고, #define으로 선언된 매크로를 치환해준다. 컴파일러는 소스코드를 어셈블리어로 변경 어셈블러는 어셈블리어를 바이너리 목적코드로 변경 마지막으로 링커는 내가 선언해준 전역값들의 주소를 하나의 파일로 이어준다. (Spring의 DI를 보는것 같았음)
ISA	Instruction Set Assembly 의 약자로, 소스코드를 컴파일할때 사용하는 각 CPU에 맞는 어셈블리어로 변환해주는 메뉴판 같은 거라고 이해했음 Instruction set은 인스트럭션의 집합으로, 즉 컴파일 대상인 소스코드 전체를 의미함 여기서 ISA 양식에 맞게 소스코드를 어셈블리어로 컴파일

 

 

어셈블리어 너무 재밌다.

인스트럭션이 어떻게 돌아가는지 눈에 보이니깐 그동안 공부했던 CS 지식이 머릿속에서 펼쳐지는 느낌