크래프톤 정글 week02, day16 - 이론 공부, 알고리즘 문제

캐시 메모리를 사용하면 컴퓨터 시스템의 성능이 왜 향상될까

• 지역성(locality)은 프로그램이 메모리를 접근할 때 특정 부분을 집중적으로 사용하는 경향을 나타낸다.
  • 시간적 지역성(Temporal Locality)
    • 한 번 접근된 데이터는 가까운 미래에 다시 접근될 가능성이 높다는 원리
    • ex) 루프 내에서 반복적으로 사용되는 변수
  • 공간적 지역성(Spatial Locality)
    • 메모리의 특정 주소에 접근한 후, 그 주변 주소에 있는 데이터에 접근될 가능성이 높다는 원리
    • ex) 배열이나 연속적인 메모리 블록에 접근할 때
• 캐시 메모리는 이러한 지역성 원리를 활용해 자주 사용되거나 연속적으로 사용될 가능성이 높은 데이터를 미리 캐시에 저장하여 CPU는 필요한 데이터를 캐시에서 빠르게 찾을 수 있다.

​

프로세스(Process)와 쓰레드(Threads)의 차이

• 프로세스
  • 독립적으로 실행되는 프로그램의 인스턴스
  • 자체적인 주소 공간, 메모리, 데이터 스택 및 다른 시스템 자원을 갖는다.
• 쓰레드
  • 프로세스 내부의 실행 흐름 단위
  • 프로세스의 자원과 주소 공간을 공유하면서 실행된다.

• 자원 공유
  • 프로세스는 독립적인 메모리 공간과 시스템 자원을 가지므로, 프로세스간 자원 공유는 IPC(Inter-Process Communication) 메커니즘을 통해 이루어진다.
    • IPC : 프로세스들 사이에 서로 데이터를 주고받는 행위
  • 같은 프로세스 내의 쓰레드들은 코드, 데이터 및 시스템 자원을 공유한다.

​

B-tree 인덱스를 사용할 때와 사용하지 않을 때의 데이터 검색 시간 복잡도

• B-tree 인덱스를 사용할 경우
  • 데이터 검색 시간 복잡도는 O(log n)이다.
    • n : 데이터 베이스 내의 레코드 수
    • B-tree 구조는 균형 이진 트리와 유사하므로 데이터를 효율적으로 검색할 수 있다.
• B-tree 인덱스를 사용하지 않을 경우
  • 선형검색을 수행해야 하므로 검색 시간 복잡도는 O(n)이다.

​

• 따라서 데이터 양이 많을수록 B-tree 인덱스를 사용하는 것이 성능 면에서 훨씬 유리하다.

---

바이러스

• 네트워크로 연결되어 있는 컴퓨터들은 하나가 감염되면 전부 감염된다. 숙주를 제외한 컴퓨터 개수 구하기

import sys

# 컴퓨터 개수와 방문현황, 연결현황을 인자로 받아
def virus(computer, visited, connect):
    # 해당 컴퓨터에 방문 체크
    visited[computer] = True
    
    # 컴퓨터들을 돌며 방문안한 곳이 있으면 재귀
    for i in connect[computer]:
        if not visited[i]:
            virus(i, visited, connect)


# 노드 computer, 간선 network, 방문확인 visited, 연결확인 connect
computer = int(sys.stdin.readline())
network = int(sys.stdin.readline())

visited = [False] * (computer+1)
connect = [[] for _ in range(computer+1)]

# 컴퓨터끼리 연결되게 값 적용
for _ in range(network):
    pc1, pc2 = map(int, sys.stdin.readline().split())
    connect[pc1].append(pc2)
    connect[pc2].append(pc1)

# 1번 컴퓨터를 시작으로 visited값이 True인것을 찾기
virus(1, visited, connect)

# 자기를 제외한 연결되어 감염된 컴퓨터 갯수
print(visited.count(True)-1)

dfs를 열심히 학습하고 풀어보는 문제였는데 상황극처럼 바이러스 걸린 컴퓨터 찾기 같은 내용이 나오니까 흥미가 생겨 재밌게 풀었던 것 같다.

재귀를 사용한 dfs와 데크를 사용한 bfs의 기본 알고리즘 코드를 열심히 외워서 기본적으론 짤 수 있게 되었다.

​

미로 탐색

• 입력값으로 행과 열 길이가 주어지고 그 안에서 [0, 0]부터 [n, m]까지 걸리는 최소 거리를 구하기

# [0,0]에서 [n,m]으로 이동할 때 지나야하는 최소 칸 수 미로찾기
from collections import deque

