유료 앱: 플러스 마이너스, 하루하루 인앱 결제: 마이 루틴, 투두 메이트, 하루콩 등 대부분의 앱 리워드 광고: 머니워크, 발로소득 앱 내 광고: 카카오톡, 인아웃

그 중 가장 인상 깊었던 수입 창출 방법과 앱은 어떤 것이 있는지 작성해 보세요.

플러스 마이너스 앱이 가장 인상 깊었습니다. 습관 형성에 도움을 주는 심플한 앱임과 동시에 4400원이라는 다소 비싼 유료 앱 인데도 불구하고 정말 많은 사람들이 구매해서 사용하고 있기 때문입니다. SNS 마케팅, 앱 스토어 키워드 검색 최적화, 깔끔한 스토어 설명 및 미리보기 이미지 등 이렇게 3가지 요인으로 인해 사람들이 자연스럽게 플러스 마이너스 유료 앱을 구매해서 사용하고 있지 않을까 라는 생각이 듭니다.

#라이프해킹스쿨#개인앱으로자동수익만들기#자유로챌린지

스터디 플래너 앱은 아직 개발 중이므로 이전에 출시한 앱의 광고 캠페인과 스크린샷을 찍었습니다.

#라이프해킹스쿨#개인앱으로자동수익만들기#자유로챌린지

이 3가지의 앱 광고가 왜 인상 깊었는지 이유를 작성하세요.

1. 만복이: 광고 디자인이 깔끔하고 직관적임
2. W CLUB: 소개팅 어플 구조상 남성이 먼저 여성에게 연락을 하는데 이 앱의 광고에서는 여성(그것도 마음에 드는 여성)이 먼저 연락함과 동시에 만남까지 보장된다고 하니 남성 입장에서는 앱을 설치하고 싶은 마음이 저절로 생김
3. 광고 중앙에 있는 배터리+베게 모양의 그림이 직관적임. 그리고 요즘 수면이 너무 불규칙적이라 한번 앱을 설치해서 도움을 받고 싶은 마음이 생김

#라이프해킹스쿨#개인앱으로자동수익만들기#자유로챌린지

현재 1인 앱 개발자로 일하고 있고 이미 출시한 앱이 있기 때문에 앱 만드는 것에 있어서는 전혀 어려울 것이 없습니다. 그래서 이전에 기획한 앱 아이디어인 스터디 플래너 앱을 바로 만들 생각입니다. 양쪽 스토어(플레이 스토어와 앱 스토어)에 배포할 예정이고 배포 후 추이를 조금 지켜 본 후 본격적으로 마케팅을 할 생각입니다.

직접 개발할 것인지? / 개발 외주를 맡길 것인지? / 개발자 지인과 함께 협업할 것인지? 이에 대한 의견,계획을 작성해주세요.

직접 개발할 예정입니다. 다만, 마케팅 영역은 아직 잘 모르는 부분이 많기 때문에 주변에 마케터로 일하고 있는 분에게 몇가지 조언을 구할 생각입니다.

#라이프해킹스쿨#개인앱으로자동수익만들기#자유로챌린지

스터디 플래너를 앱으로 만들고 싶습니다. 앱의 주 타켓층은 중고등학생, 재수생, 고시생이며 주요 기능은 과목 추가, 과목 내 할 일 추가, 과목 별 색상 선택, 각 할 일 O/X/△/→ 체크, 타임 테이블, D-Day 기간 설정, 오늘의 메모/공부 사진 추가 등이 있습니다.

강의 중 어떤 방식으로 이 앱의 아이디어를 얻었는지도 작성하세요.

내가 필요한 앱 방식에서 앱의 아이디어를 얻었습니다. 늘 공부를 위해 스터디 플래너를 구매하지만 일주일도 안되어 안쓰게 되는데 이러한 단점을 보완하고 꾸준히 쓸 수 있도록 도와주는 앱이 있으면 좋을 거 같다는 생각이 들어서 해당 아이디어를 기획하게 되었습니다.

#라이프해킹스쿨 #개인앱으로자동수익만들기 #자유로챌린지

Android 또는 IOS 개발자, React 개발자, 처음 프로그래밍을 시작하는 사람들까지 다양한 종류의 사람들이 React-Native 를 사용한다. React-Native 공식 문서는 개발 경험의 수준에 관계없이 모든 학습자를 위해 작성되었다. React-Native 를 사용하기 위해서는 React 의 기본 개념들을 알아야 한다. React 의 기본 개념들을 살펴 볼려면 아래의 문서를 참고하면 된다. #### React-Native 공식 문서 : https://reactnative.dev/docs/getting-started React 기본 개념: https://reactnative.dev/docs/intro-react

또한 React-Native 를 사용하려면 JavaScript 의 기본 개념들을 이해해야 한다. JavaScript 를 처음 접하거나 복습이 필요한 경우 아래의 Mozilla Developer Network 링크를 참고하면 된다. #### JavaScript 공식 문서 : https://developer.mozilla.org/en-US/docs/Web/JavaScript JavaScript 기본 개념: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Language_overview

엉클 박으로 유명한 로버트 C 마틴은 클린 아키텍쳐라는 책에서 다음과 같이 말하였다. “패러다임은 무엇을 해야 할지를 말하기보다 무엇을 해서는 안 되는지 말해준다.” 프로그램은 어떻게 만들던 순차, 분기, 반복, 참조로 구성된다. 이 패러다임은 위 4가지 요소를 어떻게 이용할 것인가를 다룬다. 객체 지향의 경우 객체라는 것을 통해 묶고 객체 간 통신함으로써 프로그래밍이 작동한다. 반면 함수형은 데이터의 함수를 이용해 새로운 데이터로 만들어 나가는 데이터 파이프라인의 형태로 프로그램이 작동한다.

함수형 패러다임

• 객체지향 추상화의 최소 단위가 객체인 것처럼 함수형은 함수가 최소 단위다.

• 그로인해 객체보다 더 작은 단위로 추상화가 되기 때문에 재사용성이 매우 높다.
• 데이터의 불변성을 지향하기에 동작을 예측하기 쉽고 사이드 이펙트를 방지한다. 이러한 장점은 쓰레드 등을 통한 동시성 문제를 해결해준다는 큰 장점으로 이어진다.
• 객체지향은 제어 흐름의 간접적인 전환에 부과되는 규율이다.
• 함수형은 변수 할당에 부과되는 규율이다.

한가지 문제로 패러다임 간 구현 차이를 알아보자. N개의 숫자가 공백없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 출력하는 간단한 문제이다. 먼저 객치 지향의 관점에서 보면 숫자 형태의 문자열을 담고있는 StringNumber 객체가 있고 이 객체는 계산하여 합을 구해주는 역할을 부여 받았다. 그리고 계산한 값은 객체에 저장된다. 값을 출력하는 일은 printer 객체가 담당하게 되고 단순히 StringNumber 객체는 자신의 값을 printer 로 넘기고 출력된다.

절차지향의 관점에서 보면 공유 데이터인 stringNumber 와 sum 변수가 있다. 이를 반복문을 통해 조작해준다. 이 로직은 함수로 만들 수 있다.오히려 이런 간단한 문제에선 절차 지향이 더 편할 수 있다.

마지막으로 함수형 프로그래밍은 데이터를 모두 함수 실행의 연속으로 만들어낸다. 먼저 문자열의 자른 함수, 이어서 정수로 바꿔주는 함수, 각 요소를 함해주는 함수, 마지막으로 출력해주는 함수, 이렇게 함수들을 조합하여 결과를 도출한다.

함수형 프로그래밍의 장점

크게 3가지가 있다.

• 상태가 없기 때문에 사이드 이펙트가 존재하지 않는다.
• 함수 단위로 나눠지기 때문에 재사용성이 높다.
• 함수의 조합을 통해 코드가 짧고 간결해질 수 있다.

선언형 프로그래밍

함수형 프로그래밍은 선언형 프로그래밍과 가깝다. 선언형 프로그래밍은 객체지향이나 함수형처럼 설계에 대한 패러다임이라기 보단 사고에 대한 패러다임이라 할 수 있다.

