Coding Diary

문제 및 코드 생각 // 생각 // 대놓고 큐를 쓰라고 알려 줬음. 근데 우선순위 큐인가 // 구현 // 우선순위 큐를 만들어서 priorities를 우선순위 큐에 넣는다 // 우선순위 큐를 돈다 // priorities를 돈다 // 우선순위 큐의 값과 priorities의 값이 같다 // priorities를 도는 index와 location 값이 같다 // answer에 1 추가하고 답으로 return // priorities를 도는 index와 location 값이 다르다 // 큐에서 값 하나 빼고 answer에 1 추가하고 다음 priorities로 넘어간다 // 우선순위 큐의 값과 priorities의 값이 다르다 // 다음 priorities로 넘어간다 회고 문제 이해가 잘 안 돼서 시간이 좀..

문제 및 코드 GitHub - Lee-Min-Jung/coding_test_practice Contribute to Lee-Min-Jung/coding_test_practice development by creating an account on GitHub. github.com 생각 // 생각 // 분류별 개수는 map으로 저장 // 구현 // clothes 돌면서 분류별로 개수 세서 map에 저장 // 회고 arrayList를 map에 넣어서 어떻게 해야할지 번뜩이는 생각이 안 나서 참고를 함 개수 세는 거는 의외로 간단하게 끝났음 근데 다른 풀이 보니 개수만 세면 되니까 굳이 arrayList를 안 만들고 개수만 map에 넣어도 될 것 같음 ---- map 쓰는 것까지는 생각을 했는데 개수를 어떻게 ..

문제 및 코드 GitHub - Lee-Min-Jung/coding_test_practice Contribute to Lee-Min-Jung/coding_test_practice development by creating an account on GitHub. github.com 수정된 코드 GitHub - Lee-Min-Jung/coding_test_practice Contribute to Lee-Min-Jung/coding_test_practice development by creating an account on GitHub. github.com 생각 아래 처럼 생각해서 풀었는데 테스트 케이스는 통과하나 정답 통과는 되지 않는다... 효율성 통과가 되지 않는 것을 보니 이중 for문 때문에 시간복잡도..

1. 개념 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법 2. 특징 큰 문제를 작은 문제로 나눌 수 있어야 한다 작은 문제들이 반복되고, 작은 문제들의 결과값은 항상 같아야 한다. 작은 문제들은 한 번만 계산해 DP 테이블에 저장한다. 이후에 재사용할 때는 DP 테이블에 있는 것을 사용한다. 이는 메모이제이션 기법이다. 톱 다운 방식과 바텀 업 방식으로 구현 가능하다 3. 원리 피보나치 수열을 통해 원리를 알아보자. 피보나치 수열 공식: D[N] = D[N-1] + D[N-2] 1) 동적 계획법으로 풀 수 있는지 확인하기 피보나치 수열의 3번째 값은 1번째 값과 2번째 값의 합이다. 그리고 이는 수열이 진행되면서 반복된다. 즉 큰 ..

1. 개념 n개 중 r개를 선택하는 경우의 수를 뜻한다. 이때, 선택한 것들의 순서가 달라도 같은 것이라고 처리한다. 예를 들어 1 2 3 4 5 중 2개를 뽑았을 때 1 2 를 뽑은 것과 2 1 을 뽑은 것을 같은 것이라고 보는 것이다. 2. 공식 3. 점화식 1) 조합 공식보다 점화식을 사용하면 좋은 이유 조합 공식의 경우 팩토리얼 연산을 사용해야 하는데 큰 수의 경우 계산 비용이 높다. 팩토리얼 연산을 재귀로 구현할 경우 스택 오버 플로우 문제가 발생할 수 있다. 점화식을 사용하면 반복 계산을 피할 수 있다. 이전에 계산된 것을 동적 계획법의 방식으로 사용하기 때문에 계산 비용을 줄일 수 있고 더 효율적으로 접근할 수 있다. 2) 점화식 개념 점화식을 세울 때는 모든 부분 문제가 해결된 상황이라고 ..

