전체 글303 알고리즘 14 백트래킹 백트래킹 여러개의 후보해 중에서 특정 조건을 만족시키는 모든 해를 찾는 알고리즘 ex_) 미로 탈출 알고리즘 - 갈림길->무조건 왼쪽 - 막다른 곳이 나오면 되돌아 나와서 오른쪽 시도 - 뿌리에서 해를 찾기 시작 - 현재 부분해에서 선택 가능한 다음 부분해 목록을 조회 - 부분해를 하나씩 하나씩 방문 - 해가 될 수 있는 조건이면 위를 다시 실행 - 아니면, 이전 부분해로 돌아나와서 다른 부분해를 실행 - 위의 단계를 반복 ex) 미로 탈출 찾기 - 재귀호출 기반 백트래킹 Algorithm/BackTracking at main · Sukmin-LanternK/AlgorithmContribute to Sukmin-LanternK/Algorithm development by creati.. 2025. 4. 1. 알고리즘 13 탐욕 알고리즘 탐욕 알고리즘 - 최적해를 보장하지 않지만, 적정해를 빠르게 구해준다 - 1. 부분 문제의 최적해를 구함 -> 부분해 집합에 추가 - 2. 새로운 부분해 집합이 실행가능한지 확인 = 제약조건을 위반하는지 검사 - 3. 새로운 부분해 집합이 문제의 해인지 확인 -> 아직 완성 안됬을 경우 1번부터 반복 ex) 거스름돈 문제 - 단위가 큰 돈으로만 거스름돈을 만듦 - 손님에게 드려야 하는 액수 초과하는지 검사 - 동전 총액이 일치하는 지 검사 허프만 트리 - 압축 알고리즘 - 접두어 코드 (노-프리픽스 코드) - 이진트리를 통해서, 나타낸다 ; 데이터 = 잎노드데이터 / 경로 = 접두어코드 - 사전 작업 ; 가장 빈도가 낮은 순서대로 저장 - 해 선택 ; 빈도가 가장 작은 노드 2개를 선택 .. 2025. 3. 30. 알고리즘 12 동적계획법 동적계획법 - 1. 문제를 부분 문제로 나눈다 - 2. 가장 작은 부분 문제부터 해를 구한다 - 3. 테이블에 부분 해를 저장한다 - 4. 부분해를 이용하여 점차 상위 부분 최적해를 구한다 -> 일반적으로 사람이 수계산하는 피보나치 수열 푸는 방법이 동적계획법과 같다 LCS 알고리즘 ; Longest Common Subsequence ; 최장 공통 부분 수열 - 부분수열이란 ? 수열의 일부 요소를 제거한 것 - 최장공통부분수열 ? 두 수열의 부분 수열 중 제일 긴 것 Xi = / Yj = 의 문자열이 있다고 할 때, LCS_LENGTH(Xi,Yi) = 1) 0 : i =0 or j =0 2) LCS_LENGTH(Xi-1,Yi-1) + 1 : xi = yi 3) MAX(LCS_LENGT.. 2025. 3. 26. 알고리즘 11 분할 정복 분할 정복이란, 다음의 분할-정복-결합 순서대로 문제를 푸는 방법이다 분할 - 문제가 분할 가능할 경우 2개 이상의 하위 문제로 나눈다 정복 - 더 이상 분할 불가능한 경우 문제를 푼다 결합 - 정복을 통해 구한 답을 취함 분할 정복 예시 : 병합정렬 - 정렬할 데이터를 반으로 나눔 - 크기가 1이 될때까지 나눔 - 하위 데이터를 병합함 - 데이터가 하나가 될 때까지 병합함 Algorithm/DivideConquer at main · Sukmin-LanternK/AlgorithmContribute to Sukmin-LanternK/Algorithm development by creating an account on GitHub.github.com 2025. 3. 22. 알고리즘 10 알고리즘 성능 분석 알고리즘 성능 측정 기준 1. 정확성 2. 작업량 3. 메모리 사용량 4. 단순성 5. 최적성 알고리즘 수행 시간 분석 - 최악의 경우 수행 시간 ; 보장 되는 알고리즘 성능 - 평균의 경우 - 최선의 경우 ; 알고리즘이 낼 수 있는 최적 성능 한계 점근 표기법 ; 최고차항만으로 표기 - Big O 표기법; 최악의 경우 수행 시간 표기 / 점근적 상한 - Big Omega 표기법 ; 최선의 경우 수행 시간 표기 / 점근적 하한 - Big Theta 표기법 ; 점근적으로 자신의 증가율과 같은 증가함수 포함 2025. 3. 19. 알고리즘 9 문자열 탐색 1. 고지식한 탐색의 동작 방식 -문자 바이 문자로 등호 검증 2. 카프 라빈 알고리즘 - 해시함수 계산을 가볍게 단축시켜서 검증하는 방법 3. KMP 알고리즘 - 접두부와 접미부가 같은 경우, (Border = 경계) 접두부-접미부 일치한 탐색이 한 차례 끝나고 나면, 그 다음 탐색은 바로 접미부부터 시작하면 된다 - 정확히는 -> 일치하는 부분 문자열의 길이 - 경계의 길이만큼 이동 - 경계 정보 사전 계산 방법 4. 보이어-무어 알고리즘 - 불일치 발생 -> 불일치 문자가 본문에 없을 때 -> 일치한 패턴만큼 이동 - 나쁜 문자 이동 ; 불일치 발생 시, 패턴에서 본문 불일치 문자를 오른쪽에서 부터 찾음 -> 본문과 패턴의 불일.. 2025. 3. 18. 알고리즘 8 그래프_3 데이크스트라 알고리즘 ; 최단 경로 탐색 정점들과 정점의 연결 여부만 따짐 ; 프림 / 크루스칼 경로의 길이를 감안하여 연결 ; 데이크스트라 - 각 정점에, '시작점으로부터' 자신에게 이르는 경로의 길이를 저장할 변수를 준비 - 각 정점의 경로 길이 무한대로 초기화 / 시작 정점의 경로 길이 = 0 - (최단 경로에 새로 추가된 정점)의 인접 정점에 대해 경로 길이를 갱신 - 그래프 내 모든 정점이 최단 경로에 소속될 때가지 반복 Algorithm/Graph at main · Sukmin-LanternK/AlgorithmContribute to Sukmin-LanternK/Algorithm development by creating an account on GitHub.github.com 2025. 3. 10. 운영체제 7. 파일 시스템 파일 ; 보조기억장치에 저장된 관련 정보의 집합 -> 이름/실행정보/ 부가정보(속성/메타데이터) 파일 속성 - 유형/크기/보호/생성날짜/마지막접근날짜/마지막수정날짜/생성자/소유자/위치 - 유형 ; 운영체제가 인식하는 파일의 종류- 보호 ; 어떤 사용자가 해당 파일을 읽고 쓰고 실행할 수 있는지 - 위치 ; 보조기억장치 상의 현재 위치 파일 연산을 위한 시스템 호출 - 운영체제는 아래의 시스템 호출을 제공한다 - 파일 생성 > 파일 삭제 > 파일 열기 > 파일 닫기 > 파일 읽기 > 파일 쓰기 - 디렉터리 - 윈도우는 이를 폴더라고 부른다 경로 ; 절대 경로와 상대 경로 - 같은 디렉토리에는 같은 이름 파일이 존재 X / 다른 디렉토리에는 같은 이름 파일 존재 가능- 절대 경로 : 루트 디렉토리에서 자.. 2025. 3. 7. 운영체제 6 가상 메모리 연속 메모리 할당 ; 프로세스에 연속적인 메모리 공간을 할당하는 방식 스와핑 ; 현재 실행되지 않는 프로세스에 다른 프로세스를 적재하여 실행 -> 스왑 영역 ; 프로세스들이 쫓겨나는 보조기억장치 일부 영역 -> 스왑 아웃 ; 메모리에서 스왑영역으로 쫓겨나는 것 -> 스왑 인 ; 스왑 영역 프로세스가 다시 메모리로 옮겨 오는 것 메모리 할당 - 최초 적합 ; 빈 공간을 순서대로 검색하다고 적재 가능 공간 발견 시, 배치 - 최적 적합 ; 프로세스가 적재될 수 있는 가장 작은공간에 할당 - 최악 적합 ; 프로세스가 적재될 수 있는 가장 큰 공간에 할당 외부 단편화 ; 프로세들이 종료되기를 반복하면서 빈 공간들 발생 -> 큰 프로세스 적재가 어려운 작은 빈 공간 다수일 때 외부 단편화 해결 방.. 2025. 3. 6. 알고리즘 7 그래프_2 최소 신장 트리 (Minimum Spanning Tree)- 그래프에서, 루프를 형성하는 간선만 제거하면 트리가 됨 - 각 구성 요소가 서로 연결되어 있고, 간선에 가중치가 실려 있는 연결된 가중치 그래프 최소 신장 트리 만드는 알고리즘- 프림 알고리즘- 크루스칼 알고리즘 프림 알고리즘 - 그래프와 최소신장트리준비- 임의의 정점을 시작 정점으로 -> 최소신장트리의 뿌리 노드로 삽입- 정점의 간선 가중치를 조사 -> 가장 가중치가 작은 인접접점 -> 최소 신장트리에 삽입 - 사이클이 생성되지 않도록 이를 반복 - 모든접점 순회가 끝나면 종료 - 우선순위 큐를 통해서, 정점 추가 시 마다, 조사 대상을 추가할 수 있음 - Vertex를 조회하면서, Vertex 별 가장 웨이트가 낮은 간선 정보를 수집 .. 2025. 3. 4. 이전 1 2 3 4 ··· 31 다음 반응형