• 기존 명령형 프로그래밍은 문제를 어떻게 해결해야 하는지 컴퓨터에게 명령을 내리는 방법이다.
• 선언형 프로그래밍은 무엇을 해결해야 할지에 집중하고 선언형 프로그래밍은 무엇을 해결해야 할지에 집중하고 해결 방법은 컴퓨터에게 위임하는 방법이다. 선언형 프로그래밍을 통해 문제를 쪼개어 분석할 때, 함수형 프로그래밍이 빛을 발한다. 기존 명령형 프로그래밍은 Contorl Flow 방식으로 if/switch/for 등을 통해 데이터를 제어하였다. 반면 Data Flow 는 상태가 존재하지 않고 재귀나 pipe 를 통해 데이터가 흘러간다. 따라서 Data Flow 방식으로 코드를 작성하면 데이터의 제어없이 필요한 함수만 조합하여 해결이 가능해진다.

브라우저에 URL 을 입력하면 무슨 일이 발생할까? 예를 들어 브라우저 주소 창에 프로그래머스 URL 을 입력하면 잠깐의 로딩 뒤에 프로그래머스 웹 사이트가 보이게 된다. 잠깐의 로딩 사이에 도대체 어떤 일이 발생하길래 웹 사이트가 보이게 되는 걸까? 지금부터 그 과정을 단계별로 확인해보자.

Step1. URL 을 해석한다.

scheme://user:password@host:port/url-path 여기서 scheme 는 프로토콜이 들어가는 영역이다. 
그리고 인증이 요구 되는 경우 id 와 password 를 입력하면 접속 허가를 받을 수 있다.
참고로 이 URL 은 // 두개를 생략해도 괜찮다.

예시

• http://example.com:8761/members
• ftp://admin:1q2w3e4r@example.com/image.png
• mailto:kciter@naver.com
• http:programmers.co.kr

Step2. DNS 를 조회한다.

DNS 는 Domain Name System 의 약자로, 도메인과 IP 주소를 서로 변환해주는 시스템이다. 브라우저는 DNS 를 요청을 보내기 전에 몇가지 체크를 한다. 먼저 해당 도메인을 알고 있는지 찾아보고 없다면 로컬 컴퓨터의 hosts 파일을 참조한다. 만약 정의가 되어 있다면 내부적으로 IP 를 반환한다. 둘다 해당이 안된다면 DNS 를 호출한다. DNS 서버는 Root Server -> TLD Server -> Authoritative Server 순으로 탐색한다. 참고로 도메인과 호스트를 착각할 때가 많다. present.do, www.present.do, gateway.dev.present.do 전부 도메인은 present.do 이고 나머지 서브 도메인이 붙은 경우는 host 라고 부른다.

Step3. 해당 IP가 존재하는 서버로 이동한다.

정확히는 해당 IP가 할당된 서버가 존재하는 대역으로 이동한다. 예를 들어, 한국에서 미국에 있는 서버를 요청 했다면 네트워크 장비인 라우터를 통해 여러번 거친 후, 해당 서버가 존재하는 대역으로 접근하게 된다.

Step4. ARP 를 이용하여 MAC 주소를 변환해야 한다.

ARP 는 Address Resolution Protocol 의 약자이다. 논리 주소인 IP 주소를 물리 주소인 MAC 주소로 변환하는 프로토콜이다. 네트워크 망 내에 ARP 를 Broadcasting 하면 해당 IP 주소를 가지고 있는 기기가 MAC 주소를 반환한다.

Step4-1. IP 주소와 MAC 주소

IP 는 논리적인 주소이고 MAC 은 물리적인 주소이다. 기계의 실제 위치를 알기 위해선 MAC 주소가 필요하다. 여기서 IP 주소로만 하면 되는 것을 왜 논리적 주소와 물리적 주소로 나눈걸까? 왜냐하면 사용 용도가 달라서 그렇다.

Step4-2. 경북궁의 주소는?

예시를 통해 알아보자. 경북궁의 주소는 도로명 주소로 “서울 종로구 사직로 161”, 지번 주소로는 “서울 종로구 세종로 1-91” 이다. 그런데 우리가 이것만 보고 어디에 있는지 알 수 있을까? 만약 도로명, 지번 주소 체계가 변경 된다면 어떻게 될까? 답은 실제 위치를 알 수 없다. 따라서 실제 위치를 알기 위해서는 정확한 GPS 좌표가 필요하다. 비유하자면 도로명 주소나 지번 주소는 논리적 주소인 IP 주소에 비유할 수 있다. GPS 좌표는 물리적 좌표인 MAC 주소에 비유 할 수 있다.

Step4-3. 경북궁으로 택배를 보낸다면?

여기서 끝이 아니다. 만약 경북궁으로 택배를 보낸다면 어떻게 해야 할까? 우리가 배달을 한다 생각하면 먼저 논리적 주소를 보고 범위를 좁혀 나갈 것이다. 경북궁 같은 경우 먼저 서울로 접근하고 다음 종로구, 세종로를 탐색한다. 그럼 탐색 순서가 서울의 진짜 위치를 찾게 되고 종로구의 진짜 위치, 세종로의 진짜 위치를 찾게 될 것이다. 마치 ARP 를 이용 했던 것과 비슷하다. 이처럼 IP 는 대역을 통해 범위를 좁혀 나가는 용도로 사용이 된다. 따라서 경북궁으로 택배를 보낸다면 중간 거점을 거칠 수 있다. 아래의 그림을 보면 옥천 Hub 나 군포 Hub 같은 것을 라우터라고 비유 한다면 비슷하게 각 Hub 의 진짜 위치를 찾아내어 이동 한다. 그리고 마지막으로 도착지에 배달을 하게 된다.

Step5. TCP 통신을 통해 서버의 Socket 을 열어야 한다.

실제 Socket 을 열어서 허락을 받아야만 데이터를 전달할 수 있다. 이때, TCP 연결을 허락 받기 위해 3 way handshake 가 실행된다. 다시 택배에 비유하자면 우리가 물건을 전달하기 위해 초인종을 눌러 허락을 받는 것이라 볼 수 있다. 만약 거절 당한다면 물건을 전달 할 수 없다. 여기서 요청이 수락되면 데이터를 서버로 전달하게 된다.

Step6. 서버는 요청에 따라 응답을 반환한다.

HTTP 프로토콜로 들어온 패킷을 읽고 처리한다. 요청에 따른 적절한 응답 값을 반환한다.

Step7. 브라우저는 받은 HTML 을 읽어 랜더링을 한다.

HTML 을 읽어 DOM Tree 를 구축한다. 만들어진 DOM Tree 를 이용하여 화면에 그린다. 만약 여기서 스크립트가 있다면 스크립트까지 실행하게 된다. 여기까지 진행 했다면 우리는 최종적으로 페이지를 볼 수 있게 된다. 이렇게 복잡한 과정이지만 이 과정이 아무리 길어봐야 초 단위를 벗어나지 않는다.

유효 범위라고 부르며 변수가 어느 범위까지 참조되는지를 뜻한다. 어디서든 접근 가능한 전역 스코프(Global Scope)가 있고 해당 컨텍스트 내에서만 접근 가능한 지역 스코프(Local Scope)로 나뉜다. 다만, 여기서 var 사용하면 안되는 이유가 나온다. 아래의 그림처럼 var 를 사용하면 개발자가 예상치 못한 오류를 만들 수 있다. var 를 사용하면 호이스팅 되어 변수 선언이 함수 상단으로 올라가 버린다. 그래서 블록 내부에 새롭게 선언하더라도 블록 외부 변수 값도 같이 변하게 된다. 이런 차이가 발생하는 이유는 var 는 함수 레벨의 스코프이고 const 와 let 은 블록 레벨의 스코프이기 때문이다. 따라서 var 를 사용하는 경우 개발자가 오류를 찾기 힘들어지기 때문에 가급적 사용하지 않는 것이 좋다.

클로저란?

