2025.04.07

TIL(TODAY I LEARN)

---

• WEEK04 :
  동적 프로그래밍, 그리디 알고리즘
  CSAPP 3장. 프로그램의 기계 수준 표현 (특히 3.4, 3.7, 3.8)

• 3.8 공부 및 알고리즘 풀이

---

3.8 배열의 할당과 접근

• C에서의 배열 : 스칼라 데이터를 보다 큰 자료형으로 연계시키는 수단
• 배열 인덱스를 사용하는 코드는 컴파일러에 의해 주소 계산으로 바뀜.
  EX): A[i]는 A + i * sizeof(type) 형태의 주소 계산으로 변환
  A는 배열의 시작 주소를 가리킴

3.8.1 기본 원리

1. 메모리 할당: 타입 T의 크기 L에 N을 곱한 만큼의 메모리를 연속적으로 할당.
2. 식별자 제공: A는 배열 시작 주소인 xA를 가리키는 포인터처럼 작동.

Array	Element Type
P	int
Q	short
R	int ** (pointer)
S	double * (pointer)
T	short * (pointer)

• 포인터 배열의 경우, 포인터 크기 (보통 8바이트 on x86-64) 가 배열 원소의 크기임.

3.8.2 포인터 연산

• 포인터 연산에서 p + i는 xp + L × i로 계산됨. (L: 포인터가 가리키는 데이터 타입의 크기)
• &Expr → 해당 객체의 주소
• *AExpr → 해당 주소에 저장된 값
• Expr == *&Expr
• A[i]는 *(A + i)와 동일함
• 배열과 포인터 모두 [] 연산을 사용할 수 있음

3.8.3 다중 배열

• 행 우선 방식으로 저장된다.

int A[5][3];

==

typedef int row3_t [3];
row3_t A[5];

위 아래 선언문이 동일함.
각 행에 들어가는 열의 사이즈 만큼 선언

T D[R][C];

• T: 데이터 타입 (예: int → 4바이트, long → 8바이트)
• R: 행 개수
• C: 열 개수

&D[i][j] = xD + L × (C × i + j)

• L: 타입 T의 크기 (바이트 단위)
• xD: 배열 시작 주소

3.8.4 고정크기의 배열

• 배열 크기가 고정되어 있을 때 (#define N 16 같은 경우)
• 컴파일러는 인덱스 연산을 포인터 기반 연산으로 바꿔서 루프 최적화함
• 효과적인 이유:
  • 계산량 줄이고
  • 반복문 조건 단순화하고
  • 캐시 친화적인 접근 가능
• 3.37(a) →(b)의 경우 : j인덱스 없이 메모리만 순회해 성능 UP
  • 곱셈 없음
  • 조건은 단순 포인터 비교 (!=)
  • 메모리 접근은 그냥 역참조 (*ptr)

Figure 3.37	최초 코드(a)	최적화된 코드(b)
항목	인덱스 방식 (j)	포인터 방식 (N 사용)
루프 인덱스	있음 (j++)	없음 (포인터 비교로 루프 조건 판단)
주소 계산	매 반복 A[i][j], B[j][k] 계산	처음 주소만 계산하고, 이후는 ++, +=N
명령어 수	비교적 많음	훨씬 적음
메모리 접근	배열 인덱스 → 주소 계산 필요	주소 직접 계산 후 단순 이동
레지스터 사용	인덱스, 곱셈 등 필요	포인터 2~3개로 충분

3.8.5 가변크기의 배열

• 예전 C
  • malloc(), calloc() 등으로 직접 동적 메모리 할당해야 함
  • 그리고 다차원 배열처럼 쓰고 싶으면 1차원 배열처럼 풀어서 직접 인덱싱

     int *A = malloc(n * n * sizeof(int));
     A[i * n + j]; // 직접 주소 계산

• C99 이후

  • 배열의 크기를 변수로 지정 가능

  • A[i][j] 형식 그대로 사용 가능

    int n = 100   // 반드시 n이 배열 앞에 선언!
    int A[n][n];  // n은 변수임!
    A[i][j];      // 파이썬처럼 접근 가능!

항목	예전 C : malloc/calloc 방식	C99 VLA 방식 (int A[n][n])
메모리 할당 시점	런타임	런타임
배열 선언 방식	포인터 사용	일반 배열처럼 선언
인덱싱	직접 주소 계산	A[i][j] 바로 사용 가능
코드 간결성	복잡	간단, 직관적
성능	조금 더 제어 가능	일반적으로 충분히 빠름

• 고정 배열에서는 3i, 4i 같은 건 leaq 로 계산 가능 (덧셈 + 시프트)
• 가변 배열에서는 n * i가 imul이 필요함 (곱셈)
• 일부 CPU에서는 곱셈이 상대적으로 느릴 수 있음 → 성능에 영향 있음

---

오늘의 알고리즘 풀이

11053 - 가장 긴 증가하는 부분 수열 - 실버2

문제 링크 - https://www.acmicpc.net/problem/11053

내 코드

    import sys
    
    input = sys.stdin.readline
    
    N = int(input().strip())
    
    A = list(map(int,input().split()))
    
    DP = [1] * N #수열 길이의 초깃값은 1임
    
    for i in range(N):
        for j in range(i):
            if A[i] > A[j]:
                DP[i] = max(DP[i],DP[j]+1)
                
    print(max(DP))

• 분명 분할 정복때 해본 것 같았는데 생각나지 않았음
• i 이전 j수열 중 가장 긴것 +1

문제 분류

• 다이나믹 프로그래밍

---

1541 - 잃어버린 괄호 - 실버2

문제 링크 - https://www.acmicpc.net/problem/1541

내 코드

 import sys
 
 input = sys.stdin.readline
 
 n = input().split(sep="-")
 
 total = sum(map(int,n[0].split(sep = "+")))
 
 for x in n[1:]:
     total -= sum(map(int,x.split(sep = "+")))
 
 print(total)

문제 분류

• 수학
• 그리디 알고리즘
• 문자열
• 파싱

  ---

1931 - 회의실 배정 - 골드5

문제 링크 - https://www.acmicpc.net/problem/1931

내 코드

    import sys
    
    input = sys.stdin.readline
    
    n = int(input().strip())
    
    meetings = []
    for _ in range(n):
        x, y = map(int,input().split())
        meetings.append((x,y))
    
    meetings.sort(key= lambda x : (x[1], x[0]))    
    
    result = []
    end_time = 0
    for i,j in meetings:
        if end_time <= i: 
            result.append((i,j))
            end_time = j
            
    print(len(result))

문제 분류

• 그리디 알고리즘
• 정렬

---

1946 - 신입사원 - 실버1

문제 링크 - https://www.acmicpc.net/problem/1946

내 코드

   import sys
   from heapq import heappop,heappush
   input = sys.stdin.readline
   
   for _ in range(int(input().strip())):
       n = int(input().strip())
       rank = []
       for _ in range(n):
           
           rank.append(tuple(map(int,input().split())))
       
       rank.sort() 
       result = []
       heappush(result,(rank[0][1],rank[0][0]))
       
       for i in range(1,n):
           if rank[i][1] > result[0][0]:
               continue
           x, y = rank[i]
           heappush(result,(y,x))
       print(len(result))
       

문제 분류

• 그리디 알고리즘
• 정렬

---