L.O.K

예제) 철수는 매일 점심마다 짜장면이나 짬뽕을 먹는다. 시험기간이 n일 남았을 때, 철수가 짜장, 짬뽕을 먹는 경우의 수를 구하라. ( 단, 짜장면은 2일, 4일, 6일... 같이 짝수날을 연속으로 먹어야 한다. 또한 짜장면을 먹고 짬뽕을 먹은 뒤 다시 짜장면을 먹을 수 없다. ) 조건이 까다롭다. 조건1) 짜장면은 2, 4, 6... 연속으로 먹을 수 있다. 조건2) 짜 → 짬 → 짜 순으로 먹을 수 없다. 경우의 수를 따질 때, 동적계획법으로 접근하면 효율적이다. 시험기간 n일을 작은 단위로 분류해야한다. 조건1)은 분류에 적합하다. 예를들어, 시험기간이 8일이 남았다고 해보자. 1) 짜장면을 8일 먹은 날 2) 짜장면을 6일 먹은 날 3) 짜장면을 4일 먹은 날 4) 짜장면을 2일 먹은 날 5) 짜..

예제 ) 시작도시와 목표도시가 주어질 때, 목표도시까지 가는 최단 경로를 구하시오 시작도시 : A 목표도시 : E 다익스트라 알고리즘을 사용한다. 각 노드마다 접근된 경로의 길이를 기록한다. 최단 경로이므로 최소길이만 기록한다. D노드와 C노드와 F노드는 다음과 같은 접근 경우를 가질 수 있다. 경우 중 최소를 제외한 나머지는 제거한다. 이런 방식으로 각 노드의 최단 경로 길이를 구한다. 최소만 남긴다. 마지막으로 목표노드의 최단 경로 길이를 구해보자. A에서 E까지 최단경로길이는 17km이다. 참고자료 2021년 7기 모집대비 SSAFY(삼성 청년 SW아카데미) SW적성진단 5일 완성 ㆍ객관식 이론 + 대표유형 + 유형 + 고난도 문항 수록ㆍ주관식 대표유형 + 유형 + 고난도 문항 수록ㆍ객관식 & 주관..

예제) 모든 도시를 오갈 수 있는 고속도로를 건설하려고 할 때, 총 고속도로 길이의 최소값을 구하라. 복잡하다. 써클(Circle)이 보이도록 만들어보자. 써클이란, 지점들이 서로 연결되어 순환하는 구조를 말한다. 최소길이의 고속도로를 만들려면 고속도로가 최소 개수여야 한다. n개의 지점이 있으면 n-1개의 길만 있으면 된다. 이를 최소신장트리(Spanning Tree)라고 한다. 최소신장트리를 만들려면 순환구조를 없애야 한다. 최대길이의 간선을 제거하여 총 길이가 최소 길이인 스패닝트리를 만드는 것이 목적이다. 1) D - F - E 써클 D와 F를 잇는 간선이 12km로 가장 길다. 고로 제거한다. 총 제거 길이 : 12 2) D - A - F - E 써클 D-F를 제거했더니 또 다른 써클이 생성되었..

예제) 주어진 문자열을 수정하여 하나의 문자로만 구성된 문자열을 만드려고 할 때, 최소로 수행되는 수정 횟수를 구하시오. ( 연속적인 문자는 하나의 문자로 통일 가능하다. ) AABACCBABA 위 문자열을 AAAAAAAAAA 나 BBBBBBBBBB나 CCCCCCCCCC로 바꾸라는 말이다. 수정횟수를 최소로 하려면 가장 자주 등장하는 문자를 제외한 나머지 문자를 수정해야한다. ( Greedy 알고리즘 ) 알고리즘 1) 포인터로 문자열을 검사해서 문자별 등장횟수를 카운트한다. 2) 동일한 문자가 연속되면 카운트하지 않는다. 3) 등장 횟수가 많은 문자를 제외한 두 문자의 등장횟수 합이 최소 수정횟수이다. A가 등장했다. 현재 문자는 A로 입력되고 A 등장횟수는 1 올라간다. A가 연속해서 등장했다. 현재문..