함수가 선언된 환경의 스코프를 기억하여 함수가 스코프 밖에서 실행될 때에도 기억한 스코프에 접근할 수 있게 만드는 문법이다. 아래의 코드를 보면 함수 내부에 있는 greeting 변수는 함수가 종료된 시점에 사용이 불가능해진다. 왜냐하면 블록 스코프이기 때문에 함수가 종료되면 메모리에서 사라지기 때문이다. 하지만 makeGreeting 함수를 통해 반환된 함수를 사용해보면 greeting 변수에 접근이 가능한 것을 확인할 수가 있다. 이는 반환된 함수가 Greeting 변수를 계속 참조하고 있어 메모리에서 사라지지 않기 때문이다. 이처럼 클로저는 닫힘, 패쇄라는 뜻을 가지고 있는데 더 이상 외부에서 접근이 불가능한 영역을 클로저를 통해서 접근하는 모습이 패쇄된 모습과 유사하다고 볼 수 있다. 이런 클로저를 유용하게 사용할 수 있는 방법은 은닉화이다. 클로저를 이용하면 내부 변수와 함수를 숨길 수 있다. 아래 코드의 Counter 함수를 보면 변수와 내부 함수는 외부에서 접근이 불가능하다. 따라서 반환된 함수들로만 값을 조작할 수 있게 된다. 이런 식으로 내부 변수와 함수를 숨기면서 개발자의 실수를 줄일 수 있다.

클로저의 중요성

클로저를 잘 알아야 하는 이유는 유용하게 사용하기 보단 알기 힘든 버그를 잘 수정하기 위해서이다. 예를 들어, 아래의 그림에서 보이는 출력 결과는 어떻게 될까? 출력 결과는 55555 이다. setTimeout 의 대기 시간이 끝나 콜백 함수가 실행되는 시점에는 이미 루프가 종료되어 i 가 5가 되었기 때문이다. 이런 문제를 해결할 수 있는 방법은 IIFE 를 이용하거나 let을 이용하는 방법이다. let 은 블룩 수준 스코프기 때문에 매 루프마다 클로저가 생성된다.

흐름 제어는 크게 두가지 방식으로 나뉠 수 있다. 여기선 Control Flow 라는 방식을 알아보자. Control Flow 는 우리가 흐름을 제어하는 방법 중 하나로 조건이나 반복을 통해 상태를 제어하는 것을 의미한다. 코딩을 처음 다룰 때 if 와 for 등의 반복을 이용할 수 있다. 아까 흐름 제어는 두 가지 방법이 있다고 했었다. Control Flow 와 Data Flow 가 있다. 우리가 일반적으로 알고 있는 조건문이나 반복문은 Control Flow 에 속한다. 반면 Data Flow 는 함수형 프로그래밍 방식으로 구현이 가능하다.

if, switch 조건문

if 조건문

먼저 조건문이란 조건이 맞을 때만 실행되는 문장(Statements)문법이다. 예를 들어, 이선협이라는 객체가 “몸무게가 80이 넘는가?” 라는 조건이 있을 때 조건이 참이라면 “운동 가자”로 빠지고 조건이 거짓이라면 “치킨 먹자”로 빠지게 된다. 이런 조건문은 자바스크립트 문장 문법인 if 를 통해 사용할 수 있다. if 는 괄호 안 조건식이 참인 경우에 실행되는 문법이다. 다른 언어처럼 else if, else 도 같이 사용할 수 있다. 여기서 주의해야 할 점이 한가지 있다. if 안쪽 조건이 false 가 아니더라도 아래의 값들도 거짓이 될 수 있으니 주의 해야한다 (false, undefined, null, 0, NaN, ‘’). 이런 값들을 Falsy 라고 하여 조건에서 거짓으로 평가되는 값을 통칭하고 있다. 반대로 Falsy 를 제외한 모든 값은 Truthy 라 하여 참으로 평가하게 된다. 훗날 이 오류를 보고 헤맬 수도 있으니 꼭 기억해두는 것이 좋다.

switch 조건문

조건문을 이용하는 방법으로 if 대신 switch 를 이용할 수 있다. switch 는 괄호 안 값에 따라 분기되는 문법으로 case, default 와 함께 쓰인다.여기서 주의 할 점으로 case 안 마지막에 break 를 적어주지 않으면 다음 case 가 실행 된다는 점이다.

for, while 반복문

반복문은 이름 그대로 반복적인 작업을 지시하는 문법이다. 그 중 for 문법은 가장 기초적인 반복문으로 초기문, 조건문, 증감문으로 이루어져 있다. 조건문의 결과가 거짓이 되면 반복이 종료된다. 다른 문법으로 while 이 존재한다. while 은 for 와 다르게 괄호 안에 조건만이 들어갈 수 있고 조건이 거짓이 될 때 까지 반복된다. while 의 파생으로 do while 문법이 있다. while 문과 다르게 먼저 진입 후 로직을 실행한 다음 조건을 검사한다.

일반적으로 웹사이트는 여러 개의 자바스크립트로 이루어져 있다. 대부분 스크립트 언어의 특징이지만 자바스크립트는 파일들이 각각의 별개의 프로그램으로 취급을 하고 있다. 그럼 자바스크립트 프로그램은 무엇으로 이루어져 있을까? 표현식과 문장 두가지 카테고리로 이루어져 있다. 표현식이란 어떠한 결과 값으로 평가되는 식을 의미한다. 즉, 결과가 계산되는 식을 의미한다. 표현식은 숫자와 문자열, 논리값과 같은 원시 값을 포함하여 변수나 상수, 함수 호출 등으로 조합 될 수 있다. 이러한 표현식은 연산자를 통해 조합되어 새로운 표현식을 만들어 낼 수 있다.

할당 연산자와 복합 할당 연산자

그 중에서 할당 연산자는 오른쪽 표현식을 왼쪽 피연산자 값에 할당하는 연산자이다. 등호(=)를 사용하며 다른 연산자와 같이 사용하여 복합 할당 연산자로 이용할 수 있다.

비교 연산자

좌측 피연산자와 우측 피연산자를 비교하는 연산자이다. 결과 값으로 true 혹은 false 로 반환 할 수 있다.

산술 연산자

덧셈, 뺄셈, 곱셈, 나눗셈을 하는 연산자이다. 결과 값으로 Number 를 반환한다.

비트 연산자

비트를 직접 조작하는 연산자이며, 아래의 그림처럼 이진법으로 나타냈을 때 각 비트를 조작하는 연산자이다. 일반적으로 자주 쓰이는 연산자는 아니지만 추후 코딩 테스트 문제를 풀 때 가끔 사용되는 경우가 있다.

논리 연산자

Boolean 을 통해 참과 거짓을 검증하는 연산자이다. 조건문이나 반복문에서 자주 쓰이는 연산자이다.

삼항 연산자

조건에 따라 값을 선택하는 특수한 연산자이다. ‘조건 ? 참 : 거짓’ 형태를 가지며 편의를 위해 조건문 대신 쓰일 때가 많다.

관계 연산자

객체에 속성이 있는지 확인하기 위한 연산자이다. 예를 들어 아래의 그림처럼 변수 x 에 “name” 이란 값이 있는지 체크하는데 사용할 수 있다.

typeof

피연산자의 타입을 반환하는 연산자이다. 문자열로 반환되고 이를 이용하여 변수의 타입을 알 수가 있다.

변수를 선언할 때 자바스크립트 내부에선 어떤 일이 발생할까? 이 코드가 실행될 때 자바스크립트는 변수의 고유 식별자를 생성하고 메모리에 주소를 할당한다. 최종적으로 생성한 주소에 값을 넣게 된다. 이 과정을 시각화하면 아래의 그림과 같다. 우리가 선언한 변수나 상수는 값을 바라보고 있는 것이 아닌 메모리 주소를 바라보고 있다. 만약 여기서 새로운 변수에 기존 변수를 대입하면 어떻게 될까? 답은 간단하다. 기존 변수의 메모리 주소를 참조하게 된다. 여기서 한가지만 더해보자. 만약 기존 변수를 조작하면 어떻게 될까? 두번째 생성한 변수의 값도 변하게 될까? 이번에는 그렇지 않다. 새로운 메모리 주소를 할당 받고 그것에 값을 넣게 된다. 그 이유는 자바스크립트에서 원시 타입은 변경이 불가능하기 때문이다. 따라서 원시 타입의 값이 변경 될 때는 항상 메모리가 할당된다.

