hs-archive

최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) 최장 증가 부분 수열 문제는 주어진 수열은 가장 긴 증가하는 부분 수열을 구하는 문제입니다. 예를 들어 수열 [4, 2, 1, 3, 5, 8, 6, 7] 이 주어졌을 때의 LIS는 [2, 3, 5, 6, 7] 입니다. 아래 사진을 참고해 주세요. 실제 LIS 문제인 백준 가장 긴 증가하는 부분 수열 문제를 풀어봅시다. 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50} 이고 길이는 4입니다. 입력 첫째 줄에 수열 A..

회문이란 왼쪽부터 읽는 것과 오른쪽부터 읽는 것이 같은 문자를 뜻한다. ex) 기러기, 토마토, aba, abba, aa, a 등등... 가장 긴 부분 회문이란 "babad"에서 "bab"와 "aba"이고 "cbbd"에서 "bb"이다. 회문의 특성을 생각해보면 회문 안에 회문이 있다는 것을 찾을 수 있다. 이를테면, "cabbac"는 "abba"를 포함하고 있고 "abba"는 "bb"를 포함하고 있으며 "bb"는 "b"를 포함하고 있다. 이를 보면 다음과 같은 생각을 가질 수 있다. 1. 양쪽 끝에 있는 문자들이 서로 같고 2. 양쪽 끝에 있는 문자를 제외한 글자가 회문이면 3. 해당 글자는 회문이다. (ex. "abba"일 때 1. 양쪽 끝에 있는 문자들이("abba") 서로 같고 2. 양쪽 끝에 있는..

우리는 알고리즘의 속도를 예측할 수 있어야 합니다. 그래야 무엇이 더 빠른 알고리즘인지 감별할 수 있기 때문입니다. 만약, 제가 만든 알고리즘의 시간 복잡도가 n^2/2 * e + 1.345n + 32이라면 n이 증가함에 따라 시간 복잡도가 어떻게 증가할지를 한눈에 파악하는 것은 매우 어렵습니다. 게다가 100000000n + 12345의 시간 복잡도를 갖는 또 다른 알고리즘과 속도 비교를 하기란 더더욱 어렵습니다. 그러나 위 두 식이 n^2과 n처럼 단순화된 형태라면 각각의 증가량과 두 식 간의 차이를 단숨에 파악할 수 있을 것입니다. 이를 가능하게 해주는 것이 바로 점근 표기법입니다. 우리는 점근 표기법을 사용하여 식을 단순화할 수 있습니다. 점근 표기법은 최고차 항의 차수만 남기고 다른 모든 항과 ..

해시 해시는 값이 저장될 위치(index)를 간단한 연산으로 구하는 것이다. 해시 함수를 사용하여 키를 해시값으로 매핑하고 이 해시값을 인덱스 삼아 데이터의 값을 키와 함께 저장하는 것이다. 이때 데이터가 저장되는 곳을 버킷 혹은 슬롯이라 한다. 해시 테이블의 크기는 보통 소수로 설정하는데 이는 해시 함수 내부 과정이 해싱을 한 뒤 그 값을 해시 테이블의 크기로 나눈 나머지를 리턴하기 때문이다. 해시 테이블의 크기가 소수가 아니라면 나머지 값이 한 곳으로 치우지기 쉽다. 이를 방지하기 위해 테이블의 크기는 소수로 한다. 그냥 리스트 쓰면 되지 해시 함수를 통해서 숫자를 만들고 그것을 key로 사용하는 해시라는 개념을 왜 굳이 만들었을까? 만약 List에 위 정보를 저장했다고 가정해보자. a_list = ..

수많은 마라톤 선수들이 마라톤에 참여했습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주했습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. list를 사용해 풀 수도 있겠지만 list의 경우 검색의 시간 복잡도가 O(n)인데 반해 dict는 O(1)이다. 따라서 list보다 dictionary를 사용하여 문제를 푸는 것이 더 짧다는 생각을 갖고 문제를 풀어보자. dictionary를 사용하여 푸는 방법은 다음과 같다. for문으로 participant을 하나 씩 방문한다. hash() 함수를 사용해 참가자 이름을..

ArrayList 내부적으로 데이터를 배열에서 관리하며, 요소 삽입 시 배열의 크기를 넘어설 경우 새 배열을 만들고 기존 배열의 데이터를 모두 새 배열로 복사하기 때문에 O(n)이 걸린다. 따라서 많은 양의 자료를 추가/삭제하는 경우 데이터 복사가 빈번히 일어나므로 성능 저하를 일으킨다. 데이터를 배열로 관리하므로 인덱스를 통한 검색의 경우 O(1)이 걸린다. LinkedList 한 개의 노드에 내가 갖고 있는 데이터와 다른 노드에 대한 정보를 갖고 있다. 단방향 링크드리스트의 경우 다음 노드에 대한 정보만 갖고 있고 양방향의 경우 이전 노드에 대한 정보도 갖고 있다. LinkedList는 시작 요소나 가운데 요소를 삭제/삽입할 때 O(n) 시간이 걸리는 ArrayList와는 달리 다음 노드, 이전 노드..

while progresses:로 묶고 for 문을 돌려 progress[i] += speed[i]를 해준 뒤 progresses[0]이 100 이상이라면 progresses[0]을 포함해 그 뒤에 것들까지 요소의 값이 100 이상인 것을 찾고 해당 요소를 pop()하는 식으로 문제를 풀었다. def solution(progresses, speeds): answer = [] while progresses: for i in range(len(progresses)): progresses[i] += speeds[i] if progresses[0] > 99: res = 0 while progresses and progresses[0] > 99: res += 1 progresses.pop(0) speeds.pop..

숫자를 오직 1, 2, 4로만 표현하는 나라가 있다 10진수 n이 주어졌을 때 n을 124 나라의 숫자로 변환한 결과를 리턴하시오. 124 나라의 숫자는 모든 숫자를 세 개로만 [1, 2, 4] 표현한다는 점이 삼진법[0, 1, 2]과 같다. 하지만, 0보다 큰 자연수 n을 각자의 표현 방식으로 나타낼 때 삼진법의 맨 앞자리에는 0이 올 수 없지만 124 나라의 수는 맨 앞자리에 1이 올 수 있다. ex) 길이가 2인 124 나라의 수 중 가장 작은 수는 [1, 2, 4]의 1을 활용한 11이지만, 삼진수 중 가장 작은 수는 [0, 1, 2]의 0을 활용한 00이 아니라 10이다. 십진수 삼진수 124나라의 수 1 1 1 2 2 2 3 10 4 4 11 11 5 12 12 6 20 14 7 21 21 8..

