CS (53) 썸네일형 리스트형 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기가가 필요하다! 그렇다면 이 세개는 실행이 안될까? 아니다. 아주 잘 될 것이다. 조금은 렉이 걸릴 수 있지만 잘된다. 이것을 가능캐 해주는 것이 가상메모리이다... OS - 메모리관리: 페이징 위 사진은 CPU의 논리주소를 RAM의 물리주소로 바꾸는 작업을 수행하는 일반적인 컴퓨터구조이다.외부 단편화램은 하나하나 프레임으로 구성된다. 그리고 각 하나의 같은 크기를 갖고 있는데 만약 위처럼 4바이트로 구성되었다고 하자. 그리고 빨간색으로 칠해진 곳은 사용중이라 하면 8바이트짜리 프로세스가 램에 로드하려 한다. 지금 4바이트 짜리 프레임이 3칸 12바이트가 있으니까 로드할 수 있을까? 로드할 수가 없다! 왜냐하면 CPU는 연속적으로 램에 들어있어야 읽을 수 있기 때문이다. 그럼 지금 램에는 3칸의 빈칸이 있는데도 램에 자리가 없다고 판단되어 시스템에 지장을 준다. 이것을 외부 단편화라 한다. 페이징위의 외부 단편화를 해결하기 위한 방법으로 페이징이 있다. 페이징은 프로세스를 페이징 단위로 나눈다... 이전 1 2 3 4 ··· 7 다음