자바스크립트 엔진

자바스크립트 엔진은 가상 머신(Virtual Machine)으로 구성 되어 있다. 이 가상 머신에는 메모리 모델을 구현해놓았는데 각각 Heap 영역과 Call Stack 영역으로 구성 되어 있다. Heap 은 참조 타입이 들어가고 Call Stack 은 원시 타입이 들어가게 된다. 방금 전에 위의 과정을 Call Stack 으로 표현하면 스택처럼 하나씩 쌓이게 된다. 아래의 그림에서 만약 좌측에 있는 코드를 실행 시키게 되면 어떻게 될까? 먼저 순차적으로 Call Stack 에 변수들이 쌓이게 된다. 배열 같은 경우 오브젝트 타입이기 때문에 참조 타입으로 분류 된다. 배열을 선언하면 Heap 에 배열 영역이 생성 되는데 Call Stack 에 생성된 배열 변수는 Heap 에서 생성된 배열의 메모리 주소를 참조하게 된다. 여기서 Heap 영역 메모리는 동적으로 크기가 변할 수 있다. 따라서 배열의 값을 추가하면 Heap 메모리 영역에 그대로 할당이 된다. 배열을 상수로 선언 했는데 동작하는 이유이기도 하다. 상수여도 push 함수가 동작하는 이유는 Call Stack 에 할당된 메모리를 변경 하는 것이 아닌 Heap 메모리를 변경 하는 것이기 때문이다. 위의 그림처럼 이제 모든 로직이 종료 되었다. 그런데 여기서 사용을 마친 메모리는 어떻게 정리가 될까?

가비지 컬렉터

자바스크립트 엔진은 가비지 컬렉터(Garbage Collector)라는 것을 통해 메모리를 정리한다. 가비지 컬렉터는 사용하지 않는 메모리를 해제하는 역할을 맡고 있다. 앞서 사용된 메모리 주소도 가비지 컬렉터에 의해 정리 될 수가 있다. 이때, 현대적인 브라우저의 가비지 컬렉터는 Mark and Sweep Algorithm 을 통해 메모리를 정리 하고 있다. 브라우저의 최상위 객체인 window 에서부터 시작하여 닿을 수 없는 곳은 필요 없는 주소라 생각하여 지우는 알고리즘이다. 아래의 그림을 보면 window 로부터 아래로 뻗어 나가는데 가장 왼쪽 string 은 닿지가 않는다. 이런 경우는 메모리에서 삭제가 된다.

메모리 정리

다시 처음 상황으로 되돌아가보자. 만약 또 다시 값을 할당하여 첫번째 메모리 값을 아무도 참조하지 않는다면 어떻게 될까? 가비지 컬렉터에 의해 조용히 사리지게 된다. 이처럼 메모리가 지워지게 되는 것은 참조가 중요하다. 참고로 클로저가 가능한 이유도 참조 덕분이라고 할 수 있다.

자판기는 남은 금액을 어떤 알고리즘을 반환할까? 그리고 마시멜로 실험에서 마시멜로가 하나 있고 30분을 참으면 마시멜로를 하나 더 준다고 가정할 때 아이들은 어떤 선택을 하는 것인가를 테스트 하는 실험이다. 그리디 알고리즘은 매 선택에서 지금 이순간 최적인 답만을 선택하는 알고리즘이다. 최적해를 보장해주지 않는다. 아래의 그림을 보면 먼저 A 부터 갈수 있는 정점은 B와 D가 있다. A가 볼 때는 B가 더 짧기 때문에 B를 선택한다. 이어서 C, F 로 이동하여 총 이동 거리는 65 가 된다. 하지만 실제 최적해는 D를 선택했을 때이다. D를 선택하면 총 이동거리가 33이 된다.

그리디 알고리즘의 특징

• 보통 최적해를 구하는 알고리즘보다 훨씬 빠른 경우가 많다. 특징상 되게 선형 시간만에 끝나는 경우가 많다.

• 크루스칼, 다익스트라 알고리즘 등에 사용된다.
• 직관적인 문제 풀이에 적합하다.

위의 자판기 반환 문제를 어떻게 해결하면 좋을까? 지불 금액은 5000원, 요금은 3140원일 때 거스름 돈은 1860원이다. 여기서 편의를 위해 거스름돈은 큰 단위부터 거슬러 줘야 할 때 어떻게 해야 할까? 답은 매우 간단하다. 거스름돈 1860원을 가장 큰 단위부터 처리하면 된다. 먼저 1000원 반환이 가능하기 때문에 거스름돈에서 1000원을 뺀다. 나머지 860원에서 1000원을 거슬러 줄 수 없기 때문에 다음으로 큰 단위인 500원을 반환한다. 그럼 남은 거스름돈은 360원이 된다. 다음으로 큰 단위인 100원을 세번 반환하면 남은 거스름돈은 60원이 된다. 이런 방식으로 각각 50원과 10원을 반환하면 최대한 적은 횟수로 거스름돈을 줄 수 있게 된다.

그리디 문제 풀이

그리디 알고리즘은 대게 동전 반환 문제와 같이 진행되는 경우가 많다. 참고로 여기서 착각하면 안되는 점은 그리디는 특정 구현 방법이 존재하는 것이 아닌 하나의 개념으로 봐야 한다는 점이다. 따라서 그리디 알고리즘은 문제를 풀면서 이해하는 것이 가장 좋다.

이 알고리즘은 각각 넓이 우선 탐색(Breadth-First-Search)과 깊이 우선 탐색(Depth-First-Search)이라고 부른다. 그림판의 페인트 툴은 어떻게 구현 될까? 그리고 만약 D에서 G로 가는 최단 거리는 어떻게 알 수 있을까? 넓이 우선 탐색과 깊이 우선 탐색을 이용하면 구현할 수 있다.

너비 우선 탐색(BFS)

그래프 탐색 알고리즘 중 하나로 같은 깊이에 해당하는 정점부터 탐색해나가는 알고리즘이다. 아래의 그림 예시를 보면 A 부터 시작하여 점점 퍼져나가도록 시각화 하였다. 먼저 A를 탐색하고 이어서 B, C, D 를 탐색한 후 그 다음 단계인 E, F 마지막으로 G를 탐색한 것으로 표현한 것이다.

BFS 의 특징

• Queue 를 이용하여 구현할 수 있다.
• 시작 지점에서 가까운 정점부터 탐색한다.
• V 가 정점의 수, E 가 간선의 수일 때 BFS 의 시간복잡도는 O(V + E)다.

동작 순서는 아래와 같다. 먼저 시작 지점을 A 라고 가정할 때, 큐에 A 를 넣는다. 큐에 있던 A 를 디큐(Dequeue)하고 A 로부터 이동할 수 있는 간선의 수를 체크하여 해당 정점들을 모두 큐에 넣는다. 다음은 B 정점을 디큐하여 B 로 부터 이동 가능한 정점을 큐에 넣는다. 이때 C는 이미 방문한 곳이기 때문에 추가 하지 않는다. 다음은 C 정점을 디큐한다. C 정점에선 F로 갈 수는 있지만 이미 큐에 추가가 되었기 때문에 아무것도 하지 않고 종료한다. 다음으로 D 를 디큐한 후 D 와 연결된 E 정점을 큐에 추가한다. 다음으로 F 정점을 디큐한 후에 F 와 연결된 G 정점을 추가한다. E 정점은 더 이상 갈 수 있는 정점이 없기 때문에 디큐만 하고 종료한다. 마찬가지로 G 정점도 더 이상 갈 수 있는 정점이 없기 때문에 그대로 종료된다. 보시다시피 BFS 는 시작 지점에서 인접한 요소부터 탐색하며 진행된다.

깊이 우선 탐색(DFS)

