Ikjo's Technology blog

문제 설명 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 접근 방법 해당 문제에서는 중위 순회 결과와 후위 순회 결과가 주어졌을 때 이를 통해 전위 순회 결과를 요구하고 있습니다. 이를 위해선 중위 순회 결과와 후위 순회의 결과로 트리를 재현하는 것이 우선입니다. (참고로 '전위 순회 결과와 중위 순회의 결과' 그리고 '중위 순회 결과와 후위 순회 결과'로는 트리를 재현할 수 있지만, '전위 순회의 결과와 후위 순회의 결과'로는 트리를 재현할 수 없습니다.) 우선 이 문제에 접근하기 앞서 중위 순회와 후위 순회의 특성에 대해 알아야합..

문제 설명 Number of Times Binary String Is Prefix-Aligned - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 접근 방법 나의 접근 방법 flips 배열 크기의 boolean형 배열을 생성 후 flips 값 순서대로 해당 배열의 인덱스에 true를 할당해주었습니다. 이후 배열의 인덱스가 1부터 현재 단계의 수(n'th step)까지 모두 true일 경우 결과값에 1을 더해주도록 했습니다. 하지만, 이 경우 flips 값과 상관..

병합 정렬이란? 병합 정렬은 퀵 정렬과 마찬가지로 분할 정복 알고리즘으로서 주어진 데이터를 두 개의 균등한 크기로 분할하고 분할된 영역을 정렬한 후 병합해 나가는 방식으로 정렬한다. 이때 분할하고 병합하는 과정에서 기존 데이터 전체 크기와 동일한 추가적인 자료구조를 사용하므로 O(n)의 공간 복잡도를 가진다. 그림으로 병합 정렬 이해하기 아래와 같이 최초 정렬되지 않은 크기 10의 정수형 배열이 있다고 가정했을 때, 병합 정렬을 통해 오름차순으로 정렬해보자. 우선, 주어진 배열의 영역을 절반씩 분할해나가는데, 영역의 크기가 2개 이하가 될 때까지 분할해나간다. 이때 분할해나가는 과정은 마치 깊이 우선 탐색과도 같다. 분할을 해나가는 중 영역의 크기가 2개 이하가 됐을 경우 즉, 더 이상 분할할 게 없는 ..

퀵 정렬이란? 퀵 정렬은 주어진 데이터 상 특정 값(피벗)을 기준으로 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 옮겨 2개의 파티션(Partition)으로 분할(Divide)해 나가는 방식으로 정렬한다. 퀵 정렬에 사용되는 기법을 분할 정복 알고리즘(Divide and conquer algorithm)이라고 하는데, 이는 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 분할 정복 알고리즘은 일반적으로 재귀 함수(Recursive function)를 통해 자연스럽게 구현된다. 퀵 정렬은 주어진 데이터 상 최초 피벗을 몇 번째 데이터로 정하는지에 따라 그리고 데이터 상태에 따라 다른 성능을 보일 수 있는데, 대표적으로 배열의 첫 번째 데이터를 피벗으로 정하는 호어 분할 방식이 있..

삽입 정렬이란? 삽입 정렬은 주어진 데이터들을 순회하면서 특정 데이터를 적절한 위치에 삽입하는 방식으로 정렬한다. 이때 마법의 단어 '적절한'이 들어갔는데, 이 단어가 이전에 다루었던 버블 정렬과 선택 정렬과의 차이를 낳는다. 이전에 다루었던 버블 정렬과 선택 정렬의 경우, 주어진 데이터의 정렬 상태 등에 상관없이 항상 모든 요소를 순회하면서 비교하는 비효율적인 문제가 있었다. 하지만 삽입 정렬의 경우, 순회 중 특정 데이터를 삽입할 적절한 위치를 찾으면 삽입 후 기존 순회를 중단하고 다음 순회로 넘어간다. 이로써 기존 데이터의 상태가 어느정도 정렬된 상태라면, 더욱 빠른 속도로 정렬할 수 있게 된다. 그림으로 삽입 정렬의 원리 이해하기 아래와 같이 최초 정렬되지 않은 크기 10의 정수형 배열이 있다고 ..