1. 문제 - 난이도 ★ 시공의 폭풍은 5대5 대결게임이다. 당신의 팀원들이 선택한 4명의 영웅번호와 당신이 선택하고자 하는 5명의 영웅번호가 주어질 때, 이미 팀원이 선택한 영웅이 아닌 영웅의 수를 구하라. 2. 입력 첫줄에 팀원이 선택한 4명의 영웅 번호가 주어진다. 두번째 줄에는 당신이 선택하고자 하는 5명의 영웅번호가 주어진다. 3. 출력 당신이 선택하고자 하는 영웅들 중에서 팀원이 선택하지 않은 영웅의 수를 출력한다. 4. 알고리즘 선택하고자하는 영웅리스트를 돌면서 팀원 리스트에 없으면 카운트를 1증가시킨다. 본인은 파이썬의 filter() 함수를 사용했다. x = list(map(int, input().split())) y = list(map(int, input().split())) n = l..

1. Run-Length Encoding 2. Huffman Coding 3. Lampel-Zicv-Welch Encoding 4. Arithmetic Coding

1. 접미어 배열 텍스트의 접미어들을 사전식으로 나열한 배열 파이썬에서는 리스트로 구현한다. 접미어 트리보다 메모리를 효율적으로 사용하지만 다소 느리다. 텍스트 인덱싱, 데이터 압축, bio-informatics등의 다양한 분야에서 사용한다. 예시) s = abab b, ab, bab,b abab => 접미어 사전순 정렬 : ab, abab, b, bab => 접비어 배열 : [3, 1, 4, 2] 2. 접미어 배열 복잡도 O(n)의 메모리 크기 O(nlogn) 시잔에 생성 텍스트 T에 패턴 P의 존재를 O(|P| + logn) 시간에 계산 3. 접미어 배열 장점 생성 방법이 접미어 트리에 간단하다. 적은 메모리로 구현 가능 2개의 선형 크기의 리스트로 구성 전형적으로 접미어 트리에 비해 1/4크기의 메..

1. 접미어 트리 하나의 문자열의 모든 접미어들을 포함하는 트라이(Trie)의 압축된 표현 문자열 연산에 필요한 알고리즘을 빠르게 구현할 수 있다. 응용 문자열 매칭(Exact string matching) 부분 문자열 매칭(Substring matching) 최장 공통 부분 문자열(Longest common substring of 2 strings) 예시) 문자열 S = {xabxac}에 대한 접미어 트리 길이가 6이므로 6개의 접미어가 존재 단말노드에는 접미어의 시작위치를 저장한다. 루트를 제외한 내부 노드는 최소 2개의 자식을 갖는다. 각 간선은 문자열 S의 부분문자열 라벨(label)이 부여된다. 한 노드에서 나가는 두개의 간선이 같은 문자열 라벨을 가질 수 없다. 루트에서 단말노드 i까지 경로에..

1. 트라이 정보 검색에 사용된 자료구조 문자열의 집합을 표현하는 트리 다음 5개의 문자를 하나의 트라이로 표현. 각 간선은 하나의 문자에 대응 같은 노드에 나오는 간선들은 같은 레벨을 갖지않는다. 각 문자열을 단말 노드에 대응하고 문자열의 개수만큼 단말 노드가 존재한다. 2. 접미어 트라이 문자열의 모든 접미어를 Trie로 표현 길이가 n인 문자열 A = a0 a1 a2 ... an-1 ai ai+1 ai+2 an-1인 n개의 접미어 접미어 트라이를 이용한 문자열 연산 부분 문자열 검사 두 접미어의 최장 공통 접두어 찾기 사전적 순서로 정렬된 k번째 접미어 찾기 부분 문자열 검사 'abac' 문자열 접미어 트라이가 있을 때, 어떤 문자열이 부분 문자열인지 검사하는 방법은 한 문자씩 루트에서 대응되는 간..

