프로그래밍나무

백엔드 면접 기초 질문 리스트 https://haejun0317.tistory.com/238?category=987777 자료구조 알고리즘 관련 https://okky.kr/article/673648 면접 대답하는 법 및 기술 면접 질문 리스트 https://www.youtube.com/watch?v=Mna7gby8Tcs&t=2885s

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 위 문제의 그림을 가지고 설명하였습니다. 전위 순회 전위 순회는 Root - 왼쪽 서브 트리 - 오른쪽 서브 트리 순으로 방문합니다 이진 탐색 트리는 왼쪽 서브 트리의 값들은 Root 보다 작고 오른쪽 서브트리의 값들은 Root보다 크므로 전위 순회한 결과를 통해 트리의 구조를 나타낼 수 있습니다. 50 30 24 5 28 45 98 52 60 같은 전위 순회 결과의 경우 50 | 3..

https://gyoogle.dev/blog/ 👨🏻‍💻 Tech Interview gyoogle.dev 위 블로그를 보고 간략하게 정리한 글 입니다. Algorithm 거품 정렬(Bubble Sort): 인접한 원소의 대소 비교를 통해 (오름차순일 경우) 제일 큰 원소를 뒤로 보냄. 안정정렬. O(n^2) 선택 정렬(Selection Sort): (오름차순일 경우) 제일 작은 원소를 찾고 맨 앞의 원소와 교환. 불안정정렬. O(n^2) 삽입 정렬(Insertion Sort): 2번째 원소부터 앞 원소들을 탐색하며 자신의 자리를 찾아감. 안정정렬. 최선 O(n). 평균 최악O(n^2) 퀵 정렬(Quick Sort): 1번째 원소를 피벗으로 하고 피벗보다 작은 원소들은 왼쪽, 큰 원소들은 오른쪽에 있도록 원..

개념 세그먼트 트리는 간격에 대한 정보를 저장하는 자료구조입니다. 이를 이용하면 구간 합, 구간 최댓값/최솟값 들을 빠르게 구할 수 있습니다. 보통 구간 합을 구하는 방법은 해당 구간을 전부 탐색하면서 합을 구하는 방식입니다. 이 방법은 O(N)의 시간이 걸립니다. 하지만 세그먼트 트리의 경우 구간을 탐색하는데 O(lgN)의 시간밖에 걸리지 않습니다. 해당 글은 구간의 최솟값들을 구하는 방법으로 설명하겠습니다. https://www.acmicpc.net/problem/14438 14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i..

개념 서로 중복되지 않는 부분 집합들을 표현할 때 사용하는 알고리즘 해당 알고리즘에 필요한 연산은 부분 집합들을 서로 묶는 연산(Union), 해당 원소가 어느 집합에 속해있는지 찾는 연산(Find)이 있습니다. 부분 집합들을 표현하는 방법 배열 해당 원소가 몇 번째 집합에 속해 있는지 각각의 원소마다 표시합니다. 1번째 부분 집합 : {0, 1, 2} 0 -> 1, 1 -> 1, 2 -> 1 Union 연산: 모든 원소에 대해서 몇 번째 집합에 속해 있는지에 대한 수정이 일어납니다.( O(N) ) Find 연산: 해당 원소가 몇 번째 집합에 속해있는지 바로 찾을 수 있습니다.( O(1) ) 트리 부분집합마다 트리를 생성하여 각 원소가 부모 원소를 표시하고 있습니다(루트 원소는 자기 자신을 표시) 1번째..

개념 오름차순으로 정렬된 리스트에서 특정한 값을 찾는 알고리즘입니다 의사코드 BinarySearch(A[0..N-1], value, low, high) { if (high value) return BinarySearch(A, value, low, mid-1) else if (A[mid] < value) return BinarySearch(A, value, mid+1, high) else return mid // found } BinarySearch(정렬된 배열, 찾을 값, 배열의 첫 인덱스, 배열의 마지막 인덱스) 를 통해 이진 탐색을 수행할 수 있습니다 활용 그러면 해당 알고리즘을 코테 문제에 어떻게 적용할 수 있는지 생각해 보겠습니다. https://www.acmicpc.net/problem/1300..

배낭 문제는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법입니다. 이 배낭 문제는 두 가지로 나누어집니다. 짐을 쪼갤 수 있는 경우인 분할 가능 배낭(Fractional Knapsack) 짐을 쪼갤 수 없는 경우인 0-1 배낭(0-1 Knapsack) 분할 가능 배낭 이 문제는 그리디 알고리즘을 적용하면 다항 시간 안에 풀 수 있습니다. 짐을 쪼갤 수 있는 경우에는 무게당 가치가 제일 높은 물건이 먼저 들어가야 하므로 각 물건의 가치/무게를 구한 다음 가장 높은 물건부터 무게의 최댓값까지 넣습니다. 0-1 배낭 이 문제는 백준 12865번의 예제를 참고하여 설명하겠습니다. 물건을 담았을 때의 가치를 계산할..