이 포스팅은 동빈나님의 코딩테스트 & 알고리즘 대회 핵심 노트 - 투 포인터, 구간 합이라는 강의를 보고 쓴 것이다. 배열의 특정 연속된 구간을 처리하기 원하는 경우 문제에서 연속된 데이터 구간을 처리하기를 원한다면? 다양한 접근 방법을 떠올려 보는 것이 중요! 자주 사용되는 기법들로는 어떤 것들이 있을까? 이 강의에서 나오는 대단한 풀이를 보고 그냥 지나칠 수가 없었다. 세상엔 정말 날고 기는 사람들이 많다는 것을 다시 한 번 느낀다. 분명히 프로그래머스라는 사이트에서 이러한 유형의 문제를 풀때 이중 반복문을 남발했던 것 같은데... 요새 자료구조를 복습하는 입장에서 볼 때, 과거의 나는 효율성이라고는 1도 고민하지 않고 문제를 풀었던 것 같다. 이 강의는 배열의 특정 연속된 구간을 처리하는 것을 목적..

1. 순열 순열은 서로 다른 n개의 원소에서 r개를 뽑아서 한 줄로 세우는 경우의 수를 말한다. 여기서 r,n은 자연수이며 r은 n이하여야만 한다. 또한 순열은 정의역과 공역이 같은 일대일 대응이다. 여기서 일대일 대응은 두 집합 사이를 중복 없이 모두 일대일로 대응시키는 함수를 말한다. 순열은 경우의 수이고 일대일대응이다. 왜 그런지 예를 한번 들어보자. 앞에서 경우의 수에 대해서 이야기를 하지 않았는데, 경우의 수는 1회의 시행에서 일어날 수 있는 사건의 수를 말한다. 아래 그림은 네 개의 문자를 가지고 있는 배열이 있는데, 네 개 중에 두 개의 문자를 임의로 골라 중복없이 조합하여 길이가 2인 단어를 생성하려고 하는 상황을 나타낸 것이다. 따라서 위의 예시를 보면, 두 개의 독립사건이 있는데, 첫 ..

1. 병합 정렬 병합 정렬은 여러 개의 정렬된 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만드는 방법을 말한다. 병합 정렬도 퀵 정렬 처럼 분할정복 알고리즘을 이용하는 방법이며, 속도 또한 퀵 정렬과 같이 $$ O(N\times log_2{N}) $$ 의 성능을 보인다. 병합 정렬이 퀵 정렬과 속도는 같지만, 퀵 정렬은 최악의 경우 $$ O(N^2) $$ 의 속도를 가지지만, 병합 정렬은 최악의 경우에도 $$ O(N\times log_2{N}) $$ 의 속도를 가지는 매우 안정적인 정렬이라고 할 수 있다. 2. 동작 순서 병합 정렬의 동작 순서는 매우 간단하다. 2개씩 나누어서 분할 한 후 (재귀 함수를 이용) 결합을 하면 되는데, 주의할 점은 결합을 함과 동시에 정렬 작업을 해주어야 한다. 3. ..

1. 퀵 정렬 "퀵"이라는 말 그대로 정말 정말 정말 빠른 정렬이다. 퀵 정렬은 특별한 경우를 제외하고는 정렬할 전체 원소에 대해서 정렬을 수행하지 않는다. 따라서 퀵 정렬의 시간 복잡도는 $$ O(N\times log_2{N}) $$ 이다. 여태 포스팅했던 선택 정렬, 버블 정렬, 삽입 정렬의 시간 복잡도는 $$ O(N^2) $$ 이다. 고등학교 수학을 배운 사람이라면 $$ N^2 > N \times log_2{N} $$ 이 성립된다는 것을 알 수 있다. 하지만, 빅오 표기법에서 log₂N과 N²의 차이는 어느정도일까? 차이는 어마무시하다고 말할 수 있다. $$ N=2^{10} $$ 일 때를 예로 들어보자. 2를 10번 곱하면 1024이다. 하지만 컴퓨터에서는 1024라고 하지 않고 통상 1000이라고..

1. 삽입 정렬 삽입 정렬은 선택 정렬, 버블 정렬과 함께 시간복잡도 $$ O(n^2) $$ 을 가진다. 하지만 삽입 정렬은 선택정렬, 버블 정렬과 같은 시간복잡도를 가지지만, 두 정렬보다는 빠른 속도를 가진다. 그 이유는 선택, 버블 정렬의 경우에는 일일히 원소 값을 비교하는 탐색 과정을 거치지만, 삽입 정렬의 경우, 필요할 때만 위치를 바꾸는 방식을 이용하기 때문이다. 「자바로 배우는 쉬운 자료구조, 한빛 미디어」 책에서는 S(정렬 되어있는 부분집합), U(정렬되지 않은 부분집합)으로 나누어서 U의 원소를 하나씩 꺼내서 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입하는 방식을 이용한다고 설명하지만, 결국 의미는 같다. 음, 그러니까 그냥 필요할 때만 위치를 바꾼다. 라..

1. 완성본 이번 강의에서 만들 완성본 영상입니다. 2. HTML, CSS 이번에는 스케치 없이도 바로 구조가 어떻게되있는지 알 수 있기 때문에 따로 하지 않겠습니다. 그래서 먼저 HTML과 CSS를 이용해서 다음과 같은 메뉴 디자인만 만들어보려고 합니다. 코드는 다음과 같습니다(CSS 헷갈리시는 분들을 위해 약간의 주석을 달아놓았습니다.). HTML Menu Slide Menu 1 Menu 2 Menu 3 Menu 4 Menu 5 Menu 6 CSS // 전체 태그에 box-sizing을 적용합니다. box-sizing에 border 박스를 하면 // 전체 픽셀을 유지한 채로 padding이나 border의 크기만을 늘릴 수 있습니다. // 예를 들면, 가로 300px, 세로, 300px의 블록이 있고..