IT 공부/자료구조&알고리즘21 알고리즘 14 백트래킹 백트래킹 여러개의 후보해 중에서 특정 조건을 만족시키는 모든 해를 찾는 알고리즘 ex_) 미로 탈출 알고리즘 - 갈림길->무조건 왼쪽 - 막다른 곳이 나오면 되돌아 나와서 오른쪽 시도 - 뿌리에서 해를 찾기 시작 - 현재 부분해에서 선택 가능한 다음 부분해 목록을 조회 - 부분해를 하나씩 하나씩 방문 - 해가 될 수 있는 조건이면 위를 다시 실행 - 아니면, 이전 부분해로 돌아나와서 다른 부분해를 실행 - 위의 단계를 반복 ex) 미로 탈출 찾기 - 재귀호출 기반 백트래킹 Algorithm/BackTracking at main · Sukmin-LanternK/AlgorithmContribute to Sukmin-LanternK/Algorithm development by creati.. 2025. 4. 1. 알고리즘 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 그래프_2 최소 신장 트리 (Minimum Spanning Tree)- 그래프에서, 루프를 형성하는 간선만 제거하면 트리가 됨 - 각 구성 요소가 서로 연결되어 있고, 간선에 가중치가 실려 있는 연결된 가중치 그래프 최소 신장 트리 만드는 알고리즘- 프림 알고리즘- 크루스칼 알고리즘 프림 알고리즘 - 그래프와 최소신장트리준비- 임의의 정점을 시작 정점으로 -> 최소신장트리의 뿌리 노드로 삽입- 정점의 간선 가중치를 조사 -> 가장 가중치가 작은 인접접점 -> 최소 신장트리에 삽입 - 사이클이 생성되지 않도록 이를 반복 - 모든접점 순회가 끝나면 종료 - 우선순위 큐를 통해서, 정점 추가 시 마다, 조사 대상을 추가할 수 있음 - Vertex를 조회하면서, Vertex 별 가장 웨이트가 낮은 간선 정보를 수집 .. 2025. 3. 4. 알고리즘 6 그래프_1 그래프란? 정점의 모음과 간선의 모음이 결합 G= G(V,E) 인접/이웃관계 Adjacent ; 간선으로 연결되 두 정점 경로 ; 길이 ; 정점과 정점 사이의 간선의 숫자 사이클 ; 정점을 두 번 이상 거치도록 되어 있을 경우 방향성 ; 간선에 방향성이 있는 경우와 없는 경우 연결성 ; 두 정점 사이에 간선이 있는 경우 정점의 집합 -> 배열 또는 리스트로 나타냄 간선의 집합 -> 행렬 또는 리스트로 나타냄 = 인접행렬 또는 인접리스트 인접행렬 vs 인접리스트 - 정점 간의 인접 인식 속도 ; 행렬 > 리스트- 필요한 메모리 양 ; 행렬 > 리스트 - 정점과 간선 삽입 속도 ; 행렬 그래프 순회 기법 - 깊이 우선 탐색 - 너비 우선 탐색 GitHub - Sukmin-LanternK/Algor.. 2025. 2. 24. 알고리즘 5 해시 테이블 해시테이블- 데이터의 해시값을 테이블 내 주소로 이용하는 탐색 알고리즘 예 ) 엄청 크기가 큰 배열 -> 주소 다수 / 특정 데이터를 조회하는 시나리오에서-> 통상적으로, 순차탐색 / 이진탐색 등 사용 -> 시간 오래 걸림조회하고자 하는 데이터를 해시함수를 통해 바로 테이블 내 주소값으로 그라운딩 ex) 123817을 조회하고자 할 때, 123817 해싱 -> 3819 얻음해시테이블 Table[3819] = 123817 해시함수 나눗셈법 ; 주소 = 입력값 % 테이블 크기 -> 테이블 안의 범위에 그라운딩 되는 걸 보장 자릿수접기 ; 숫자의 각 자릿수를 더해 해시값을 만드는 것 - 한계 : 나머지 값이 같은 경우, 충돌이 일어날 가능성 - 클러스터링 ; 일부 지역 주소들을 집중적으로 반환하여 한 곳.. 2025. 2. 22. 이전 1 2 3 다음 반응형