알고리즘15 이진 트리 트리와 터미널로지 트리 구조 자료의 계층적인 성질을 토식으로 표현하는 방법 Etc): 조직도, 토너먼트, 카테고리, 파일 시스템, etc… 루트가 있는 트리 트리 구조를 노드와 간선의 집합으로 표현한 것 (일반적인 트리)트리 루트가 없는 트리 → 사이클이 없고 방향이 없고 연결된 그래프 → 트리에는 루트가 없지만 루트를 정하면 루티드 트리가 된다. 노드 유닛, 노드 혹은 버텍스라고 부른다. 간선 두 노드 사이에 있는 연결, 엣지 혹은 아크라고 부른다. 부모 노드 노드 X의 부모 노드는 X와 간선으로 연결된 노드 중 루트에 더 가까운 노드 자식 노드 노드 X의 부모 노드는 X와 간선으로 연결된 노드 중 루트에서 더 멀리있는 노드 단말 노드 자식이 없는 노드, 리프 노드라고 한다. 내부 노드 단말 노드가 아.. 2023. 4. 8. 구현 아이디어를 코드로 바꾸는 구현 코딩 테스트에서 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 그런 의미에서 알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않는다. 하지만 취업을 목표로 하는 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제 되기에 다른 알고리즘을 배우기 전에 먼저 다룬다. 알고리즘 문제를 해결할 떄 문제를 읽고 풀이 방법을 고민한다. 이후 구현을 위해 프로그래밍 언어의 문법을 정확히 알고 있어야하고 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야한다. 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드.. 2023. 2. 12. 그리디 알고리즘 당장 좋은 것만 선택하는 그리디 그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 그리지 알고리즘을 이용하면 매순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 코딩 테스트에서 만나게 될 그리디 알고리즘의 문제 유형을 앞으로 다루게 된 알고리즘과 비교했을 때 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이라는 특징이 있다. 반면 이후에 공부할 정렬, 최단 경로 등의 알고리즘 유형은 이미 그 알고리즘의 사용 방법을 정확히 알고 있어야만 해결 가능한 경우가 많다. 예를 들어 여러 개의 데이터를 빠르게.. 2023. 2. 12. 1/29 WIL 1. 알고리즘 관련 공부 이번 주는 공부했던 알고리즘 지식을 정리하려 한다. 냅색 알고리즘 (Knapsack Algorithm) 유명한 다이나믹 프로그래밍 문제 혹은 그리디 알고리즘 문제 중 하나이다. 두 가지 유형으로 나뉜다. Fractional Knapsack Algorithm: 주어진 자원을 쪼갤 수 있다는 가정 하에 그리디 알고리즘으로 최적의 조건이 구해진다. 주어진 조건(ex: 가격, 무게) 중 가장 크거나 작은 것부터 대입하여 최적 방식을 구한다.(그리디 알고리즘) 0 - 1 Knapsack Algorithm: 주어진 자원이 0 또는 1, 즉 존재하거나 존재하지 않는, 쪼갤 수 없는 상태면 DP를 사용해야한다. 보통 후자의 문제가 자주 나온다. 그래서 쪼갤 수 없는 보석이 나오면 제로원, 디피.. 2023. 1. 31. 이전 1 2 3 4 다음
