이진 트리의 자식 표현 방법 이진 트리는 트리와 달리 자식의 Left, Right에 대한 정보가 반드시 필요하다. 따라서 일반적인 그래프로 구현하기 힘들다. 배열, 구조체, 연결리스트 등으로 표현가능하지만 트리의 구조를 이용하여 배열로 간단하게 나타낼 수 있다. 이진 트리의 4가지 순회 방법 1. 레벨 순회(Lever Travel) Level Travel은 트리이 깊이를 순차적으로 탐색한다. 방문 순서는 cur → Left Child → Right Child이다. 레벨 순회는 BFS와 유사한 구조를 가진다. 구현은 일반적인 BFS처럼 해주면 된다. 이를 코드로 구현하면 다음과 같다. void levelTravel(){ queue q; q.push(1); while(!q.empty()){ int cur =..

1. 두 포인터란? 포인터 두 개를 사용하여 배열이나 문자열을 탐색하는 알고리즘이다. 흔히 배열을 탐색하다 보면 완전탐색을 진행할 경우 O(N²)의 시간복잡도를 가진다. 하지만 투 포인터를 이용하면 동시에 포인터 두 개로 탐색하므로 O(N)의 시간 복잡도로 한 번에 탐색할 수 있다. 예시 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net #include #include using namespace std; int N, M, a..

최적화(최대 or 최소)문제를 결정 문제로 바꾸어서 푸는 기법이다. 의심: 완전탐색, DP, 그리디로도 해결할 수 없는 최적화문제의 경우에 두 데이터간의 관계가 단순 비례 반비례에 따른 증감이며 Parameteric Search를 의심해볼 수 있다. 보통 감을 잡기가 매우 어려워서 나중에 돌아와서 떠올리면 베스트 파라메트릭 서치는 STL을 직접 이용할 수 있는 이분탐색과 달리 직접 변수를 설정하고 관계에 따라서 탐색의 범위를 지정해주어야 한다. ??? 예제: 랜선 자르기 백준 1654 주의 사항: 1. 무한 루프 주의: mid를 기준으로 선택의 범위가 균등한지 만약 균등하지 않다면 mid+1로 보정해줘서 무한루프를 방지해줘야함 2. 두 변수간의 관계주의: parameter과 target간의 관계(비례 반..