# Foundation/알고리즘 (11) # Foundation/알고리즘 [코딩테스트 대비] 트라이(Trie) 자료구조 개요 접근법 Trie라는 용어 자체는 생소할 수 있지만, 알게 모르게 실생활에서도 사용한 적이 있을만큼 매우 간단한 개념입니다. 예를 들어, 영어사전에서 apple 이라는 단어를 찾고 싶다면, 앞에서부터 a - p - p - l - e 순서로 prefix를 조합하면서 찾아갈 수 있습니다. // 영어사전에서 apple를 찾고 싶다면... 앞에서 a를 찾는다. -> a 이어지는 p를 찾는다. -> ap 이어지는 p를 찾는다. -> app 이어지는 l를 찾는다. -> appl 이어지는 e를 찾는다. -> apple 위와 비슷하게 xx시 xx고등학교 xx학년 xx반에 소속된 학생정보를 찾고 싶다면, 앞에서부터 prefix를 조합하면서 차례대로 접근하면 됩니다. step 1) xx시 step 2) xx시 xx고등.. 2020. 9. 16. 19:37 # Foundation/알고리즘 [코딩테스트 대비] 순열(Permutation)과 조합(Combination) 알고리즘 개요 순열Permutation과 조합Combination은 코딩테스트에서 매우 빈번하게 사용되는 도구 중 하나입니다. 어떤 배열의 순열 또는 조합을 구하라!라는 직접적인 문제는 출제되지 않지만, 이것을 사용해야 문제가 풀리는 경우가 많으므로 순열과 조합 알고리즘 구현에 대해 정리하고자 합니다. 해당 포스팅에서는 TypeScript를 사용하여 구현했지만, 다른 언어에서도 충분히 구현할 수 있을만큼 상세하게 설명하겠습니다. 순열 (Permutation) 정의 길이가 $n$인 배열에서 $r$개의 요소를 차례대로 뽑아 새로운 배열을 만들었을 때, 가능한 모든 배열의 합입니다. 예를 들어 [1, 2, 3, 4]라는 배열에서 3개의 요소를 뽑아 새로운 배열을 만든다고 한다면, 아래와 같이 24개의 배열이 도출됩니다.. 2020. 9. 15. 20:37 # Foundation/알고리즘 C++ Permutation 함수 해당 포스트 대신, 아래의 포스트를 사용해주세요. [코딩테스트 대비] 순열 및 조합 알고리즘 개요 순열 Permutation과 조합 Combination은 코딩테스트에서 매우 빈번하게 사용되는 도구 중 하나입니다. 어떤 배열의 순열 또는 조합을 구하라! 라는 직접적인 문제는 출제되지 않지만, 이것을 사용 aerocode.net C++ Permutation Overview 어떤 집합에서 r개를 선택하여 얻을 수 있는, 모든 순열(Permutation)을 가져온다. 예를 들어, 벡터 집합 = {"a", "b", "c"} 에서 2개를 선택하여 얻을 수 있는 순열은 다음과 같다. b c c b a c c a a b b a 비트셋 집합은 순서를 표현할 수 없으므로 논외이다. Function Usage int ma.. 2019. 10. 20. 16:54 # Foundation/알고리즘 C++ Combination 함수 해당 포스트 대신, 아래의 포스트를 사용해주세요. [코딩테스트 대비] 순열 및 조합 알고리즘 개요 순열 Permutation과 조합 Combination은 코딩테스트에서 매우 빈번하게 사용되는 도구 중 하나입니다. 어떤 배열의 순열 또는 조합을 구하라! 라는 직접적인 문제는 출제되지 않지만, 이것을 사용 aerocode.net C++ Combination Overview 어떤 집합에서 r개를 선택하여 얻을 수 있는, 모든 조합(Combination)을 가져온다. 예를 들어, 벡터 집합 = {"a", "b", "d"} 에서 2개를 선택하여 얻을 수 있는 조합은 다음과 같다. b d a d a b 다른 예로, 비트셋 집합 = 0b1101 에서 2개를 선택하여 얻을 수 있는 조합은 다음과 같다. 1100 10.. 2019. 10. 20. 16:19 # Foundation/알고리즘 비트셋으로 집합 표현하기 (Bitset) 비트셋이란? 비트셋이란, 말 그대로 Set of Bits를 의미한다. 즉, 여러개의 비트가 모여서 하나의 집합을 형성하는 것 이다. 아래는 8비트를 나타내는 비트셋의 예시이며, 비트셋의 인덱스는 오른쪽에서 왼쪽으로 증가함에 유의하자. 문제 제기 과일을 도메인으로 갖는 공간을 생각해보자. 아래의 집합은 서로 같은가? 다른가? vector A = {사과, 포도, 딸기} vector B = {사과, 딸기, 포도} 포도와 딸기의 위치가 바뀌긴 했지만, 그 집합의 구성원은 일치하므로 같은 집합이다. 하지만 벡터로 표현된 두 집합이 동치인지 확인하는 작업은 복잡하며, 벡터의 크기가 커질수록 느려진다. 비트셋을 이용한 집합표현 (1) 비트셋은 정규화된 집합을 표현하는데 매우 효과적이다. 각 과일마다 비트의 인덱스를 .. 2019. 10. 20. 13:31 # Foundation/알고리즘 그래프 이론 (1) 그래프란?정점(Vertex)과, 두 정점을 잇는 간선(Edge)의 집합.간선에 의해 이어진 두 정점은 서로 인접(Adjacent)하다고 한다. [그림 01] 일반적인 그래프 그래프의 방향성간선에 화살표 표시가 있다면, 해당 방향으로만 움직일 수 있다. 그래프의 방향성간선에 화살표 없음 : 무향 그래프, 양방통행.간선에 화살표 있음 : 유향 그래프, 일방통행. [그림 02] 무방향성 그래프 [그림 03] 방향성 그래프 위의 방향성 그래프에서는 3에서 5로 갈 수 없다.간선에 방향성이 부여되었기 때문. 정점의 차수무향 그래프에서 정점에 연결된 간선의 수를 차수(Degree)라고 한다. 유향 그래프에서는 더욱 세부적으로 구분한다.입력 차수 (in-degree) : 해당 정점으로 들어오는 간선의 수.출력 차수 .. 2019. 7. 23. 18:35 # Foundation/알고리즘 가장 긴 공통 부분 수열 (LCS - Longest Common Subsequence) 알고리즘 LCS의 정의가장 긴 공통 부분 문자열 (Longest Common Substring)두 문자열의 가장 긴 부분 문자열이다.문자열이란 끊어지지 않는 문자들의 연속이다. 가장 긴 공통 부분 수열 (Longest Common Sequence)두 문자열의 가장 긴 부분 수열이다.부분 수열이란 원래 수열에서 임의의 원소를 0개 이상 지워서 만든 수열이다. 이 포스팅에서는 가장 긴 공통 부분 수열을 다루며, 다루어지는 주제는 다음과 같다.N^2 풀이경로 추적N*logN 풀이 - Using LIS문자열이 N개일 때메모리 최적화 N^2 풀이동적 계획법을 사용하여 문제를 풀어보자.작은 문제부터 시작하여 큰 문제를 해결하는 것 이다! int solve (int i, int j) // A[0...i]와 B[0...j]에서.. 2019. 7. 2. 15:07 # Foundation/알고리즘 가장 긴 공통 부분 문자열 (LCS - Longest Common Substring) 알고리즘 LCS의 정의가장 긴 공통 부분 문자열 (Longest Common Substring)두 문자열의 가장 긴 부분 문자열이다.문자열이란 끊어지지 않는 문자들의 연속이다. 가장 긴 공통 부분 수열 (Longest Common Sequence)두 문자열의 가장 긴 부분 수열이다.부분 수열이란 원래 수열에서 임의의 원소를 0개 이상 지워서 만든 수열이다. 이 포스팅에서는 가장 긴 공통 부분 문자열을 다루며, 다루어지는 주제는 다음과 같다.N^2 풀이경로 추적 N^2 풀이동적 계획법을 사용하여 문제를 풀어보자.작은 문제부터 시작하여 큰 문제를 해결하는 것 이다! int solve(int i, int j) // A[0...i]와 B[0...j]에서, A[i]와 B[j]를 공통된 끝으로 갖는 최대 부분 문자열의 길이.. 2019. 7. 1. 12:32 이전 1 2 다음