그래프 탐색 알고리즘 중 하나로 최대한 깊은 정점부터 탐색하는 알고리즘이다. 예시를 살펴보면 아래와 같다. 탐색 우선 순위가 더 작은 알파벳이 우선이라 가정할 때, 아래의 그림을 보면 A 정점부터 시작하여 B, F, C 로 이동한 것을 볼 수 있다. C 에서 더 이상 방문할 곳이 없어 F에서 G 로 이동한다. G에선 더 이상 이동할 간선이 없기 때문에 그대로 다시 A까지 빠진다. 이어서 D 를 탐색하고 E 를 탐색하면 깊이 우선 탐색이 마무리된다.

DFS 의 특징

• Stack 자료구조를 이용하여 구현 할 수 있다.
• 시작 정점에서 깊은 것 부터 찾는다.
• V 가 정점의 수, E 가 간선의 수일 때 BFS 의 시간 복잡도는 O(V+E)다.

동작 순서는 아래와 같다. 이번에도 A부터 시작할 것이기 때문에 스택에 A를 넣는다. 스택의 탑인 A 를 참고하여 이동할 수 있는 정점인 B 를 스택에 추가한다. 이어서 스택의 탑인 B 에서 이동할 수 있는 정점인 F 를 추가한다. 또 이어서 스택의 탑인 F 에서 갈 수 있는 정점인 C 를 스택에 추가한다. C 에서는 더 이상 갈 수 있는 곳이 없기 때문에 Pop 하고 다시 F 에서 갈 수 있는 정점인 G 를 스택에 추가한다. G 에서는 더 이상 갈 수 있는 곳이 없기 때문에 그대로 Pop 한다. 나머지 F 와 B 도 더 이상 갈 수 있는 곳이 없어 스택은 A 까지 모든 요소가 Pop 된다. 다시 A 부터 시작되어 D 를 스택에 추가한다. 이이서 E 를 추가한다. 그리고 E 에서 더 이상 갈 수 있는 곳이 없기 때문에 모든 정점을 스택에서 Pop 하게 된다. 이런식으로 DFS 는 깊은 정점부터 탐색하게 된다.

만약에 우리가 구슬들을 크기별로 나열해야 한다면 어떻게 하면 될까? 제일 큰 것부터 찾을 수도 있고 일단 분류해서 정리하는 경우도 있을 것이다. 이러한 행동을 우리는 정렬이라고 부른다. 정렬은 앞서 살펴본 것처럼 요소들을 일정한 순서대로 열거하는 알고리즘이다. 정렬 알고리즘은 우리가 실제로 순서를 정리할 때 사고하는 절차와 거의 유사하다.

정렬의 특징

• 정렬 기준은 사용자가 정할 수 있다. 무슨 값을 기준으로 할 지 오름차순일지 내림차순일지 정할 수 있다.

• 크게 비교식 정렬과 분산식 정렬로 나눌 수 있다.
• 대부분의 언어가 빌트인으로 제공 해주기 때문에 편리하게 사용할 수 있다.
• 정렬 방식은 다양하다. 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등의 정렬이 있다. 여기서 말한 정렬 외에도 기수 정렬, 팀 정렬, 스파게티 정렬도 있다.

정렬 알고리즘 중 어떤 것이 제일 빠를까? 퀵 정렬이나 머지 정렬이 제일 빠를 것이라 예상할 수 있다. 하지만 정렬들은 각각 유리한 상황과 불리한 상황이 있기 때문에 무엇이 더 좋고 나쁜지 정해져 있지는 않다.

버블 정렬

다른 요소와 비교를 통해 정렬하는 방식을 말한다. 버블 정렬은 비교식 정렬 중에 하나로 서로 인접한 두 요소를 검사하여 정렬하느 알고리즘이다. 시간 복잡도는 O(n제곱)이 걸린다. 동작 순서는 아래와 같다. 먼저 정렬되지 않은 배열을 보고 이 배열을 오름차순으로 배열해보자.

1. 첫번째 요소에서 인접한 요소를 검사한다. 7보다 4가 더 작기 때문에 오름차순에 따라 두 요소를 교환한다.
2. 교환 후 두번째 요소와 세번째 요소를 비교한다. 7보다 5가 더 작기 때문에 교환한다.
3. 교환 후 이어서 세번째 요소와 네번째 요소를 비교한다. 7보다 1이 작기 때문에 교환한다.
4. 마지막으로 네번째 요소와 다섯번째 요소를 비교한다. 7보다 3이 작기 때문에 교환한다. 이렇게 하면 첫번째 순회가 완료된다. 이제 두번째 순회를 진행한다.

1. 첫번째 요소와 두번째 요소를 비교한다. 4가 5보다 작기 때문에 교환하지 않는다.
2. 두번째 요쇼와 세번째 요소를 비교한다. 5가 1보다 크기 때문에 교환한다.
3. 마지막으로 세번째 요소와 네번째 요소를 비교한다. 이어서 세번째 순회를 진행한다.
4. 첫번째와 두번째 요소를 비교한다. 1이 더 작기 때문에 교환한다.
5. 두번째 요소와 세번째 요소를 비교한다. 4가 더 크기 때문에 교환한다. 이렇게 세번째 순회도 마무리 된다. 마지막 순회를 진행한다.
6. 1과 3을 비교한 다음에 교환하지 않고 순회가 마무리 된다. 결국 버블 정렬은 (n - 1)번 순회하면 정렬이 마무리 된다.

선택 정렬

선택 정렬은 사람이 이해하기에 제일 단순한 정렬이라고 볼 수 있다. 선택한 요소와 나머지 요소 중 가장 우선순위가 높은 요소를 정렬 알고리즘이다. 선택 정렬도 마찬가지로 이차 시간 O(n 제곱) 시간복잡도를 가진다. 동작 순서는 아래와 같다.

1. 먼저 선택된 첫번째 요소와 나머지 요소 중 가장 우선 순위가 높은 1과 교환한다.
2. 그 다음 두번째 요소와 나머지 요소 중 가장 우선 순위가 높은 3과 교환한다.이렇게 되면 두개의 요소가 정렬된다.
3. 세번째 요소와 나머지 요소 중 가장 우선 순위가 높은 요소와 교환한다. 세개의 요소가 정렬 되었다.
4. 마지막으로 남은 두 요소를 비교한 후 교환한다. 선택 정렬은 이처럼 간단하다. 참고로 나머지 요소 중 선택된 요소보다 우선 순위가 높은 요소가 없다면 교환을 하지 않고 넘어가면 된다.

삽입 정렬

선택한 요소를 삽입 할 수 있는 위치를 찾아서 삽입하는 방식의 정렬 알고리즘이다. 이차시간 O(n제곱) 시간복잡도를 가진다. 다른 정렬보다 구현하는데 있어서 조금 더 복잡하다.

1. 삽입 정렬은 특이하게 두번째 요소부터 시작한다. 4를 선택하여 7과 비교한다. 7이 더 크기 때문에 7을 밀어내고 4가 삽입된다.
2. 7은 4보다 크기 때문에 생략한다.
3. 세번째 요소인 5를 선택한다. 5와 7을 비교해서 7이 더 크기 때문에 7을 밀어낸다.
4. 다음으로 4와 비교한다. 4가 더 작기 때문에 밀어내지 못하고 그대로 5가 두번째 삽입 되면서 종료된다.
5. 이번엔 4번째 요소인 1을 선택한다. 7은 1보다 크기 때문에 밀려난다. 다음으로 5와 비교한 후 또 밀려난다. 4도 밀려나고 제일 첫번째로 1이 삽입된다.
6. 마지막 순회로 다섯 번째 요소 3이 선택된다. 7과 비교 후에 밀어내고 5와 비교 후에 밀어내고 4와 비교 후 밀어낸다. 마지막으로 1과 비교 했을 때 더 이상 밀어낼 수 없으므로 그대로 두번째에 삽입이 된다. 삽입 정렬은 이렇게 복잡하지만 어느 정도 정렬이 되어 있다는 가정하에서는 퀵 정렬보다도 빠른 성능을 보여준다.

분할 정복

