전공 수업 CS/algorithms

[알고리즘] 순환(Recursion)의 개념과 기본 예제 1, 2, 3

Recursion : 자기 자신을 호출하는 함수(재귀함수) java식) 자기 자신을 호출하는 method > void func(...) { ... func(...); ... } what will happen? public class Code01 { public static void main(String [] args) { func(); } public static void func() { System.out.println("Hello"); func(); #자기자신을 다시 호출 } } 무한루프에 빠짐 그럼 Recursion은 항상 무한루프에 빠질까? public class Code02 { public static void main(String [] args){ int n =4; func(n); } publ..

[알고리즘] 개념을 재정리 하기 위한 알고리즘 커리큘럼 로드맵

지난학기 알고리즘을 수강했었는데 어려움을 많이 느낀 과목이었다. 이번 방학에는 알고리즘 커리큘럼을 새우고, 탄탄한 알고리즘 실력을 기르려고 한다. 내가 지향하는 바는 SOLID BASIC 이니까! 백준 문제 커리큘럼 입출력 방식에서 시작해서, 기초 자료구조, 기초 수학, DP, 정렬, 그래프, 이분탐색, 분할정복, 그리디, 완전탐색으로 끝이 남 입출력 - 2557, 1000, 2558, 10950, 10951, 10952, 10953, 11021, 11022, 11718, 11719, 11720, 11721, 2741, 2742, 2739, 1924, 8393, 10818, 2438, 2439, 2440, 2441, 2442, 2445, 2522, 2446, 10991, 10992 DP - 1463, 1..

[알고리즘] 스트링 처리 알고리즘 | kmp 알고리즘, 보이어 무어 알고리즘, 패턴 매칭 알고리즘, 라빈 카프 알고리즘

시험 공부하다가 다시 정리한다. String탐색 알고리즘 Text에서 원하는 string, pattern을 찾는 알고리즘 1. Brute Force 그냥 모든 경우의 수를 전부 비교해 보는 방법이다. 1) Code void BruteForce(string text, string pattern){ int i, j; for(i=0, j=0; i= 0) && (text[i] != pattern[j])) j = next[j]; } if (j == pattern.length()) return i - pattern.length(); else return i; } 사실 위에서 next배열의 정의와 InitNext()함수를 잘 이해했다면, KMP의 동작 과정을 표현하는데에는 문제가 없을 것이다. 즉, text[i] !..

[알고리즘] 동적계획법 | 스트링 편집 거리(String edit distance)

스트링 편집 거리(String edit distance)는 두 스트링의 유사도를 측정하기 위해 사용되는 알고리즘을 말한다. 이 알고리즘을 제안한 수학자의 이름을 따서 레벤슈타인 거리 라고도 불린다. (LD) 원래 스트링: S 목표 스트링: T 라고 할때, 원래 스트링을 목표 스트링으로 변환하는데 필요한 삽입, 삭제, 대치 연산의 최소 비용을 편집 거리하고 한다. 삽입: 원래 스트링에 새로운 문자를 삽입하는 연산 삭제: 특정 위치에 있는 문자를 삭제 대치 : 특정 위치의 문자를 다른 문자로 바꾸는 연산 세 종류의 연산마다 비용이 정해져 있다. 예를 들어보자! S: "test"이고 T: "tent"라면, "s" 을 "n"으로 변경하는 하나의 대치 연산을 함으로써 S를 T로 변환할 수 있으므로 LD(S, T)..

[알고리즘] 동적계획법 | 최적 이진 탐색 트리

이진 탐색 트리는 루트의 왼쪽 서브트리에 있는 원소의 키 값은 루트보다 작고, 오른쪽 서브트리에 있는 원소의 값은 루트보다 큰 값을 가진다. 또, leaf 노드들 간의 depth 차이가 1보다 클 수 없다. 여기서 '최적'이란 단어까지 붙으면 최적 이진 검색트리가 된다. 최적 이진 검색 트리는 가능한 이진 검색 트리 중 key를 찾는데에 걸리는 평균 시간이 가장 짧은 이진 검색 트리를 의미한다. 즉, 트리 내의 키와 각 키가 탐색될 확률이 주어져 있을 때 그 트리의 평균 탐색 비용(평균 비교 횟수)를 계산하고 이를 최소화하는 탐색 트리를 구축하는 문제이다. 여기서 탐색 비용은 원하는 키를 찾기까지 필요한 비교 횟수를 뜻한다. 평균 탐색시간은 한 노드에 담긴 keym이 찾고자하는 search key일 확률..

[알고리즘] 동적 계획법 | 연쇄 행렬 곱셈