# 상하 movex, 좌우 movey를 지정. 이동할때 좌표 변화
movex = [-1, 1, 0, 0]
movey = [0, 0, -1, 1]

# x좌표와 y좌표를 받는 미로 찾기 함수
def maze_runner(x, y):
    # 데큐를 사용하고 현재 좌표 추가 (0, 0)
    queue = deque()
    queue.append((x, y))

    # 큐가 없을 때까지 반복. 큐값에서 처음 들어온값을 pop해 x, y에 저장
    while queue:
        x, y = queue.popleft()

        # 상하좌우를 확인해야 해서 4번 반복하고 nx, ny값에 담는다.(좌표갱신)
        for i in range(4):
            nx = x + movex[i]
            ny = y + movey[i]

            # 만약 nx가 0보다 작거나 n보다 크거나 같을 때
            # ny가 0보다 작거나 m보다 크거나 같을 때
            # 즉 갱신한 좌표가 미로를 안 벗어났는지 확인
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            # 새로운 좌표가 벽이면 다음 방향으로 넘어간다.(지나가는 길은 1이기 때문)
            if maze[nx][ny] == 0:
                continue

            # 새로운 좌표로 이동가능하면 현재위치에서 이동하고 칸 수를 기록한 뒤 좌 큐에 저장
            if maze[nx][ny] == 1:
                maze[nx][ny] = maze[x][y] + 1
                queue.append((nx, ny))

    # 현재 위치의 이동칸 반환
    # 인덱스는 0에서 시작하므로 4행6열로 가정할 때 마지막은 [3][5]라 -1을 해줘야함
    return maze[n - 1][m - 1]

# 행 n, 열 m을 입력받기
# n, m = map(int, sys.stdin.readline().split())
n, m = map(int, input().split())

# 미로 변수를 만들고 다음 미로 값을 입력받음
maze = []
for i in range(n):
    maze.append(list(map(int, input())))

print(maze_runner(0, 0))

바이러스 풀어서 건방져졌던 본인에게 다시 겸손을 입힌 문제

좌표이동 개념은 학습하질 않아서 변수 만들때부터 애먹었다. 결국 지피티 선생님 도움으로 답을 확인하고 코드의 이해만 완료했다. 잘 생각해놨다가 나중에 여유있을 때 내 힘으로 다시 풀어보고 싶다.

​

특정 거리 도시 찾기

• 시작도시에서 도착 도시의 최단거리를 찾고 입력값과 같은 최단거리 도시 찾기

from collections import deque
import sys

# 연결작성 리스트, 출발점, 방문확인, 거리를 매개채로 받기
def fine_city(line, x, visited, dist):
    # 데크를 이용해 큐에 출발점 넣기
    queue = deque([x])
    # 방문확인을 True로 변환
    visited[x] = True

    # 큐가 없어질 때까지 반복
    while queue:
        # pop 변수에 가장 먼저 넣은 값을 pop하기
        pop = queue.popleft()

        # 연결점 리스트를 돌려 방문확인이 안된 곳이 있으면
        for i in line[pop]:
            if not visited[i]:
                # 큐에 그 값을 넣고 방문확인 체크, 거리에 1을 추가한다
                queue.append(i)
                dist[i] = dist[pop] + 1
                visited[i] = True
    # 값이 없을 때의 -1을 출력할 조건이 필요하기 때문에 넣음
    found = False
    # 간선만큼 돌려서 최단거리가 목표거리와 같으면 그 값을 출력하기
    for s in range(len(dist)):
        if dist[s] == k:
            print(s)
            found = True
    # 아니라면 -1을 출력하기
    if not found:
        print(-1)

# 노드 수 n, 간선 수 m, 최단거리 k, 출발점 x 입력
n, m, k, x = list(map(int, sys.stdin.readline().split()))
# 노드간의 연결점을 작성할 리스트
line = [[] for _ in range(n+1)]
# 방문확인 리스트
visited = [False] * (n+1)
# 간선 수만큼 반복을 돌리며 a와 b의 연결 관계를 line 리스트에 넣기
# 방향성이 있는 그래프이기 때문에 b에도 넣을 필요는 없다.
for i in range(m):
    a, b = list(map(int, sys.stdin.readline().split()))
    line[a].append(b)
# 거리를 입력할 리스트 생성
dist = [0] * (n+1)
# 함수 실행
fine_city(line, x, visited, dist)

열심히 공부해놨던 bfs알고리즘이 통했다. 노드를 탐색해 목적지의 도시를 가는 동안 방문체크와 거리를 확인하고 저장된 거리와 같은 도시를 찾아 출력했는데, 출력부분에서 원하는대로 잘 나오지 않아 애먹었다.

​

학습시간 : 10 ~ 25시