문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능 할 때 처리한 후 문제를 합치는 전략이다. 꼭 분산식 전략이 아니더라도 분할 정복은 다양한 알고리즘에 응용되는 전략이니 기억에 두면 좋다.

합병 정렬

분할 정복 알고리즘을 이용한 가장 정직한 알고리즘이라 할 수 있다. 정직하게 요소를 이분하여 계산하기 때문에 최악과 최선이 항상 선형 로그 시간 O(n log n) 이 걸리는 안정적인 정렬 알고리즘이다. 합병 정렬은 우선 요소들을 나누는 작업부터 시작한다. 아래의 그림처럼 우선 8개 요소를 절반으로 나눈다. 그리고 요소가 하나만 남을 때까지 계속해서 절반으로 나눈다. 모든 요소를 나눴다면 합치는 알고리즘이 진행된다. 나눈 것을 합치면 두 요소 중 작은 것을 먼저 배치한다. 예를 들어, 21 과 10 의 경우 10이 먼저 배치되고 21이 배치된다. 이어서 두개 짜리를 합칠 때도 작은 순으로 배치한다. 이 작업들은 선형 시간이 소요된다. 최종적으로 나머지를 합치면 정렬된 상태가 된다. 선형 시간이 O(log n) 만큼 걸려서 O(n log n) 시간 복잡도가 소요된다.

퀵 정렬

퀵 이라는 이름이 붙을 정도로 평균적으로 빠른 성능을 보여준다. 하지만 특정 경우엔 이차 시간이 걸리는 최악의 경우가 존재한다. 그래서 퀵 정렬은 불안정 정렬이라고 부른다. 시간 복잡도는 합병 정렬과 같은 선형 로그 시간이다. 퀵 정렬은 피벗이라는 기준으로 좌측과 우측을 나눈다. 여기서는 첫번째 요소인 5를 피벗이라 치고 진행하면 5를 기준으로 작은 값을 왼쪽에 배치, 큰 값이 오른쪽에 배치된다. 그리고 다시 나눈 배열에서 첫번째 요소가 피벗이 된다. 각각 1과 9인데 이 숫자를 기준으로 나뉜다. 이번엔 전부 큰 값과 작은 값으로 나뉠 수 있다. 다시 첫번째 요소들이 피벗이 된다. 이렇게 마지막으로 더 이상 나눌 수 없는 상태가 되었다면 그대로 합쳐준다. 그럼 요소들이 정렬된 상태로 나열된다.

정리가 안된 책장에서 원하는 책을 찾을려면 어떻게 하면 좋을까? 사람마다 다르겠지만 어느 방향이든 순차적으로 찾는 사람이 많을 것이다. 이러한 탐색을 선형 탐색이라고 부른다. 순서대로 하나씩 찾는 탐색 알고리즘이기 때문에 O(n) 시간복잡도가 걸린다. 그리고 up and down 게임에 대해서 아는가? 흔히 나이 맞추기 게임을 할 때 많이 사용하는 게임이다. 예상 나이를 말하고 더 큰지 더 작은지를 판단하여 절반씩 줄여나가는 전략을 많이 사용한다. 이런 전략을 이용한 탐색을 이진 탐색이라고 부른다. 이진 탐색은 요소들이 이미 정렬이 되어야 사용할 수 있는 알고리즘이다. 즉, 정렬 되어있는 요소들을 반씩 제외하며 타겟 요소를 찾는 알고리즘이므로 O(log n)만큼 시간복잡도가 걸린다.

이진 탐색의 특징

• 반드시 정렬이 되어 있어야 사용할 수 있다. 따라서 정렬로 탐색하면 선형 탐색보다 느릴 수 있다.

• 배열 혹은 이진 트리를 이용하여 구현할 수 있다.
• O(log n) 시간복잡도인 만큼 상당히 빠르다. 정렬이 되어 있다면 가급적 이진 탐색을 이용하는 것이 좋다. 이렇게 빠른 알고리즘은 거의 없다.

배열을 이용한 구현 방법

아래의 배열에서 45를 찾으려면 어떻게 하면 될까? 이진 탐색에서는 먼저 시작 지점을 Left 로 두고 끝 지점을 Right 로 둔다. 그리고 중간 지점을 Mid 라고 표현한다. 여기서 mid 와 찾을 값인 45와 비교한다. 58 보다 45 가 작기 때문에 right 값을 한칸 왼쪽에 위치한 후 다시 Mid 값을 구한다. 이번엔 36이 45보다 작기 때문에 Left가 36에 오른쪽으로 이동한다. 마침 Left 와 right 가 동일하기 때문에 Mid 도 동일한 값으로 다시 부여된다. 이번엔 Mid 값과 찾을 45 값이 같기 때문에 탐색이 종료된다. 배열을 이용한 방법은 중간에 요소를 추가하거나 삭제하는 경우에는 선형 시간이 걸린다는 단점을 여전히 들고 있다. 그래서 이 방법을 해소하기 위해 이진 탐색 트리를 이용할 수 있다.

이진 탐색 트리를 이용한 구현 방법

이진 탐색 트리

이진 트리에서 한가지 규칙을 추가한 자료구조이다. 이진 트리에서 왼쪽 서브 트리는 루트보다 작은 값이 모여있고 오른쪽 서브 트리는 루트보다 큰 값이 모여있도록 구성되어 있는 트리이다.

이진 탐색 트리 요소 추가

1. 먼저 5를 추가하면 root 가 5가 된다.
2. 다음으로 4를 추가한다. 4는 root 인 5보다 작기 때문에 왼쪽 정점에 위치한다.
3. 다음으로 7을 추가한다. 7은 root 인 5보다 크기 때문에 오른쪽 정점에 위치한다.
4. 다음으로 8을 추가한다. 8은 root 인 5보다 크기 때문에 오른쪽 정점으로 이동하고 서브트리인 root 인 7 보다 크기 때문에 7의 오른쪽 정점에 위치한다.
5. 이번엔 root 와 동일한 값인 5를 추가한다. 동일한 경우 왼쪽 또는 오른쪽 아무곳에 넣어도 상관 없지만 여기선 왼쪽 정점에 넣어보자. 4보다는 크기 때문에 4의 오른쪽 정점에 추가된다.
6. 이번엔 6을 추가해보자. 6은 5보다 크고 7 보다 작기 때문에 7의 왼쪽 노드에 추가된다.
7. 마지막으로 2를 추가해보자. 2는 5보다 작고 4보다 작기 때문에 4의 왼쪽 정점에 추가된다.

이진 탐색 트리 요소 삭제

단말 정점, 즉 leaf 노드를 삭제하는 경우에는 단순하다. 별다른 처리 없이 부모 정점과의 연결을 끊으면 자연스럽게 제거된다. 하나의 서브 트리를 가지는 경우, 제거되는 정점의 부모 간선을 자식 정점을 가르키게 바꾸면 된다. 예를 들어 아래의 그림처럼 7을 제거할 경우에 5의 오른쪽 간선을 8을 가리키도록 수정하면 된다. 두 개의 서브 트리를 가지는 경우, 조금 복잡하다. 둘중 하나를 선택하면 되는데 왼쪽 서브 트리의 가장 큰 값 혹은 오른쪽 서브 트리의 가장 작은 값과 교체하면 된다. 예시를 보면 4를 삭제할 때 3 혹은 5 에 해당하는 정점과 교체하면 된다.
(교체된 정점의 좌우 자식이 없다면 제거되는 정점의 링크로 대체된다.)

이진 탐색 트리의 문제점

굉장히 자주 발생할 수 있는 문제점이다.

1. 먼저 5를 추가한다. root 정점이 된다.
2. 4를 추가한다. root 정점의 왼쪽 정점이 된다.
3. 3을 추가한다. 또 왼쪽 정점으로 삽입된다.
4. 2를 추가한다. 또 왼쪽 정점으로 삽입된다.
5. 1을 추가한다. 또 왼쪽 정점으로 삽입된다. 위의 예시처럼 이진 탐색 트리는 최악의 경우 한쪽으로 편향된 트리가 될 수 있다. 그래서 이런 경우에는 순차 탐색과 동일한 시간복잡도를 가진다. 이를 해결하기 위해 AVL 트리, 레드-블랙 트리 자료구조를 이용할 수 있다. AVL 트리, 레드-블랙 트리 자료구조를 이용하면 이진 탐색 트리의 균형을 맞춰줄 수 있다.

