CS (54) 썸네일형 리스트형 [알고리즘] 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence) 가장 긴 증가하는 부분 수열이란3 9 2 10 2 11 19라는 수열이 있을 때 부분 수열은 3 9 2, 10 2 19, 9 2 10 등 많은 수열이 있지만 그 중에서도 3 9 10 11 19를 뽑으면 오름차순을 유지하면서 가장 긴 부분 수열을 뽑을 수 있다. LIS알고리즘이란 이 수열의 길이를 빠르게 찾아내는 방법을 말한다.그렇다면 이 수열을 어떻게 구할 수 있을까?1. 브루트포스 완전탐색모든 수열을 다 구해보면 된다. 그렇다면 1 2 3 4 라는 수열이 있다면 각 자리의 수를 사용하거나 혹은 사용하지 않는 경우의 수를 샐 수 있으므로 시간 복잡도는 O(2^N) 으로 너무 긴 시간이 걸린다.2. 동적계획법 (Dynamic Programming)각 자릿수가 자신을 포함했을 때의 최장 길이 부분 수열의 길.. Abstract와 Interface Java 관련 면접에서 자주 나오는 추상클래스와 인터페이스의 차이를 알아보자 인터페이스와 추상클래스는 비슷한점이 많지만 서로 다른 목적을 가진다.인터페이스: 인터페이스에 정의된 메서드들을 각 클래스의 목적에 맞게 구현한다.추상클래스: 자신의 기능을 아래로 확장시킨다. 목적공통 기능(상속) 제공.표준 규격 정의(구현).메서드추상 메서드 + 일반 메서드 가능.추상 메서드만 포함 (Java 8부터 default 메서드 지원).필드인스턴스 변수, 상수 모두 가능.상수만 가능 (Java 8 이후 일부 허용).다중 구현다중 상속 불가.다중 구현 가능. 좋은 git 커밋 메시지를 위한 7가지 약속 0. 커밋 첫줄 유형feat (feature)fix (bug fix)docs (documentation)style (formatting, missing semi colons, …)refactortest (when adding missing tests)chore (maintain)1. 제목과 본문을 한 줄 띄워 분리하기별거 아닐 수 있지만 git log 등을 사용했을 때 간편하게 로그를 확인 할 수 있다. 특히 git log --oneline 같은 것을 누군가 사용했을 때 위 규칙을 잘 적용했다면 깔끔하게 첫 제목만 출력되지만 만약 그렇지 않았다면 아주 많은 문장들이 출력 될 것이다. 2. 제목은 영문 기준 50자 이내제목을 길게 쓰는 것은 커밋하는 사람에겐 괜찮아도 다른 사람에겐 쓸대없이 더 많은 시간.. 배낭문제에서 넣은 것을 저장하는 아이디어 문제는 https://www.acmicpc.net/problem/14728 문제를 예로 들었다. 배낭문제를 푸는데 어떤 것을 넣었는지 기억해야하는 문제가 있었다. 나의 경우 trace 벡터를 만들고 배낭에 넣을 때의 따라 벡터를 조절하며 문제를 해결했다. 그러나 2차원 크기의 벡터가 필요하기 때문에 메모리가 상당히 많이 필요할 것으로 보여서 N이 충분히 작을 때만 사용할 수 있을 것 같다. 더 좋은 방법이 있을까... 트레이스 벡터는 만약 갱신하게 되면 i번 물건을 가져간다는 의미로 인덱스를 넣는다. dp와 거의 유사하게 동작한다. #include#includeusing namespace std;int N, M;int dp[101][10001];int main(){ cin >> N >> M; vector.. 누적합 알고리즘(1차원, 2차원 누적합) 누적합 알고리즘은 1~N까지 합을 효율적으로 구할 수 있는 알고리즘이다. 11 + 21 + 2 + 31 + 2 + 3 + 4 라고하면 sum[1] = 1sum[2] = 3sum[3] = 6sum[4] = 10 이고 여기서 2~4까지의 합을 구하면 sum[4] - sum[1] 과 같다. 즉 answer = sum[end] - sum[start - 1] 이다. 그리고 중요한건 모든 sum 배열을 구성하는 것이다. 이 때 O(N^2)의 시간을 사용하는 것은 너무 비효율적이다. 효율적으로 사용하기 위해 sum[2] = sum[1] + arr[2]sum[3] = sum[2] + arr[3]... 식을 사용하면 O(N)으로 prefix배열을 구성할 수 있다. 1차원 배열 누적합은 쉽게 구성이 가능하다. 이것을 응용.. 최소 스패닝 트리 (MST) - 크루스칼 알고리즘 MST는 최소 스패닝 트리의 줄임말로 어떤 그래프가 있을 때 모든 노드를 포함하여 사이클이 생기지 않는 트리를 뜻한다. 한붓그리기를 생각하면 편하다. 크루스칼 알고리즘은 Greedy 알고리즘의 일종이다. 간선을 선택할 때 가장 비용이 적은 간선을 선택하면서 사이클이 생기면 넘어가는 식으로 진행된다.그렇기 때문에 크루스칼 알고리즘은 모든 간선의 정보가 정렬되어 있어야 사용할 수 있고 모든 간선을 한번씩 검사하기 때문에 시간 복잡도 = 모든 간선의 수 + 정렬 시간 이 소요된다. 사이클을 검사해야하기 때문에 필연적으로 유니온 파인드 알고리즘도 필요하다. 나름 여러 알고리즘이 합쳐진 고급 알고리즘이라 할 수 있다. 정리해보면 1. 간선의 정보들을 모두 정렬한다. 간선의 비용이 적은 순서대로2. 선택한 간선들.. Dynamic Programming - Top Down, Bottom Up 다이나믹 프로그래밍은 메모이제이션을 사용해 이전에 사용한 값을 그대로 읽어 사용함으로서 극적으로 줄일 수 있다. 여기서 메모이제이션의 개념을 보면 마치 캐시 와 비슷해보인다. 그래서 혹자는 캐시질이라고도 한다. Top - Down큰 숫자에서 작은 숫자까지 내려가면서 솔루션을 구하는 방법이다. rec(N){ dp[N] = min(rec(N - 1), rec(N - 2))}Bottom - Up작은 숫자부터 시작하며 다음 숫자에서 이전의 값을 사용하는 정석적인 dp 방식이다. 주로 점화식을 찾아서 적용시킬 때 사용된다.for(int i = 2; i 운영체제 - 가상메모리의 개념 위 컴퓨터 구조에서 프로그램이 실행될 때, 예를들어 유튜브를 실행하거나 VS CODE 를 실행하려면 우리는 Main Memory 에 프로세스를 적재해야한다. 그리고 요즘 램은 16~32기가 정도 되는데 편의를 위해 10기가 라고 가정하자. 그리고 우리는 지금 메이플스토리, 워드, 카카오톡을 실행한다고 가정하자. 그런데 알다시피 요즘 메이플스토리 용량은 10기가가 넘는다. 그리고 워드도 1기가는 되고 카카오톡은 500메가 정도되지만 1기가라고 하면 메이플 : 10워드 : 1카톡: 1 이 세개의 프로그램을 동시에 실행하려면 메인 메모리에 무려 12기가가 필요하다! 그렇다면 이 세개는 실행이 안될까? 아니다. 아주 잘 될 것이다. 조금은 렉이 걸릴 수 있지만 잘된다. 이것을 가능캐 해주는 것이 가상메모리이다... 이전 1 2 3 4 ··· 7 다음 목록 더보기