예제) 아래 이름 나열을 '가나다' 오름차순으로 나열하려고 할 때, 이름을 최소 몇 번 이동하면 구현이 가능할까? 위 이름 나열을 가나다 오름차순으로 나열하면 다음과 같다. 최소 횟수로 구현하려면 얼마나 공통된 순서로 배치되었는지를 확인하면 된다. 예를들어, 위치는 다르지만 류다영 → 신서리 → 이다영 → 홍원주 순은 두 배열 모두 동일하다. 그러므로 공통된 순서에 있지 않은 이름을 이동시키면된다. [동적계획법] 최장공통문자열 ( Longest Common SubSequence ) 동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우 lordofkang..

예제 ) 두 문자열의 최장 공통 문자열의 길이를 찾으시오 ASEFSDCA 와 SESDASEF Common SubString은 연속적으로 공통된 부분 문자열을 의미한다. ASEFSDCA 와 SESDASEF 인간은 직관으로 공통된 문자열을 찾을 수 있지만 최장 공통 문자열을 찾기란 쉽지않다 또한 컴퓨터는 직관을 갖고 있지 않다. 그러므로 포인터를 사용하여 두 문자열의 문자를 하나씩 비교해야 한다. 두 문자열을 비교하려면 두 개의 포인터가 필요하다. 두 개의 포인터를 움직이며 두 문자열의 문자를 하나씩 비교해본다. 포인터가 비교하는 모든 경우를 살펴보려면 이차원 테이블이 필요하다. 이차원 테이블에서 '대각선'은 의미가 크다. 포인터A와 포인터B가 동시에 한 칸씩 이동하면 대각선으로 한 칸 이동한다. 포인터A로..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. 최장 공통 문자열 ( Longest Common SubSequence; LCS ) 예제) 주어진 두 문자열의 최장 공통 문자열을 구하라. [ abdcg , bdag ] SubString과 SubSequence 의 차이는 연속적이냐 비연속적이냐의 차이다. 두 문자열의 bd는 SubString이다. 두 문자열의 b , g는 SubSequence이다. 비연속적이지만 순서가 맞다. 한 마디로 LCS는 얼마나 두 문자열이 공통된 순서대로 배치되었는가를 확인하..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. Longest Palindrome SubString 예제) 문자 수열이 주어질 때, 대칭을 이루는 부분수열 중 최대길이를 구하라. [ b, a, a, b, c ] Palindrome이란, 정방향으로 읽어도 역방향으로 읽어도 같은 배열을 의미한다. b, a, a, b 는 → 으로 읽어도 ← 으로 읽어도 같다. 이런 성질을 가진 부분수열 중 최대길이를 구해야 한다. Palindrome은 몇가지 특징을 가진다. 1) Prlindrome 성질을 가진 가장 ..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. Maximum Product SubArray 예제) 정수로 구성된 한 수열이 주어질 때, 곱이 최대가 되는 부분수열을 구하라. [ 3, -2, 1, 0, -8, 9 ] 동적계획법을 발상하기 어려운 문제다. 부분수열로 분할할 수 있는 경우의 수가 너무 많다. Top에서 Down하면서 분할하기가 쉽지 않다. 그래서 일반적으로는 브루트포스 방법을 생각하게 된다. [ 3 ], [ 3, -2 ] [ 3, -2, 1] [ 3, -2, 1, 0 ] [ 3, -2..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. Maximum Sum SubArray 예제) 정수로 구성된 한 수열이 주어질 때, 합이 최대가 되는 부분수열을 구하라. [ 5, -2, 9, -15, 8 ] 동적계획법을 발상하기 어려운 문제다. 부분수열로 분할 할 수 있는 경우의 수가 너무 많다. Top에서 Down하면서 분할하기가 쉽지 않다. 그래서 일반적으로는 브루트 포스 방법을 생각하게 된다. [ 5 ] , [ 5 ,-2 ] , [ 5, -2, 9 ] , [ 5, -2, 9, -15 ] , [..