구글이나 네이버 같은 검색 서비스에서 자동 완성을 하려면 어떻게 해야 할까? 이런 경우에 사용하는 적합한 자료구조로 트라이가 있다. 트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 아래의 그림처럼 트리 구조로 되어 있어 간선은 이전 정점으로부터 새롭게 추가되는 문자 정보를 가지고 있다. 그리고 정점은 이전 정점으로부터 더해진 문자열 정보를 가지고 있다. 예를 들어 루트의 오른쪽 정점 t 하위는 모두 앞 글자로 t 를 가지고 있다. 이런 식으로 우리가 미리 정의한 문자열로 자동 완성을 구현할 수 있다.

트라이의 특징

• 검색어 자동완성, 사전 찾기 등에 응용될 수 있다.

• 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다.
• L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.
• 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용한다.

트라이의 생성

트라이 구조는 몇가지 규칙이 있다.

• 먼저 루트는 비어있는 공백이다.
• 각 간선(링크)은 추가돌 문자를 키로 가진다.
• 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.
• 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.

예시를 살펴보자.

처음에는 빈 루트 정점만 존재한다. 여기에 cat 이라는 문자열을 추가한다. 먼저 문자열의 맨 앞 ‘c’ 를 잘라 루트 정점의 자식으로 추가한다. 이어서 맨 앞 문자열 ‘a’ 를 잘라 c 정점의 자식으로 추가한다. 이때 간선의 키는 a 가 된다. 마지막 문자열 ’t’ 를 잘라 ca 정점의 자식으로 추가한다. 이렇게 되면 문자열 ‘cat’ 는 트라이 구조에 저장된다. 이번에는 문자열 ‘can’ 을 추가해보자. 맨 앞 문자열 ‘c’ 을 자른 후 확인한다. 이미 정점이 있기에 이동만 한다. 다음으로 맨 앞 문자열 ‘a’ 를 자른 후 확인한다. 이미 정점이 있기에 이동만 한다. 마지막으로 남은 문자열 ’n’ 을 자른 후 확인한다. n 간선은 없기에 정점에 추가한다. 이렇게 하면 문자열 ‘can’ 은 트라이에 저장된다.

자바스크립트에서 사용법

트라이의 로직을 구성하는 방법은 다음과 같다. 먼저 트리 구조인 만큼 그래프처럼 노드가 필요하다. 여기서 인접 리스트 형태로 구현한다. 트라이를 생성하면 root 로 빈 노드를 생성한다. 문자열을 추가하면 탐색을 위해서 루트부터 시작을 한다. 문자열을 앞에서부터 하나씩 자르면서 순회한다. 만약 현재 노드에서 짜른 문자열을 간선으로 가지고 있지 않다면, 새롭게 노드를 추가한다. 그리고 나서 다음 정점으로 이동한다. 이 루프를 반복하면 문자열을 요소로 전부 추가할 수 있다. 그리고 트라이에서 문자열이 존재하는지에 대한 여부를 체크하는 함수는 has 이다. 추가를 응용한 코드라서 그다지 어렵지는 않다.

힙을 설명하기 전에 우선순위 큐에 대해서 알아보자. 우선순위 큐는 FIFO 인 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 큐를 말한다. 여기서 주의해야 하는 것은 우선순위 큐는 자료구조가 아닌 개념이다. 따라서 우선순위 큐를 구현하는 방법은 다양하게 존재할 수 있다. 그중 힙은 우선순위 큐를 구현하기 위한 가장 적합한 방법이다. 자료구조 힙은 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될때 바로 정렬되는 특징이 있다. 그래서 간혹 우선순위 큐와 힙을 같은 것이라고 말하는 경우가 있지만, 실제로는 다르다. 만약 매번 배열을 우선순위에 따라 정렬한다면 그것도 우선순위 큐가 될 수 있다. 단지 힙 보다 효율이 떨어질 뿐이다.

힙의 특징

• 우선순위가 높은 요소를 루트 보다 배치하고 항상 루트가 먼저 나간다라는 특징을 가진다.

• 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 힙(Min Heap)으로 나뉠 수 있다. 오름차순이냐, 내림차순이냐의 정도의 차이이다.
• 다른 언어와 다르게 자바스크립트는 힙을 직접 코드로 구현해서 사용해야 한다.

힙의 요소 추가

1. 먼저 요소가 추가될 때 이진 트리의 가장 마지막 정점에 추가한다.
2. 요소가 추가되었다면 부모 정점보다 우선순위가 높은지 체크한다. 만약 추가된 요소가 더 높다면 부모 정점과 순서를 바꾼다.
3. 그리고 더 이상 순서를 바꿀 수 없을 때까지 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다.
4. 그리고 요소는 항상 이진 트리의 마지막에 추가가 되기 때문에 힙은 항상 완전 이진트리이다. 따라서 높이는 log N 이기에 요소 추가 알고리즘은 최악의 경우에도 log N이라는 짧은 시간만에 가능하다.

먼저 최대 힙을 만든다 가정하고 45를 추가해본다고 가정하자. 그러먼 루트에 45 정점이 생긴다. 그리고 힙은 이진트리이기 때문에 배열로 표현이 가능하다. 이번에는 36을 추가해보자. 가장 마지막 위치인 45정점 왼쪽에 추가된다. 이어서 54를 추가한다. 가장 마지막 위치인 루트의 오른쪽에 추가된다. 최대 힙에서 45보다 54가 우선순위가 더 높기 때문에 서로 순서를 바꿔야 한다. 규칙에 따라 루트와 오른쪽 정점을 바꿔준다.
이번에는 27을 추가해보자. 마지막 위치 36에 왼쪽 정점에 추가된다. 이어서 63을 추가한다. 36의 오른쪽 정점에 추가된다. 36보다 63이 우선순위가 더 높기 때문에 바꿔야한다. 규칙에 따라 36과 63을 바꿔준다. 여기서 또 부모 정점과 비교해보니 54보다 63이 우선순위가 더 높음을 알 수 있다. 마찬가지로 규칙에 따라 54와 63를 교체해준다. 루트까지 이동했기 때문에 탐색을 종료한다. 이런 식의 추가 로직에 따라 알고리즘을 작성하면 최대 힙을 완성할 수 있다.

힙의 요소 제거

힙 요소 제거 알고리즘은 추가 알고리즘보다 조금 더 복잡하다.

• 먼저 요소를 제거하는 건 루트 정점만 가능하다.
• 루트 정점이 제거되면 그 공백을 가장 마지막 정점에 배치한다.
• 이때 추가와는 반대로 루트로부터 점점 정점을 아래로 내려야 한다.
• 루트 정점의 두 정점 자식 중 더 우선순위가 높은 정점과 바꾼다.
• 두 자식의 정점이 우선순위가 더 낮을 때까지 반복한다.
• 그러면 자연스럽게 우선순위가 더 높은 정점이 루트 정점이 될 수 있다.
• 추가와 마찬가지로 제거도 완전 이진트리의 높이 만큼만 진행되기 때문에 시간 복잡도가 log 시간을 가진다.

먼저 루트 정점인 63을 제거해보자. 그럼 가장 마지막 정점인 36이 루트에 위치하게 된다. 다음엔 규칙에 따라 자식 정점인 54와 45를 비교한다. 54가 우선 순위가 더 높기 때문에 54와 45를 교체한다. 그리고 자식 정점인 27과 비교한다. 여기서 오른쪽 자식은 없기 때문에 27하고만 비교한다. 이번엔 자식의 우선 순위가 더 낮기 때문에 바꾸지 않고 로직을 종료한다.

