L.O.K

예제) 어떤 퀴즈대회에서 숫자게임이 진행되었다. 숫자게임의 규칙은 주어진 범위 안의 숫자들을 더해 목표하는 수를 만드는 것이다. 중복된 숫자를 사용하는 것은 가능하지만 숫자들의 조합은 두 사람 이상 똑같이 사용할 수 없다. 사용 가능한 숫자 범위와 목표하는 수가 주어졌을 때, 목표하는 수를 만들 수 있는 최대 경우의 수를 구하시오. 숫자 범위 [ 1 , 2 , 3 ] 목표 : 8 ( 답지에 답은 10이라 나온다. 근데 문제 조건이 너무 헷갈리고 'SSAFY 5일완성' 책이 오류가 상당히 많다. 조건이 애매하니 어떻게 해석하느냐에 따라 결과가 달라진다고 생각한다. 그래서 그냥 내가 해석한 방식대로 풀었고 답은 31은 나왔다. ) 1, 2, 3을 더해 8을 만드는 경우의 수를 구하는 문제이다. 동적계획법의 ..

예제) 남자 m명과 여자 n명이 있다. 남자는 여자보다 많고 커플은 여자의 수만큼 생성된다. 여자는 키가 큰 순서로 선택할 수 있다. 남자는 키 순서대로 서있다. 한 여자가 한 남자를 선택했을 때, 다음 여자는 선택된 남자보다 키 큰 남자를 선택할 수 없다. 남성의 키가 모두 다를 때, 커플이 탄생할 수 있는 경우의 수를 구하라. ( 개인적으로 이게 뭔 문제인지 감도 잘 안 잡혔다. 동적계획법에 억지로 문제를 끼어맞추다보니 이상한 문제가 탄생한거 같다. 그래도 한 번 풀어보자. ) 결국 커플은 n개 탄생한다. 동적계획법을 발상하려면 두 가지를 고려하면 된다. 1) 큰 단위와 작은 단위에 공통으로 적용되는 원리를 발견한다. 2) 큰 단위와 작은 단위를 분리한다. 첫 번째 여자는 3명의 남자를 선택할 수 있..

예제 ) 하노이탑 원반의 개수가 주어질 때 원반을 이동시킬 최소 횟수를 구하시오. 규칙 1. 1회에 한 개의 원판만 옮길 수 있다. 2. 반드시 큰 원판 위에 작은 원판이 있어야 한다. . 1번에 쌓여있는 원판들을 규칙을 지키며 3번까지 옮겨야 한다. 동적계획법의 TopDown 방식에 따라 결과부터 생각해보자. n개의 원판을 3번 막대로 옮기려면 우선, n-1개 원판을 2번 막대로 옮겨야 한다. 그래야 가장 큰 원판을 3번으로 옮길 수 있다. 그 다음, 2번 막대의 n-1개 원판을 다시 3번 막대로 옮긴다. 공식으로 나타내보자. n : 원판 갯수 F(n) : n개의 원판을 한 막대에서 다른 막대로 옮기는 경우의 최소 횟수 과정 1) n-1개 원판을 1번에서 3번으로 이동 : F(n-1) 2) 가장 큰 원..

예제) 철수는 매일 점심마다 짜장면이나 짬뽕을 먹는다. 시험기간이 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는 얼마나 두 문자열이 공통된 순서대로 배치되었는가를 확인하..