[04.03/week03]TIL

오늘 한줄 요약

한주가 마무리 됐으니 신나요... 물론 다시 한주의 시작입니다.

오늘 공부한 것

• BOJ(1388, 2667)
• CSAPP 3.0 ~ 3.4

새로 배우게 된 것

BOJ

1388

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

일단 DFS로 풀려고 했다.
이유는 탐색 방향이 가로 한방향 혹은 세로 한방향으로 정해져있어서 계속 다른거 만날때까지 탐색하는 것이다.

그래서 DFS로 구현하려 했는데 뭔가 DFS 코드가 안떠올라서 BFS로 냅다 풀었다.

# 구할 것 : 나무판자 개수
# 1. 입력받기
# 2. 2차원 배열 BFS -> - 케이스, | 케이스로 분리해서 생각
# BFS를 돌다가 다른거 만나면 스탑 => 그게 나무판자 하나
# 3. count 리턴

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

N, M = map(int, input().split())
floor = [list(input().rstrip()) for _ in range(N)]
visited = [[False] * M for _ in range(N)]

count = 0

def bfs(graph, y, x):
  queue = deque([(y, x)])
  while queue:
    y, x = queue.popleft()
    visited[y][x] = True
    if graph[y][x] == '-':
        nx = x + 1
        if 0 <= nx < M and not visited[y][nx] and graph[y][x] == graph[y][nx]:
          queue.append((y, nx))
          visited[y][nx] = True
    else:
        ny = y + 1
        if 0 <= ny < N and not visited[ny][x] and graph[y][x] == graph[ny][x]:
          queue.append((ny, x))
          visited[ny][x] = True


for i in range(N):
  for j in range(M):
    if not visited[i][j]:
      bfs(floor,i,j)
      count += 1

print(count)

다시보니 방문처리도 두번이나 하고, 값 비교시에도 idx 활용이 아니라 '-'이나 '|' 으로 바로 비교했다면 더 깔끔한 코드가 되었을 것 같다.
시간에 대한 압박이 있다보니 일단 돌아가게만 만드는데 급급했다...

• DFS 풀이

import sys
sys.setrecursionlimit(10000)

n, m = map(int, input().split())
board = [list(input()) for _ in range(n)]
visited = [[False] * m for _ in range(n)]

def dfs(x, y):
    visited[x][y] = True
    if board[x][y] == '-':
        ny = y + 1
        if ny < m and not visited[x][ny] and board[x][ny] == '-':
            dfs(x, ny)
    else:  # '|'
        nx = x + 1
        if nx < n and not visited[nx][y] and board[nx][y] == '|':
            dfs(nx, y)

count = 0
for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            dfs(i, j)
            count += 1

print(count)

2667

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

이건 딱봐도 BFS고, 먼저 풀었던 바닥장식에서 방향 탐색만 4방향으로 늘리면 되겠다 싶어서 BFS로 빠르게 풀었다.

입력이 1 0 0 1 1 이런식이 아니라 10011 로 들어와서 입력받을때 의외로 잘못 받으신 동료분들이 많았다.

입력과 출력을 다시한번 체크하자.

# 구할 것 : 각 단지의 집 개수 오름차순 출력
# 1. 입력받기
# 2. BFS
# 시작을 1인 곳에서 시작
# Dx,dy 로 이동했는데 전부 0이면 단지가 끝
# 그러면 1의 개수를 합해서 result에 저장
# 3. result 오름차순 정렬 후 리턴

import sys
from collections import deque

N = int(input())
village = [list(map(int, list(input().rstrip()))) for _ in range(N)]
visited =[[False] * N for _ in range(N)]

result = []

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

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


for i in range(N):
  for j in range(N):
    if not visited[i][j] and village[i][j] == 1:
      bfs(village,i,j)

print(len(result))
print(*sorted(result), sep='\n')

CSAPP ~ 3.4