방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조를 가지고 있다. 하나의 root 에서 하위로 뻗어나가는 구조를 가지고 있다. 용어 설명을 하자면 가장 상위에 존재하는 정점을 root 라고 부른다. 각 정점은 Node 라고 부르며 더 이상 자식이 없는 정점을 leaf 노드라고 부른다. 그리고 트리에는 레벨이라는 개념이 존재한다. 레벨은 root 로부터 몇 번째 깊이인지를 표현할 때 쓰인다. 그림에서 표현한 트리는 레벨3까지 존재한다. 그리고 한 정점에서 뻗어나가는 정점 수를 Degree 혹은 차수라고 부른다. 이런 트리는 어디에서 많이 사용할까? 가장 먼저 사용되는 곳은 조직도이다. 아래의 그림을 보면 대표이사부터 시작하여 여러 부서로 뻗어나가고 있다. 위의 그림처럼 트리의 특징과 비슷하다.
그리고 소프트웨어에서 떠올릴 수 있는 것은 디렉토리 구조이다. 이처럼 트리도 다양한 곳에서 쓰일 수 있는 자료구조이다.

트리의 특징

• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.

• 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다. 왜냐하면 하나의 부모 정점만을 가지기 때문이다.
• 루트에서 특정 정점으로 가는 경로는 유일하다.

이진 트리

이진 트리란?

이진 트리는 각 정점이 최대 2개의 자식을 가지는 트리를 의미한다.탐색을 위한 알고리즘에서 많이 사용되므로 그 특징을 알아두면 좋다.완전 이진 트리는 마지막 레벨을 제외하고 모든 정점이 채워져 있는 트리를 의미한다. 만약 마지막 레벨도 모두 채워져 있다면 포화 이진 트리라고 부른다. 편향 트리의 경우에는 한 방향으로만 정점이 이어져 있는 것을 뜻한다.

이진 트리의 특징

• 정점이 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있다. N개의 정점을 가진 편향 트리가 된다고 생각하면 된다.
• 정점이 N개인 포화 또는 완전 이진 트리의 높이는 logN 이다. 레벨이 증가 됨에 따라 2배씩 정점이 생기기 때문이다.
• 높이가 h인 포화 이진 트리는 2의 h제곱 - 1개의 정점을 가진다. 이진법을 생각하면 편하다.
• 일반적인 이진 트리를 사용하는 경우는 많지 않다. 다음 자료구조에 응용된다. -> 이진 탐색 트리, 힙, AVL 트리, 레드 블래 트리

트리의 구현 방법

트리가 그래프의 일종인 만큼 트리의 구현 방법도 그래프와 동일하게 인접 행렬 리스트 두가지 방식으로 트리를 표현할 수 있다. 이진 트리의 경우 자식의 수가 2개 이하로 제한 되는 특징 때문에 조금 더 최적화된 방식으로 구현이 가능하다. 1차원 배열 혹은 링크가 두개 존재하는 연결 리스트로 구현이 가능하다. JavaScript 에서 이진 트리의 구현 방법은 배열을 사용하면 된다. 단, 몇가지 규칙을 지켜야 한다. index * 2 를 하면 왼쪽 정점이고 index * 2 + 1 을 하면 오른쪽 정점이 된다. 만야 부모 정점을 알고 싶다면 Index / 2 로 나누고 소수점을 버리면 된다. 이런 방식으로 굉장히 간단하게 이진 트리를 표현할 수 있다. 이진 트리를 연결 리스트로 구현하는 것도 그렇게 어렵지는 않다. 기존 연결리스트의 노드에 next 대신 left 와 right 를 넣는다. 그리고 계속 left 와 right 에 값을 연결 시켜주면 이진 트리가 완성된다.

그래프는 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조이다. 정점 집합과 간선 집합으로 표현이 가능하다. 여기서 정점과 간선은 노드(Node) 와 엣지(Edge)라고 부른다. 이런 그래프는 보통 인물 관계도에서 많이 볼 수 있다. 여기서는 정점이 인물이고 간선이 정점간의 관계이다. 실제 소프트웨어에 사용되는 예로는 지하철 노선도나 페이지 랭크 알고리즘이 있다. 지하철 노선도의 경우 각 정점이 지하철역이 되며 지하철역과 역 사이의 간선은 이동 시간 정보를 가지고 있다. 페이지 랭크 알고리즘은 구글이 존재 할 수 있게 한 알고리즘이다. 간단하게 설명하자면, 하나의 페이지가 정점이 되고 페이지에서 파생되는 링크들이 간선이 된다. 페이지 랭크는 이런 방식으로 페이지와 랭크를 수집하여 우선도를 측정하고 검색 결과를 계산한다.

그래프의 특징

위의 예시처럼 그래프는 소프트웨어 개발에서 중요한 자료구조중 하나이다. 그래프의 특징으로 4가지가 있다.

1. 정점은 여러 개의 간선을 가질 수 있다. 선형 자료구조는 앞뒤로 하나의 요소만 가질 수 있었지만 비선형 자료구조인 그래프는 앞뒤로 여러 개의 요소가 배치 될 수 있다.
2. 크게 방향 그래프와 무방향 그래프로 나눌 수 있다.
3. 간선은 가중치를 가질 수 있다.
4. 탐색 시 계속 루프가 가능한 사이클이 발생할 수 있다. 그래서 탐색 시엔 무한 루프에 빠지지 않도록 사이클을 찾아야 할 필요가 있다.

그래프의 종류

무방향 그래프

말 그대로 방향이 존재하지 않는 그래프이다. 반대로 말하면 앙뱡향으로 이동 가능한 간선으로 이루어져 있다고 볼 수 있다. 따라서 간선으로 이어진 정점끼리는 양방향으로 이동이 가능한데 표현하기에는 A에서 B로 이동이 가능하고 B에서 A로 이동이 가능하다.

방향 그래프

간선에 방향성이 존재하는 그래프이다. A정점과 B정점을 보면 양방향으로 갈 수는 있지만 간선이 두개가 존재한다. 만약 간선 두개 중 하나가 존재하지 않는다면 양방향으로 이동할 수 없게 된다.

연결 그래프

모든 정점이 서로 이동 가능한 상태인 그래프이다. 특정 정점에서 또 다른 특정정점까지 모든 경우의 수가 이동 가능해야만 한다.

비연결 그래프

특정 정점쌍 사이에 간선이 존재하지 않는 그래프이다. 예를 들어 아래의 그림처럼 이선협 정점이 그 어떤 간선과도 연결되어 있지 않기 때문에 이 그래프는 비연결 그래프라고 부른다.

완전 그래프

연결 그래프를 넘어 모든 정점끼리 연결된 상태인 그래프이다. 따라서 한점의 간선 수는 모든 정점의 수 - 1 이 된다. 그리고 모든 정점의 수에 1을 뺀 값에 모든 정점 수를 곱하면 모든 간선 수를 알 수 있다.

사이클

사이클은 말 그대로 순환되는 영역을 말한다. 그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분을 말할 수 있는데 그림에서는 A,B,C 정점이 서로 순환되는 것을 알 수 있다.

이런 그래프를 코드로 나타내려면 두 가지 방법이 존재한다. 인접 행렬과 인접 리스트 두 가지 방식으로 그래프를 표현할 수 있다. 인접 행렬은 2차원 배열을 이용할 수 있고 인접 리스트는 연결 리스트로 표현이 가능하다.

그래프 구현

인접 행렬

인접 행렬은 간단하다. 정점의 크기만큼 2차언 배열을 만들고 연결이 안된 상태로 초기화한다. 그리고 나서 행렬의 열 부분을 시작 정점, 행 부분을 도착 정점으로 두고 true 값을 넣어주면 간선이 연결 된 것으로 할 수 있다. 이런 식으로 쉽게 그래프 표현이 가능하다. 만약 간선에 가중치를 넣고 싶다면 false 와 true 가 아닌 null 과 임의의 가중치 값을 넣으면 된다. 참고로 무방향 그래프를 구현한다면 모든 값을 대칭으로 넣어주면 된다.

인접 리스트

인접 리스트도 구현이 간단하다. 특히 자바스크립트에서 배열은 마치 연결 리스트처럼 무한정 늘어날 수 있기 때문에 정점의 수 만큼 배열을 만든 후 연결할 정점을 배열에 추가하면 된다.