24.01.25 시험,CSAPP 3.10.2 , Algorithm,코어타임

시험

• 문제를 풀 때 너무 조급해서 막 접근했던 것 같다.
• 다음에 풀 때는 조금만 더 생각해서 하는게 오히려 시간을 줄일 수 있을 것같다.
• BFS DFS 문제에 대해서 잘 생각해보자

1388

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().split())
floor = []
for i in range(n):
    floor.append(list(map(str,sys.stdin.readline().rstrip())))
visited = [[False for i in range(m)] for i in range(n)]
cnt = 0
def bfs(x,y):
    q = deque()
    q.append((x,y))
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]
    visited[x][y] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            if floor[x][y] == '-':
                ny = y + dy[i]
                if ny<0 or ny>=m:
                    continue
            elif floor[x][y] == '|':
                nx = x + dx[i]
                if nx<0 or nx>=n:
                    continue
            if floor[x][y] == '-':
                if floor[x][ny] == floor[x][y] and visited[x][ny] == False:
                    q.append((x,ny))
                    visited[x][ny] = True
                else:
                    continue
            elif floor[x][y] == '|':
                if floor[nx][y] == floor[x][y] and visited[nx][y] == False:
                    q.append((nx,y))
                    visited[nx][y] = True
                else:
                    continue

for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            bfs(i,j)
            cnt += 1
                
print(cnt)

• BFS로 풀었지만 문제의 내용상 DFS로 풀었으면 조금 더 편하게 풀지 않았을까 생각한다.
• 그래도 한 문제 풀었다!!
• 치타 달린다!!

CSAPP

3.10.2 실제 적용하기 : GDB 디버거 사용하기

• GDB를 사용하며, 프로그램의 실행을 정교하게 제어하면서 실행되는 프로그램을 관찰하여 프로그램의 동작을 분석할 수 있다.
• 일반적인 방법은 브레이크 포인트(BreakPoint)를 프로그램에서 관심이 있는 부분 근처에 설정하는 것이다.
• 함수의 시작 직후나 프로그램의 특정 주소에 설정할 수 있다. 프로그램 실행중에 브레이크 포인트를 만나게 되면, 프로그램은 실행을 중단하고, 제어를 사용자에게 넘긴다. 브레이크 포인트로부터 레지스터나 메모리 위치의 값을 다양한 형식으로 조사할 수있다.

Algorithm

그리디 알고리즘(Greedy Algorithm)

• 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론
• 각 단계에서 최적이라고 생각되는것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘 이다.
• 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 ‘근시값’을 목표로 하고 있다.

그리디 알고리즘 주요속성

1. 탐욕선택속성(Greedy Choice Property)
   1. 각 단계에서 ‘최선의 선택’을 했을때 전체 문제에 대한 최적해를 구할 수 있는 경우
2. 최적부분구조(Optimal Substructure)
   1. 전체 문제의 최적해가 부분 문제의 최적해로 구성 될 수 있는 경우
   2. 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 다음 이를 조합해 전체 문제의 최적해를 구하는 것을 의미

단계

1. 문제의 최적해 구조를 결정한다
2. 문제의 구조에 맞게 선택절차를 정의한다. - 선택절차
3. 선택절차에 따라 선택수행
4. 선택된 해가 문제의 조건을 만족하는지 검사한다. - 적절성검사
5. 조건을 만족하지 않으면 해당 해를 제외한다.
6. 모든 선택이 완료되면 해답을 검사한다 - 해답검사
7. 조건을 만족하지 않으면 해답으로 인정되지 않는다.

• 선택절차 (Selection precedure) : 현재상태에서 최적인 선택을 한다
• 적절성 검사(Feasibility check) : 선택한 항목이 문제의 조건을 만족하는지 확인한다
• 해답검사(Solution check) : 모든 선택이 완료, 최종선택이 문제의 조건을 만족 시키는지 확인한다.

동적계획법(DP : Dynamic Programming)

• 작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘
• 중복 계산을 줄여서 계산속도를 높일 수 있으며 경우의 수가 많은 경우에도 효율적으로 계산할 수 있다 일반적으로 재귀로 구현되며 메모이제이션(memoization) 기법을 사용하여 중복 계산을 피한다
  • 메모이제이션 - 이전에 계산된 결과를 저장하고 다음에 동일한 계산에 필요할 때 저장된 결과를 이용하여 중복계산을 피함으로서 성능을 향상 시킬 수 있다.

구현단계

1. 문제를 하위 문제로 쪼갠다
2. 하위 문제를 재귀적으로 해결한다
3. 결과를 저장한다(메모이제이션, 테블레이션)
4. 저장된 결과를 이용해 큰 문제를 해결한다.

동적 계획법 조건

1. 최적부분구조(Optimal Substucture)
   1. 전체 문제의 최적해가 부분 문제의 최적해로 구성 될 수 있는 경우
   2. 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 다음 이를 조합해 전체 문제의 최적해를 구하는 것을 의미
2. 중복부분문제(Overlapping Subproblems)
   1. 동일한 작은 문제를 반복적으로 해결해야하는 성질

동적계획법 종류

1. 탑 다운(Top-down) : 큰 문제를 해결하기 위해 작은 문제를 호출하는 형식
   1. 장점 : 작은 문제들의 결과값을 저장함으로써 동일한 계산을 반복하지 않아 시간복잡도도 감소한다 - 메모이제이션
   2. 단점 : 스택오버플로우 발생 가능성이 있다 - 재귀 때문에
2. 바텀 업(Bottom-up) : 작은 문제부터 차례대로 해결해 나가는 방식
   1. 장점 : 부분 문제의 해를 저장하고 이를 활용하여 다음 문제를 해결함으로써 시간복잡도도 감소한다. - 테블레이션
   2. 단점 : 초기값을 설정해줘야 하고, 작은 문제들의 결과값을 임시적으로 저장해둘 공간이 필요하다.

코어타임

분할정복은 중복이 없다.

• 코어타임에서 그리디 알고리즘과 동적계획법을 하면서 작은 문제로 쪼개고 합치고 해결하길래 다 분할정복의 일종인줄 알았는데, 인우가 머지소트로 설명해주면서 분할정복에는 중복이 없기에 비슷하지만 다른것이라고 알려줬다.
• 신기방기스..
• 오늘의 TIL 핵심 키워드!!!