그냥 가장 중요한 건 이거였다.

3.0 개요

• 목표: x86-64 어셈블리어를 통해 C 코드가 기계어로 변환되는 과정을 이해
• 핵심 주제:
  • 데이터 표현과 연산
  • 제어 흐름 (조건문, 반복문)
  • 함수 호출 (스택 사용)
  • 자료구조의 메모리 표현
  • 버퍼 오버플로우, 디버깅(GDB)
  • 부동소수점 연산

---

3.1 역사적 관점

• 8086 (1978): 16비트 마이크로프로세서
• 8087: 부동소수점 보조 프로세서
• 32비트(4GB), 64비트(16EB)로 확장
• ISA (Instruction Set Architecture): CPU가 이해하는 명령 체계
  • x86-64가 우리가 배우는 ISA

---

3.2 프로그램의 인코딩

• 컴파일 흐름

.c → .s → .o → 실행 파일

단계	명령어	생성물
전처리	cpp	.i
컴파일	gcc -S	.s
어셈블	as	.o
링크	ld or gcc	실행파일

역어셈블

• objdump -d 파일.o: 기계어 바이트 → 어셈블리 형태로 디코딩
• 인스트럭션은 1~15바이트 길이
• 메모리 주소만 보고 역추적 가능 (소스 없이도 가능)

---

3.2.3 어셈블리 형식

• .s 파일에는 많은 디렉티브 존재 (.globl, .section 등)
• 실전에서는 주석과 함께 간단하게 표현한 형태로 학습

---

3.3 데이터의 형식

크기	명령어	이름
1B	movb	byte
2B	movw	word
4B	movl	long
8B	movq	quad

• C의 기본 타입:
  int = 4B, long = 8B, long* = 8B

---

3.4 정보 접근하기

레지스터 구성 (x86-64)

• 16개 범용 레지스터 (%rax~%r15)
• 하나의 레지스터를 다양한 크기로 접근 가능:
  • %rax (64), %eax (32), %ax (16), %al (8 하위), %ah (8 상위)

명령	영향
movb	하위 1바이트만 변경
movw	하위 2바이트만 변경
movl	하위 4바이트 저장 + 상위 4바이트 0으로 설정
movq	전체 8바이트 덮어씀

---

스택 구조와 스택 포인터 %rsp

• 낮은 주소 방향으로 성장
• %rsp: 스택의 top을 가리킴 (최근 저장된 위치)
• 함수 호출 시 스택 구조:

[ 높은 주소 ]
리턴 주소
저장된 %rbp
지역 변수들
[ 낮은 주소 ]

---

오퍼랜드 타입 정리

타입	형식	설명
Immediate	$10	즉시값 (상수)
Register	%rax	레지스터
Memory	8(%rbx, %rsi, 4)	유효주소 계산 기반

→ 괄호가 있으면 메모리 참조, $가 있으면 즉시값

---

데이터 이동 명령어 (MOV)

• mov는 단순 복사
• 메모리 ↔ 메모리 직접 이동 ❌
  • 중간에 레지스터를 반드시 거쳐야 함

예:

movq (%rsi), %rax
movq %rax, (%rdi)

---

스택 연산 명령어

명령어	내부 동작
pushq %reg	subq $8, %rsp + movq %reg, (%rsp)
popq %reg	movq (%rsp), %reg + addq $8, %rsp

---

예제 요약

// multstore.c
void multstore(long x, long y, long *dest){
    long t = mult2(x, y);
    *dest = t;
}

→ 어셈블리:

pushq %rbx
movq %rdx, %rbx
call mult2
movq %rax, (%rbx)
popq %rbx
ret

공부하다가 아쉬운 점

골드라고 해서 살짝 기죽고 들어가서 풀수 있는데 못푼 게 조금 있다.
그리고 CSAPP 에서 C언어 개념이 살짝씩 나오니까 글이 1도 읽히지가 않는다...ㅠ