목록카테고리 (60)
교대최소제곱법
다익스트라 알고리즘 하나의 정점에서 다른 “모든” 정점으로 가는 최단 경로를 측정하는 알고리즘 다시 다익스트라 구현 순서도 출발 노드 설정 출발 노드를 기준으로 각 노드의 최소비용 저장 방문하지 않은 노드 중에서 가장 비용이 적게드는 노드 선택 (이동한다는 개념을 가져야한다) 해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소비용 갱신 3번 4번 과정 반복 어떻게 구현하나요? DP + heap을 활용한다 DP로 최단거리를 기억하고 heap을 통해 토탈 최단 거리를 구해 최단경로를 추적한다 힙을 쓰면 O(n log n), 안 쓰면 O(N**2) → 힙은 속도에 이점만 있을 뿐 다익스트라와는 관계가 없다 + 힙정렬은 불안정정렬이다 따라서 다익스트라에서도 같은 거리여도 어떤 값이 먼저 나올지는 정해지지..
DFS 깊이우선문제 sys를 import할 수 있다면 sys.setrecursionlimit(int(1e9))를 호출해야 에러가 안뜬다 사이클을 확인할때 사용 먹고 또 이동하고 먹고 또 이동하고를 나타낼때 그래프의 경우, 가중치 또는 특정 기준을 따라 탐색 방향의 우선순위를 결정한다 최대값 구할 때 "최대값보다 작으면" 이란 기준을 설정하고 찾는다 시간복잡도 N이 노드의 개수, E가 간선의 개수일 때 인접 리스트: O(N + E) 인접 행렬: O(N^2) 예제 풀이 프로세스 재귀함수를 사용 입력값 받기 방문여부를 남기는 그래프 만들기 탐색조건 시작점을 불러오고 방문했는지 여부확인하고 탐색 not visited[][] and graph[][] == 1 탐색 일단 방문기록 남기고 4방향으로 움직인다 조건에 ..
BFS 너비우선탐색 문제 최단거리를 구할때 사용 가장 먼저 찾아내는게 최단거리이다 -> BFS 사용이유 시간복잡도 N이 노드의 개수, E가 간선의 개수일 때 인접 리스트: O(N + E) 인접 행렬: O(N^2) 예제 풀이 프로세스 deque을 사용 입력값 받기 그래프크기 N, M = map(int, input().split()) 그래프 모양 board = [list(map(int,input().split())) for _ in range(N)] 볼 위치파악 for i for j append 구문으로 현위치를 파악하고 from collection import deque에 넣어놓는다 방문여부를 기억하려면 넣어두기 visited[i][j] = 1 이거로 장난 칠수도 있다 기억했다가 안했다가를 바꾸는 문제도 ..
시간복잡도 줄이는 법 최대 1억이 넘는가를 확인한다 1억 = 1초 순서대로 시간을 줄여보자 O(n) 탐색보다는 hashmap을 쓰자 단, hash도 저격당하면 O(n)임 -> 100점은 못 받는다고 보면 된다 (하지만 풀었죠?) 정렬이 되어 있다면 binary search 이진 탐색 -> O(log n) 정렬 -> O(NlogN) 투포인터 알고리즘 -> O(N) 리스트를 순차적으로 접근해야할 때 사용가능 ex) 연속 수열의 합 누적합 배열을 이용 -> O(N)으로 구현 가능 DP문제처럼 누적합 배열의 이전 값을 이용하면 O(N)으로 구현
파일과 디렉토리 파일 : 논리적 단위 디렉토리 : 트리 구조 디렉토리 디렉토리 엔트리 : 특별한 파일로 간주 파일에 데이터가 담겨져 있다면, 디렉토리에는 정보가 담기는 거임 파일 이름 + 파일이 보조기억장치에 저장된 위치 파일 할당 방법 연속적 할당 → 외부 단편화 문제 발생 불연속적 할당 연결 할당 : 다음 블록 주소를 저장해서 연결 리스트로 관리 but 순차적으로 접근해야 원하는 부분에 접근할 수 있어 느리다 + 오류 발생시 끝 색인 할당 : 색인 번호를 관리하는 블록을 만든다 파일 시스템 포매팅 : 파일 시스템을 결정함 FAT 파일 시스템 : 블록 주소를 테이블(FAT)로 관리 루트 디렉토리 → 하위 디렉토리 → 첫 번째 블록 주소 발견 → FAT에서 다음 주소 발견 → … 유닉스 파일 시스템 : ..
메모리 할당 스와핑 : 안 쓰는 메모리를 보조기억장치로 보내는 방법 → 요구하는 메모리가 실제 메모리보다 크더라도 실행 가능 but 애초에 덩어리가 커버리면 실행 불가함 메모리 할당 알고리즘 최초 적합 / 최적 적합 / 최악 적합 : 다 비효율적임 → 외부 단편화 때문에 *외부 단편화 : 메모리 사이사이 공간이 발생, 메모리 낭비 외부 단편화 해결방법 메모리 압축 : 잘 안씀 페이징(goat) 페이징 모든 프로세스를 페이지라는 일정한 크기로 짜르고 메모리를 프레임으로 일정하게 짤라서 할당 페이지 단위로 스와핑도 가능(페이지 인, 페이지 아웃) = 프로세스에서 필요한 페이지만 담으면 되는거 아님? → 큰 프로세스도 실행 가능 또한 메모리에 불연속적으로 흩어 놓아 저장 가능 → 순차적 실행에 어려움이 있음 ..
CPU 스케쥴링 우선순위 : 입출력 작업이 많은 프로세스 > cpu 작업이 많은 프로세스 스케쥴링 큐 : 자원마다 큐를 생성 → 순서대로 나가는건 아님 대표적으로 준비 큐, 대기 큐 가 있다 선점형, 비선점형 스케쥴링 선점형 : 이미 사용하고 있어도 시간이 지나면 빼앗아서 사용 → 오버헤드가 많이 발생 *오버헤드 : 프로세스 처리를 위해 간접적으로 들어가는 시간 비선점형 : 앞 프로세스가 종료나 대기가 되어야 사용 스케쥴링 알고리즘 선입선처리 : 비선점 최단작업 : 선점 or 비선점 라운드 로빈 : 선입 선처리 + 타임 슬라이스 → 선점형 = 타임 슬라이스의 크기가 매우 중요하다 최소 잔여 시간 우선 : 최단 작업 + 라운드 로빈 우선 순위 : 기아 현상 → 우선 순위가 낮은 프로세스는 끝도 없이 밀림 ..
모든 프로그램은 실행을 위해 자원을 필요로 한다 커널 영역에 적재되는 프로그램 오류메세지에 대한 깊은 이해가 가능하다 커널 : 핵심적인 서비스를 담당하는 부분 유저 인터페이스는 커널이 아님 이중모드 : 플래그로 구별 가능, 사용자모드 vs 커널모드 시스템 호출 : 커널모드로 전환하기 위한 방법 → 소프트웨어 인터럽트 프로세스(실행 중인 프로그램) 관리 자원 접근 및 할당 : cpu 스케쥴링, 메모리(페이징, 스와핑), 입출력장치 파일 시스템 관리 프로세스 프로세스 제어 블록 PCB : 프로세스 관련 정보를 저장하는 자료 구조 → 커널 영역에 저장 프로세스 ID (PID) 레지스터 값 : 자신의 실행 차례가 오면 이전에 사용한 레지스터 값을 복원해 실행을 재개하기 위해 저장 프로세스 상태 cpu 스케쥴링 ..