Ikjo's Technology blog

지난 한 주 되돌아보기 벌써 9월이다. 🍂 작년에 위염으로 한동안 학습을 중단하고 다시 마음을 다잡고 학습을 시작했을 때가 9월 즈음이었는데, 시간이 정말 빠르다. 요즘에는 한 주 한 주 어떤 성과를 내겠다는 마음 보다도 '꾸준히'만 하자는 마음으로 꾸역꾸역(?) 학습을 하고있다. 정렬 알고리즘을 파헤쳐보다! 사실 자바 프로그래밍을 하면서 기본 정렬 API(Collections 클래스의 sort 메서드, Arrays 클래스의 sort 메서드)로 컬렉션이나 배열을 정렬해왔었기에 버블 정렬, 선택 정렬, 삽입 정렬 등 정렬의 원리나 구현에 대해 학습해야 할 필요성을 느끼지 못했었는데, 간혹 면접 때 이와 관련한 질문이 나온다는 얘기를 듣고 이에 대해 정리해보고싶다는 생각이 들었다. 어떻게 보면 반강제적(?)..

문제 설명 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)를 통해 자연스럽게 구현된다. 퀵 정렬은 주어진 데이터 상 최초 피벗을 몇 번째 데이터로 정하는지에 따라 그리고 데이터 상태에 따라 다른 성능을 보일 수 있는데, 대표적으로 배열의 첫 번째 데이터를 피벗으로 정하는 호어 분할 방식이 있..