CS (51) 썸네일형 리스트형 배낭문제에서 넣은 것을 저장하는 아이디어 문제는 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기가가 필요하다! 그렇다면 이 세개는 실행이 안될까? 아니다. 아주 잘 될 것이다. 조금은 렉이 걸릴 수 있지만 잘된다. 이것을 가능캐 해주는 것이 가상메모리이다... OS - 메모리관리: 페이징 위 사진은 CPU의 논리주소를 RAM의 물리주소로 바꾸는 작업을 수행하는 일반적인 컴퓨터구조이다.외부 단편화램은 하나하나 프레임으로 구성된다. 그리고 각 하나의 같은 크기를 갖고 있는데 만약 위처럼 4바이트로 구성되었다고 하자. 그리고 빨간색으로 칠해진 곳은 사용중이라 하면 8바이트짜리 프로세스가 램에 로드하려 한다. 지금 4바이트 짜리 프레임이 3칸 12바이트가 있으니까 로드할 수 있을까? 로드할 수가 없다! 왜냐하면 CPU는 연속적으로 램에 들어있어야 읽을 수 있기 때문이다. 그럼 지금 램에는 3칸의 빈칸이 있는데도 램에 자리가 없다고 판단되어 시스템에 지장을 준다. 이것을 외부 단편화라 한다. 페이징위의 외부 단편화를 해결하기 위한 방법으로 페이징이 있다. 페이징은 프로세스를 페이징 단위로 나눈다... 알고리즘 - 에라토스테네스의 체(C++) 최근 코딩테스트에서 소수를 판별해야하는 문제가 나왔다. 그래서 에라토스테네스의 체를 사용해야함을 바로 알았지만 아쉽게 떠올리지 못하여 정리해두려고 한다. 원래 소수를 판별하는 방법은 대학교 1학년 C언어 시간에 배울 정도로 쉽다. N까지 모두 나눠보며 나눠 떨어지는 수가 2이면 소수이다. 그러나 이것은 매우 시간이 오래걸린다. 에라토스테네스의 체는 이 수가 소수인지 아닌지 판별하는 것이 아니라 1~100만 등 어떠한 범위내에서 소수인지 아닌지 판별할 때 유용하다. 즉 1~100만 중 소수가 몇개인가? 이러한 것을 해결하는 방법이다. 알고리즘은 다음과 같다. 1. 2 ~ N까지 2의 배수를 false 처리한다. 2. 3 ~ N까지 3의 배수를 false 처리한다.4. 5 ~ N까지 5의 배수를 fals.. VScode Git 계정 이름 바꾸기 VScode 에서 Private 레포지토리를 클론해야할 일이 생겼다. 어떠한 이유로 내 깃허브 계정이 아닌 그 Private 레포지토리의 주인의 깃허브 계정을 받아 클론해야했는데 VScode 에서 그 계정으로 로그인 했는데도 깃클론이 되지 않았다. VScode 에서 사용자는 아직 나였기 때문이다. 그래서window 자격증명에서 github 연동을 지우고 나서야 새로운 계정의 자격이 내 PC에 부여되었다. 이전 1 2 3 4 ··· 7 다음