1. 문자열 처리 예제) 다음 중 x안에 y가 존재하는지 찾아보자. 2. 문자열 매칭(패턴 매칭) 텍스트 문자열(t)에서 패턴 문자열(p) 포함 여부를 찾는 것. 고지식한 패턴 검색 알고리즘 카프-라빈 알고리즘 KMP 알고리즘 보이어-무어 알고리즘 파이썬의 패턴 매칭 3. 고지식한 알고리즘(Brute Force) 텍스트 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작 # t : 텍스트 # p : 패턴 # N : 텍스트의 길이 # M : 패턴의 길이 def BruteForce(t, p): N = len(t); M = len(p) i = 0 # 텍스트 인덱스 j = 0 # 패턴 인덱스 while i < N and j < M: if t[i] != p[i]: # 다..

자주 수행되는 작업들 디렉토리 경로 따라가기 디렉토리 내에 존재하는 파일들 나열하기 특정 파일의 존재 유무 판별하기 해당 작업들은 시스템의 성능 저하의 원인이 된다. 이 작업들은 검색에 기반해서 수행되는 작업들이므로 어떻게 해결해야할까. 1. 해싱 특정 항목 검색 시, 탐색 키에 대한 산술적 연산으로 키가 있는 위치를 계산하여 바로 찾아가는 방법이다. O(1) 시간 복잡도 1. 직접 번지 테이블 직접 번지 테이블(배열)에 저장하는 경우 전체 키(key)들의 집합(U)이 작은 경우에 효율적이다. 키 k가 테이블(T)에서 위치 k에 저장 테이블(배열)의 크기 = 집합 U의 크기 그러나 전체 키 값들의 집합 U가 클 때, 현실적인 컴퓨터 메모리 공간에서 테이블 T를 생성하는 것은 불가능하다. 또한 실제 저장되..

1. 백트래킹 2. 그래프의 기본과 탐색 3. 그래프의 최소 비용 문제 1. 백트래킹 해를 찾는 도중 해가 아니면 되돌아가서 다시 해를 찾는다. 2. 그래프의 기본과 탐색 객체들 사이의 연결 관계 표현 정점(vertex)집합과 정점을 연결하는 간선(edge)집합으로 구성 1) 깊이 우선 탐색(DFS) 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 2) 너비 우선 탐색(BFS) 시작 정점에서 인접한 정점을 먼저 모두 차례로 방문 3. 그래프의 최소 비용 문제 프림 알고리즘 한 정점에 연결된 간선들 중 하나씩 선택하며 최소 신장 트리를 만드는 알고리즘 크루스칼 알고리즘 최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘 다익스트라 알고리즘..

3주차 스터디 계획 https://swexpertacademy.com/main/learn/course/subjectList.do?courseId=AVuPDYSqAAbw5UW6 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이번 주 공부할 내용은 문자열 탐색입니다! 파이썬은 타 언어에 비해서 문자열을 다루는데 굉장히 강력한 언어입니다. 그러면 이러한 파이썬의 특성을 이용해서 문자열 탐색을 공부해봅시다. 1. 문자열 탐색 1) 학습 목표 1. 해싱에 대한 기본 개념에 대해 이해한다. 2. 문자열에서 패턴을 탐색하는 주요한 알고리즘에 대해 이해한다. 3. 트라이, 접미어 트리, 접미어 배열에 대해 학습하고 문자열 ..

https://swexpertacademy.com/main/learn/course/lectureVideoPlayer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 최단 경로 간선의 가중치가 있는 directed graph가 있을 때, 두 정점 사이의 경로들 중 간선의 가중치가 합이 최소인 경로 단일 시작점 최단 경로 문제 출발점에서 다른 모든 정점들에 이르는 최단경로를 구하는 문제 다익스트라 알고리즘 : 음의 가중치 허용 안함. 밸만 포드 알고리즘 : 음의 가중치 허용, 음의 사이클은 허용 안함 모든 쌍 최단 경로 문제 모든 정점 쌍 간의 최단 경로를 구하는 문제 플로이드-워샬 알고리즘 : 동적계획..