크래프톤 정글 - TIL

2178. 미로탐색 BFS(Breadth First Search, 너비 우선 탐색)으로 해결 시작점을 1로 두고 기존값을 더해가면서 최단 거리 계산 import sys from collections import deque input = sys.stdin.readline y, x = map(int, input().split()) graph = [list(map(int, input().strip())) for _ in range(y)] for i in range(y): for j in range(x): if graph[i][j] == 1: graph[i][j] = 0 else: graph[i][j] = -1 visited = [[0] * x for _ in range(y)] deq = deque() dx =..

트라이(Trie) 문자열에서의 검색을 빠르게 해주는 자료구조 장점 M개의 문자로 구성된 문자열을 추가와 탐색하는 시간 복잡도는 O(M) 문자열을 빠르게 탐색할 수 있음 단점 필요한 메모리의 크기가 너무 큼 모두 소문자로만 이루어졌다고 해도, 26개의 공간이 필요 플로이드 와샬(Floyd-Warshall) 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 알고리즘(방향, 음수 상관없음 / 싸이클이 발생하면 안됨) 단계마다 ‘거쳐 가는 노드’를 기준으로 알고리즘 수행 2차원 테이블에 최단 거리 정보를 저장 DP 알고리즘에 해당 시간 복잡도는 O(N^3) 노드의 개수가 N개 일 때, N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는 모든 경로'를 고려한다. ..

1260. DFS와 BFS DFS(Depth First Search, 깊이 우선 탐색), BFS(Breadth First Search, 너비 우선 탐색)으로 구현 Stack과 Queue를 사용하고 방문처리를 통해 탐색 import sys from collections import deque input = sys.stdin.readline n, m, v = map(int, input().split()) arr = [[] for i in range(n + 1)] visited = [False for _ in range(n + 1)] deq = deque() for i in range(m): a, b = map(int, input().split()) arr[a].append(b) arr[b].append(a)..

프로세스(Process) 실행중인 프로그램을 나타냄 프로세스의 문맥(Context) 프로그램이 무엇을 어떻게 실행했고, 현재 시점에 어떠한 상태인지 나타내기 위한 요소 CPU의 수행 상태를 나타내는 하드웨어 문맥 Program Counter 각종 레지스터 프로세스의 주소 공간 code, data, heap, stack 프로세스 관련 커널 자료 구조 PCB(Process Control Block) -> 프로세스가 실행될 때마다 관리하는 구조체 생성(이중 연결 리스트) 운영체제가 각 프로세스를 관리하기 위해 프로세스당 유지하는 정보 OS가 관리상 사용하는 정보 프로세스 ID, 프로세스 상태 스케쥴링 정보, 우선순위 CPU 수행 관련 하드웨어 값 Program Counter, 레지스터 메모리 관련 code, ..

인터럽트 하드웨어 인터럽트 timer의 인터럽트 컨트롤러의 인터럽트 : 요청한 I/O 작업이 끝났다는 것을 CPU에게 알림 트랩(Trap, 소프트웨어 인터럽트) Exception : 프로그램이 오류를 범한 경우 (ex. 0으로 나누는 연산, 사용자 프로그램에서 운영체제에 접근 등) System call : 프로그램이 커널 함수를 호출하는 경우 인터럽트 벡터 인터럽트의 처리 루틴의 주소를 가지고 있음 인터럽트 처리 루틴 인터럽트를 처리하는 커널 함수 — 인스트럭션이 실행되고 다음 인스트럭션이 실행되기 전에 I/O컨트롤러나 timer에서 보낸 인터럽트가 들어왔는지 체크 — 만약 인터럽트가 들어왔다면 지금 하던 작업을 멈추고(Program Counter 저장) CPU 제어권을 운영체제(OS)에게 넘김 — 운영..

트리 구조 트리는 노드(Node)와 노드들을 연결하는 간선(Edge)으로 연결된 비선형 자료구조 관련 용어 노드(Node) 트리를 구성하는 기본 용소 노드에는 키 또는 값과 하위 노드에 대한 포인터를 갖고 있음 노드 : A, B, C, D, E, F, G, H, I ,J 간선(Edge) 노드와 노드 간의 연결선 루트 노드(Root node) 트리 구조에서 부모가 없는 최상위 노드 루트 노드 : A 부모 노드(Parent node) 자식 노드를 가진 노드 H, I의 부모 노드는 D 자식 노드(Child node) 부모 노드의 하위 노드 노드 D의 자식 노드는 H, I 형제 노드(Sibling node) 같은 부모를 가진 노드 H, I은 같은 부모를 가진 형제 노드 리프 노드, 외부 노드, 단말 노드(Lea..

알고리즘 문제풀이 2468. 안전영역 그래프 탐색으로 모든 좌표 순회 방문여부(visited)와 높이로 조건 설정 시간초과 발생.. from collections import deque import sys input = sys.stdin.readline dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] deq = deque() def search(graph, height): visited = [[0]*n for i in range(n)] count = 0 for y in range(n): for x in range(n): if graph[x][y] > height and visited[x][y] == 0: deq.append((x, y)) count += 1 visited[x][y] =..