동적 계획법을 복습할겸 연쇄 행렬 곱셈에 대해 다시 한 번 정리하고자 한다. 연쇄 행렬 곱셈 문제가 뭔데? 주어진 n 개의 연쇄 행렬을 곱하는 최적의 순서를 구하시오. n 개의 연쇄 행렬 곱셈: A1 * A2 * ...* An [행렬 곱셈은 결합 법칙이 성립한다!] 예를 들어, (Ax * Ay) * Az = Ax * (Ay * Az) 이렇게 곱셈 순서를 바꾸어도 계산 결과가 같다는 뜻이다. 그러나 중요한 점은 행렬 곱셈의 순서에 따라 각 원소의 곱셈 횟수가 달라진다는 것이다. 그렇다면 최적의 순서는 곱셈의 횟수가 가장 작아지도록 하는게 최적일 것이다. 즉 이 문제는 최적화 문제라는 뜻이다. -> 원소의 곱셈 횟수를 최적화하는 문제를 찾아보도록하자. 연쇄 행렬 곱셈 문제를 이해해보자! 2 * 3 행렬과 3..

[알고리즘] 동적 계획법 | 행렬의 연쇄적 곱셈 | 연쇄 행렬 최소곱셈 알고리즘

연쇄행렬 최소곱셈 알고리즘 두 개 이상의 행렬을 곱할 때, 최소 곱셈 횟수를 구하는 문제이다. -> 행렬의 곱셈은 아래와 같이 결합법칩이 성립한다. A*(B*C) = (A*B)*C 그러나, 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라진다. 예를들어 설명하면, 행렬 A,B,C,D 4개가 존재한다. 각각 행렬의 차수는 20x1, 1x30, 30x10, 10x10이라고 한다. 4개의 행렬은 여러가지 방법으로 곱할 수 있지만, 다음 4개의 경우에 대하여 생각해볼때, 곱셈 횟수를 비교하면 아래와 같다. ((A*B)*C)*D) = (20*1*30) + (20*30*10) + (20*10*10) = 8,600 A*(B*(C*D)) = (30*10*10) + (1*30*10) + (20*1*10) = 3,500 (A..

[알고리즘] 욕심쟁이 알고리즘 | 그리디 알고리즘(Greedy Algorithm)동적 계획법을 공부하다가 궁금해진 알고리즘

그리디 알고리즘을 한 마디로 정의해 보자면, 눈 앞에 보이는 최적의 상황만을 보는 알고리즘이라고 할 수 있다. 이 알고리즘은 항상 최적해를 도출하는 것은 아니다. 그러나 어느정도는 최적해에 근사한 값을 빠른 속도로 구할 수 있다는 장점을 가진다. 또한 특정한 상황에서 최적해를 보장할 수 있다는 장점이 있다. 그리디 알고리즘의 대표적인 예제는 거스름돈 문제이다. 예를 들어 730원을 거슬러주어야할때 10원짜리 동전을 73개 거슬러 주기 보다, 500원짜리 1개와 30원짜리 3개를 주는 것이 편하다. 따라서 이 경우 '무조건 더 큰 화폐 단위부터 거슬러 준다'는 알고리즘만 지킨다면 최적의 해를 보장할 수 있다. 그리디 알고리즘은 극단적으로 문제를 접근한다는 점에서 ( 무조건적으로 큰 경우대로, 작은 경우대로..

[알고리즘] 동적 계획법 | 다이나믹 프로그래밍 ( Dynamic Programing)

동적 계획법은 주어진 문제를 여러 개의 부분 문제로 분할하여 각 부분문제의 해결안을 바탕으로 주어진 문제를 해결하는 기법이다. 이 때 각 부분 문제는 다시 여러개의 부분 문제로 분할될 수 있다. 각 부분문제는 원래 주어진 문제와 동일한 문제이지만 입력 크기가 작다. 따라서 부분 문제를 반복해서 분할하면 궁극적으로 입력의 크기가 매우 작은 단순한 문제가 되기에 쉽게 문제를 해결할 수 있게된다. 반복해서 여러 번 호출되는 부분 문제가 있을 경우 해당되는 부분 문제가 첫 번째 수행될 때 그 결과를 기록해 두었다가 이후에 다시 수행이 요구될 때 또 수행하지 않고 기록해둔 결과를 이용하는 것이 동적 계획법의 핵심이다. 즉, 한 마디로 동적 계획법을 표현하자면 '하나의 문제는 단 한 번만 풀도록 하는 알고리즘'이다..

[알고리즘] 스트링 처리 알고리즘 | 허프만 코드, 허프만 알고리즘

압축이란 파일의 크기를 줄이는 방법을 의미한다. 즉, 시간 보다는 공간을 절약하는 방법에 대해 연구한다. 대부분의 컴퓨터 화일에서는 데이터가 중복되어 있다고 착안하고 있다. 압축을 하게되면 한정된 컴퓨터자원을 효율적으로 사용할 수 있다. 1) 런-길이 인코딩 화일에서 기본적인 중복은 같은 문자가 연속적으로 나타나는 것이다. 하나 예시를 들어보자면, AAAABBCCCCC = 4A2B5C 와 같이 표현할 수 있다. 위와 같이 동일한 문자가 여러개 나올 경우 숫자와 문자 쌍으로 화일을 압축하는 기법을 '런-길이 인코딩'이라고 한다. 그러나 실제 문서에서는 같은 문자가 여러번 연속해서 나오는 경우가 많지 않기에 런-길이 인코딩은 주로 이진수로 표현되는 비트맵 이미지를 압축하는데 사용된다. 예를들어 이진수 000..