격자 칸 1cm x 1cm로 이루어진 사각형이 주어져있고 해당 사각형의 대각선 꼭짓점 2개를 잇는 선이 그어질 때 선이 지나지 않는 1cm x 1cm 격자 칸의 개수를 구하는 문제이다. 8x12 직사각형에서 대각선이 지나는 격자의 개수를 반으로 나눠서 생각하면 (4x8 직사각형에서 대각선이 지나는 격자의 개수) x 2와 같고 이것을 또 반으로 나눠서 생각하면 (2x3 직사각형에서 대각선이 지나는 격자의 개수) x 4와 같다. 2와 3을 공통으로 나누는 2 이상의 자연수는 없으므로 2와 3은 서로소이고 8과 12를 서로소로 만든 수 4는 8과 12의 최대 공약수이다. 더보기 * a와 b를 c로 나누었을 때의 결과가 서로소라면 c는 a와 b의 최대 공약수임 따라서 전체 사각형에서 두 꼭짓점을 잇는 대각선이 ..

DFS, BFS에 대해 알아보자 얻어갈 지식 DFS, BFS DFS( Depth-First Search : 깊이 우선 탐색) 깊이 우선 탐색은 그래프에서 한 루트로 더 이상 내려갈 곳이 없을 때까지 검색한 뒤 옆으로 이동하여 다른 루트를 검색하는 방식이다. 보통 한없이 깊이 검색하는 것을 방지하기 위해 깊이 제한을 사용한다. 깊이 제한에 도달할 때까지 목표 노드가 발견되지 않으면 가장 최근 노드의 부모 노드로 되돌아와서, 이전과는 다른 노드를 선택한다. 여기서 부모 노드로 되돌아오는 과정을 백트리킹이라 한다. 장점 단지 현 경로상의 노드만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라..