![]()
분류: 재귀, 좌표계 / 문제 문제 링크 문제 설명 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 입력 첫째 줄에 정수 N, r, c가 주어진다. 출력 r행 c열을 몇 번째로 방문했는지 출력한다. 풀이 - Python import sys readline = sys.stdin.readline def..
![]()
개인 프로젝트를 진행하던 도중 데이터베이스의 쿼리 실행 시간을 비교할 필요가 생겼습니다. 쿼리 실행 시간 측정 기능을 제공하는 패키지가 당연히 있을 줄 알았지만 찾지 못했고 저와 같은 기능을 찾는 사람들이 많다는 것을 알게 되어 패키지로 제작하게 되었습니다. 패키지 제작 이유부터 중간에 했던 시행착오들을 포함한 패키지 제작과정을 기록해 볼까 합니다. ❗️이 글은 2022년 2월에 작성된 글을 블로그를 리뉴얼하며 다시 작성한 글입니다. 노드에서 MySQL 쿼리 실행 속도 측정 MySQL의 쿼리 실행속도를 노드에서 측정하는 법을 검색해 보면 아래와 같은 방법이 나옵니다. // 시작시간 var start = new Date().getTime(); // 쿼리 실행 connection.query(query, fu..
![]()
최악의 경우 $\Theta(n^2)$의 시간복잡도를 갖지만 $\Omicron(n\log n)$ 평균적으로 가장 좋은 성능을 보이고 구현이 쉬워 현업에서 가장 많이 쓰인다고 알려진 퀵 정렬을 알아보고 자바와 파이썬으로 구현해 봅시다. 자료구조, 알고리즘 시리즈 모아보기 퀵 정렬 `퀵 정렬(quick sort)`은 병합 정렬 알고리즘과 비슷하게 입력을 나누어 각각에 대해 재귀적으로 정렬하는 알고리즘입니다. 퀵 정렬과 병합 정렬의 차이점은 크게 두 가지가 있습니다. 퀵 정렬은 병합 정렬과 달리 합치는 과정이 없고 입력을 항상 반씩 균등하게 나누지 않습니다. 퀵 정렬은 기준값정하고 기준값보다 큰 값들과 작은 값들로 입력을 분할합니다. 이때 기준값을 `피벗(pivot)`이라 합니다. - Pseudocode qui..
![]()
지금까지 기본적인 시간 복잡도가 $\Omicron(n^2)$인 정렬 알고리즘들을 알아봤습니다. 선택 정렬, 삽입 정렬, 버블 정렬은 모두 평균 $\Theta(n^2)$의 시간 복잡도를 가졌고 삽입정렬과 개선된 버블 정렬은 최선의 경우 $\Theta(n)$의 시간 복잡도를 가졌습니다. 이번에는 평균 $\Theta(n\log n)$의 시간 복잡도인 고급 정렬 알고리즘들에 대해 알아봅시다. 자료구조, 알고리즘 시리즈 모아보기 병합 정렬 `병합 정렬(merge sort)`은 입력을 반으로 나누어 각각 정렬한 뒤 합치는 재귀 알고리즘입니다. "정렬하는 방법이 반으로 나눈 뒤 각각 정렬하는거면 각각은 어떻게 정렬하라는 거지?" 싶을 수 있습니다. 재귀적으로 입력을 반으로 나눠 정렬하다보면 어느 순간 입력의 크기는 ..
![]()
그 유명한 버블 정렬에 대해 알아보고 C++, 자바, 파이썬으로 구현해 봅시다. 자료구조, 알고리즘 시리즈 모아보기 버블 정렬 `버블 정렬(bubble sort)`은 선택 정렬처럼 가장 큰 원소를 끝으로 옮기는 작업을 반복하는 알고리즘입니다. 선택 정렬이 큰 값을 콕 찍어서 옯겼다면 버블 정렬은 한쪽 끝에서 긁어 올라가며 더 큰 값만 가지고 올라가는 방식입니다. 이렇게 논리적으로 아래에서부터 수면 위로 올라가는 모습을 컴퓨터 과학에서는 버블링이라고 합니다. DOM트리에서 일어나는 이벤트 버블링도 아래에서 위로 올라가는 의미의 버블링이죠. - Pseudocode 정렬해야 하는 배열 A[n]이 주어졌을 때 버블 정렬 알고리즘은 다음과 같습니다. bubbleSort(A[], n){ for( last ← n d..
![]()
정렬 알고리즘 중 삽입 정렬을 알아보고 C++, 자바, 파이썬으로 구현해봅시다. 자료구조, 알고리즘 시리즈 모아보기 삽입 정렬 `삽입 정렬(insertion sort)`은 정렬된 부분을 하나씩 확장해 가며 모든 수열을 정렬하는 알고리즘입니다. - Pseudocode 정렬해야 하는 배열 A[n]이 주어졌을 때 삽입 정렬 알고리즘은 다음과 같습니다. insertionSort(A[], n){ for( last ← 2 to n ) A[1 ⋯ last] 에 A[last]가 들어갈 곳을 찾아 넣는다; } 구체화하면 아래와 같습니다. insertionSort(A[], n){ for( last ← 2 to n ){ newElement ← A[last]; // 추가할 요소 i ← last-1; // newElement와..
![]()
이번 글에서는 잘 사용하면 복잡한 연산을 쉽고 빠르게 처리할 수 있는 비트 연산과 시프트 연산을 알아보고 Java로 실습해 보겠습니다. 비트 연산 `비트 연산(bitwise operation)`은 이진수에 대해 비트 단위로 적용되는 연산입니다. 비트 연산자에는 논리 연산에서 사용되는 논리합(OR), 논리곱(AND), 배타적 논리곱(XOR), 부정(NOT)이 있습니다. 많은 프로그래밍 언어에서 `비트 연산자`로 &(AND), |(OR), ^(XOR), ~(NOT)을 사용합니다. `비트 연산의 진리표`는 논리 연산의 진리표에서 True와 False를 1과 0으로 바꾸면 됩니다. 진리표는 아래와 같습니다. AND(&) OR(|) XOR(^) NOT(~) 1 & 1 1 1 | 1 1 1 ^ 1 0 ~1 0 1 ..
![]()
정렬 알고리즘에서 가장 기본이 되는 선택 정렬을 알아보고 C++, 자바 그리고 파이썬으로 구현해봅시다. 자료구조, 알고리즘 시리즈 모아보기 선택 정렬 `선택 정렬(selection sort)`은 정렬할 수열에서 가장 큰 값(혹은 가장 작은 값)을 선택해 한쪽 끝으로 옮기는 행위를 반복하여 정렬하는 알고리즘입니다. - Pseudocode 정렬해야 하는 배열 A[n]이 주어졌을 때 선택 정렬 알고리즘은 다음과 같습니다. selectionSort(A[], n){ for( last ← n downto 2 ){ A[1 ⋯ last] 중 가장 큰 수 A[k]를 찾는다; A[k] ↔︎ A[last]; } } 조금 더 구체화하면 아래와 같습니다. selectionSort(A[], n){ for( last ← n dow..
![]()
저번 글에서는 시간 복잡도가 무엇인지와 시간 복잡도를 표현하는 점근적 표기법에 대해 알아봤습니다. 이번 글에서는 구조가 복잡한 재귀 알고리즘의 시간 복잡도를 어떻게 계산하는지 살펴봅시다. 자료구조, 알고리즘 시리즈 모아보기 재귀 알고리즘 `재귀 알고리즘`은 어떤 문제를 해결할 때 크기가 더 작은 동일한 문제를 해결해 얻은 답을 이용하는 알고리즘입니다. 말로 풀어 설명하는 것보다 직접 보는 게 더 이해가 쉬우실 겁니다. 대표적으로 팩토리얼과 피보나치 수열이 있습니다. 1. 팩토리얼 더보기 입력 n이 주어졌을 때 $n!$을 계산하는 함수를 $f_{actorial}(n)$이라고 합시다. $$\begin{align*}f_{actorial}(5)&=5\times f_{actorial}(4)\\&=5\times4\..
![]()
제가 사용한 hELLO Tistory 스킨에 Katex를 적용하는 방법을 공유해 볼까 합니다. hELLO 스킨에 KaTeX 적용하기 KaTeX 공식 문서에 나와있는 CDN을 티스토리 스킨 편집에서 html head에 넣어봤으나 적용이 됐다 안 됐다 하는 버그가 있었습니다. hELLO 스킨은 alphine.js와 pug로 만들어진 SPA이기 때문에 생긴 버그가 아닐까 추측돼서 스킨에 직접 적용하기로 했습니다. 스킨의 app.pug에 CDN을 넣어봅시다. 모바일 모드에서도 KaTeX 적용하기 위 방법으로 KaTeX를 적용했을 때 모바일 모드(tistory.com/m/)에서는 적용이 안 되는 버그가 있었습니다. 아마 모바일 모드에서는 스킨 적용이 안 돼서 그런 것 같습니다. 저는 블로그 글 안에 스크립트 태그..
![]()
알고리즘의 성능과 효율성을 판단할 때 주로 시간 복잡도를 가장 중요하게 생각합니다. 이번 글에서는 시간 복잡도가 무엇인지와 시간 복잡도를 단순화하여 표현하는 점근적 표기법(빅 오, 리틀 오, 빅 세타, 빅 오메가, 리틀 오메가)에 대해 알아보겠습니다. 자료구조, 알고리즘 시리즈 모아보기 시간 복잡도(Time Complexity) 알고리즘의 복잡성(효율성 혹은 성능)은 알고리즘 수행에 소모되는 자원의 양으로 판단됩니다. 여기서 자원은 소요 시간, 메모리, 통신대역 등이 될 수 있지만 가장 중요하게 생각되는 판단 기준은 소요 시간입니다. 메모리는 돈으로 어느 정도 해결 할 수 있지만 시간은 돈으로 살 수 없으니까요. 알고리즘의 시간 복잡도(소요 시간)는 입력 크기에 대한 함수로 표현할 수 있습니다. 아래 코..
![]()
프레임워크를 사용하거나 공부하다 보면 의존성 주입, 제어의 역전과 같은 말을 많이 접하게 됩니다. 대충 이런 뜻이겠거니 하며 짐작은 가지만 정확히 무엇을 말하는지 모르겠습니다. 이번 글에서는 의존성 주입이 무엇인지 왜 이런 개념들이 등장했고 왜 사용하는지 알아보겠습니다. 의존성 의존성 주입을 알아보기 전에 먼저 의존성에 대해 알아봅시다. 프로그래밍에서 `의존성(Dependency)`는 변경 혹은 에러로부터 영향을 받는다는 의미로 이해할 수 있습니다. 즉, "A가 B에 대한 의존성을 갖는다."라는 말은 A가 B의 변경 혹은 에러로부터 영향을 받는다는 의미로 받아들일 수 있습니다. 예시 1 - 의존성 아주 간단한 예시를 들어보겠습니다. 사람이 음료수를 먹는 예시입니다. 이 글은 아래 예시 코드를 고쳐가며 설..