1. 개념 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드를 최소 공통 조상이라고 한다. 2. 원리 1) 일반적인 최소 공통 조상 구하기 4번과 15번 노드의 최소 공통 조상을 구한다고 가정. 루트 노드에서 탐색을 시작해 4번의 부모 노드와 깊이를 저장, 루트 노드에서 탐색을 시작해 15번의 부모 노드와 깊이를 저장 선택된 두 노드의 깊이가 같은 경우 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복 - 1 선택된 두 노드의 깊이가 다른 경우 더 깊은 노드의 노드를 부모 노드로 올려서 같은 깊이로 맞추기 그리고 1을 진행 트리의 높이가 커질 경우 시간 제약 문제에 직면할 수 있다..

1. 개념 각 노드의 자식 노드의 개수가 2 이하로 구성돼 있는 트리이다. 2. 종류 1) 편향 이진 트리 노드들이 한쪽으로 편향돼 생성된 이진트리 이렇게 저장된 이진 트리는 탐색 속도가 저하되고 공간이 많이 낭비된다 2) 포화 이진 트리 트리의 높이가 모두 일정하며 리프 노드가 꽉찬 이진 트리 3) 완전 이진 트리 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고 마지막 레벨은 왼쪽부터 채워진 트리 4) 이진 탐색 트리 루트보다 작은 값은 왼쪽에 위치, 루트보다 큰 값은 오른쪽에 위치하도록 하여 노드를 저장 데이터를 효율적으로 저장하고 검색, 삭제할 수 있다. 3. 트리의 노드와 배열 인덱스의 상관관계 루트 노드 인덱스 = 1 부모 노드 인덱스 = 현재 노드 인덱스 / 2 (현재 노드가 루트가 아니..

1. 개념 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조. 각 노드는 문자 혹은 문자열의 한 글자를 나타낸다. 또한, 각 노드는 자식을 가지고 있을 수 있는데, 이는 각 노드의 다음 문자를 나타낸다. 2. 특징 루트 노드는 항상 공백이다. N진 트리의 형식을 가진다. 문자 종류에 따라 N이 결정된다. 알파벳은 26개의 문자로 이루어져 있기 때문에 26진 트리 형태를 갖게 된다. 즉 부모 노드가 자식을 최대 26개까지 가질 수 있다는 것이다. 각 문자의 접두사를 공유하기 때문에 검색이 빠르다. 트리 형태로 문자를 저장하기 때문에 삽입과 삭제 연산이 빠르다. 조건을 만족한다면 상수시간 안에도 가능하다. 3. 구현 // 트라이에서 사용하는 노드 정의 class tNode{ tNode[] ..

1. 개념 노드와 에지로 연결된 그래프의 특수한 형태. 2. 특징 순환 구조를 가지고 있지 않다. 1개의 루트 노드가 존재한다. 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다. 트리의 부분 트리도 트리의 모든 특징을 따른다. 3. 트리의 구성 요소 1) 루트 노드 2) 부모 노드 3) 자식 노드 4) 에지 5) 리프 노드 6) 서브 트리 4. 구현 1) 그래프 이용 그래프 구현을 이용해서 구현하면 된다. 인접 리스트 사용. 동적으로 크기 조정이 가능하다. 연결리스트로 구현되기 때문에 노드의 삽입과 삭제가 쉽다. 특정 위치의 노드에 접근하기 위해서 연결리스트를 순회해야 해서 접근 시간이 오래 걸린다. 다음 노드를 가리키는 정보를 저장해야 해서 메모리 사용량이 증가할 수 있다. adjList = ..

1. 개념 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다. 2. 특징 사이클은 없어야 한다. 사이클이 있으면 가중치의 합이 최소가 될 수 없기 때문이다. N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개다. 에지 리스트의 형태로 구현하는 것이 간단하다. 3. 종류 1) 크루스칼 모든 에지를 가중치 기준으로 오름차순으로 정렬한 후, 가중치가 작은 간선부터 선택하면서 사이클을 형성하지 않도록 하여 최소 신장 트리를 만든다. 2) 프림 시작 노드부터 출발하여 가장 가까운 노드를 선택하며, 해당 노드와 연결된 에지 중 가장 가중치가 작은 간선을 선택하는 방식으로 최소 신장 트리를 만든다. 4. 크루스칼 1) 원리 에지 리스트를 생성한다. 에지 리..