Data structure & Algorithm(old)

210606 일요일 13~14일차

# 12~13일차 복습

CH6 연결 리스트

배열의 단점 : 대부분 프로그래밍 언어에서는 배열이 꽉 차면 데이터를 입력하기가 어렵다. 데이터를 추가하거나 삭제할 때도 나머지 요소를 이동해야 하므로 어려움이 따른다. 자바스크립트는 배열의 split()을 이용하면 간단하다. 하지만 자바스크립트의 배열은 객체라서 C++이나 자바보다 배열의 효율이 떨어진다. 따라서 배열이 너무 느리다고 판단되면 사용할 수 있다. 다만 임의의 요소에 접근해야 할 때는 연결리스트보다 배열이 낫다.

•

연결 리스트 정의 : node라 불리는 객체가 모여 연결 리스트를 구성한다. 각 노드는 객체 레퍼런스를 통해 리스트의 다른 노드와 연결된다. 다른 노드를 참조하는 레퍼런스를 Link라고 한다.

•

연결 리스트의 요소는 다른 요소와의 관계를 통해 원하는 요소를 참조할 수 있다. 예를 들어, Bread가 두 번째 위치에 있다라고 표현하는 것이 아니라 "Milk" 다음에 "Bread"가 있다라고 표현한다.

•

연결 리스트에서는 첫 번째 노드에서 마지막 노드로 이동하는 방식으로 전체 요소를 확인할 수 있다.

•

새 노드를 추가하려면 삽입하려는 노드의 이전 노드 링크가 새 노드를 가리키도록 바꿔야 하고 새 노드의 링크는 이전 노드가 가리키던 노드를 가리키도록 설정해야 한다.

•

항목을 삭제할 때는 삭제하려는 노드의 이전에 있는 노드 링크를 삭제하려는 노드가 가리키는 노드로 바꾼 다음, 삭제하려는 노드의 링크를 NULL로 설정하면 노드가 삭제된다.

•

Node 클래스

•

연결 리스트 클래스

LList 클래스는 연결 리스트의 기능을 제공한다. LList 클래스는 새 노드의 삽입, 기존 노드의 삭제, 리스트의 특정 데이터 검색 등의 기능을 제공한다. 새 연결 리스트를 만드는 데 사용할 생성자 함수도 제공한다. 초기에는 head의 next 프로퍼티를 null로 설정한다. 리스트에 노드가 추가되면 next 프로퍼티 값을 바꾼다.

with JavaScripts Study Days 14-15

Dictionary

2021/06/06

2021/12/26 10:48

210519 토요일 12~13일차

# 9~11일차 복습

CH5 큐

•

큐는 리스트의 일종으로 끝부분으로 데이터가 삽입되고 앞부분에서 데이터가 삭제되는 구조이다. 일어난 순서대로 데이터를 저장하지만 스택과 반대로 먼저 들어온 순서대로 처리한다. 선입선출.

•

enqueue는 큐의 끝부분에 요소 추가, dequeue는 큐의 앞부분에 요소 삭제, 큐의 앞부분 요소를 확인하는 peek, 요소 개수를 확인하는 length, 전체 요소를 삭제하는 length, front()는 맨 앞의 요소, back()은 맨 뒤의 요소를 보여준다.

•

큐로 데이터 정렬하기

큐를 이용하여 기수정렬을 구현할 수 있다. 기수정렬은 두 번의 과정을 거쳐 데이터를 정렬한다. 0~99 정수를 이용한다.

•

우선순위 큐

보통 큐에서는 먼저 넣은 요소부터 삭제된다. 하지만 선입선출이 아니라 우선순위와 같은 다른 기준으로 요소를 삭제해야 하는 경우도 있다. 이럴 때는 우선순위 큐를 이용한다. 응급실에서는 환자의 상태를 평가해 우선순위 코드를 부여한다. 우선순위가 높은 환자가 낮은 환자보다는 먼저 진료 받는다. code는 우선순위를 나타내며 가장 높은 우선순위는 1,2,3,4,,, 순이다.(숫자가 낮을수록 높다.)

with JavaScripts Study Days 12-13

LinkedList

2021/05/30

2021/12/26 10:48

210519 수요일 9~11일차

# 8일차 복습

CH3 리스트

•

#1 : 현재 리스트의 모든 요소보다 클 때만 요소를 삽입하는 함수를 구현하시오. 여기서 크다는 의미는 숫자일 때는 크기를 비교하고, 텍스트일 때는 알파벳순으로 나중을 의미한다.

현재 리스트의 모든 요소보다 클 때라는 조건을 만족하는 지 확인하기 위한 함수를 만들었다.

모든 요소보다 크면 true, 큰 요소가 존재할 시 중간에 false를 반환해주는 함수를 구현했다.

먼저 삽입하고자 하는 요소 (after)를 find함수로 찾아서 인덱스를 받은 다음 인덱스가 존재한다면 그 위치에 slice함수를 이용해서 삽입하였다. 삽입 후에는 listSize를 1 증가시킨다.

•

#2 현재 리스트의 모든 요소보다 작을 때만 요소를 삽입하는 함수를 구현하시오.

비교 연산자만 반대로 바꾸어 구현하였다.

•

#3 사람의 이름과 성별을 저장하는 Person 클래스를 구현하시오. 최소한 10개의 Person 객체를 포함하는 리스트를 만드시오. 리스트에서 같은 성별을 가진 사람을 모두 출력하는 함수를 구현하시오.

filter는 주어진 조건을 통과하는 모든 요소를 모아 배열로 반환한다. 따라서 이를 통해 인자로 주어진 성별을 가진 객체만 모아서 배열을 구성하도록 했다.

CH4 스택

•

가장 윗 부분에서만 자료의 추가/삭제가 일어나므로 실행속도가 빠르고 구현이 쉽다.

•

후입선출로 밑바닥에 있는 요소에 접근하려면 모든 요소를 제거하는 수 밖에 없다.

•

Top은 pop으로 확인할 수 있지만 요소를 꺼내기 때문에 peek으로 내용을 확인한다. peek은 top - 1의 위치에 접근해 스택의 탑 요소를 확인한다. (스택의 요소가 3이면 top(length)는 3이고 배열의 가장 오른쪽 값은 가장 윗 값이므로 top-1이 top에 있는 요소의 인덱스다.

with JavaScripts Study Days 9-11

Queue

2021/05/20

2021/12/26 10:48

210508 토요일 8일차

# 5~7일차 복습

•

리스트는 위치를 가리키는 프로퍼티(front, end)가 있다.

•

next() 함수로 리스트의 현재 요소에서 다음 요소로 이동할 수 있다.

•

prev() 함수로 현재 요소에서 이전 요소로 이동할 수 있다.

•

moveTo(n) 함수를 이용하면 n 번째 위치로 한 번에 이동할 수 있다.

•

currPos() 함수는 리스트의 현재 위치를 가리킨다.

•

List 클래스 구현

생성자 함수

•

Append : 리스트에 요소 추가(listSize 위치에 요소를 추가한다.)

•

Find : 리스트의 요소 검색(length 함수 필요, 인덱스 값 반환)

•

Remove : 리스트의 요소 삭제

with JavaScripts Study Days 8

210502 일요일 5일차

# 3~4일차 복습

•

배열의 처음에 요소를 추가할 때 변형자 함수가 없다면 배열에 있던 기존 모든 요소를 한 칸씩 뒤로 이동시킨 다음 새 데이터를 추가해야 한다. unshift()는 한 번에 여러 요소를 배열 앞으로 추가할 수도 있다.

•

배열의 앞 요소를 제거할 때 변형자 함수가 없다면 요소를 추가할 때와 마찬가지로 비효율적이다. 비효율적인 동작 후에 맨 끝에 불필요한 값이 저장된다. 마지막 콤마가 출력된 것으로 알 수 있다.

shift() 함수를 이용하면 간단히 배열의 맨 처음 요소를 제거할 수 있다.

•

pop()과 shift()는 제거된 요소를 반환하므로 필요하면 이 요소를 변수에 저장할 수 있다.

•

splice()

•

시작 인덱스(어느 지점부터 요소를 추가할 것인지)

•

삭제할 요소의 개수(요소를 추가할 때는 O)

•

배열에 추가할 요소들

시작 인덱스 3(nums[3]), 0이므로 요소 추가, 그 다음부터는 추가하려는 요소 목록을 자유롭게 제공하면 된다.

시작 인덱스 3(nums[3])부터 요소 4개를 삭제한다.

with JavaScripts Study Days 5-7

List

2021/05/05

2021/12/26 10:48

# 1~2일차 복습

•

자바스크립트에서 모든 함수의 파라미터는 값으로 전달되며(call by value) 레퍼런스 전용 파라미터는 없다. 하지만 배열처럼 객체 레퍼런스를 함수 파라미터로 사용할 때는 레퍼런스로 전달된다.

•

JS는 기본 타입(number, string, boolean, null, undefined)을 제외한 모든 값이 '객체'이다. 따라서 배열, 함수, 정규표현식 등 모두 객체로 표현된다. 이것은 객체의 모든 연산이 실제 값이 아닌 참조값으로 처리되기 때문이다.

•

기본 타입과 참조 타입의 경우는 함수 호출 방식도 다르다. 기본 타입은 call by value로 동작한다. 함수의 인자로 기본 타입이 넘겨질 경우, 함수의 매개변수로 복사된 값이 전달된다. 따라서 함수 내부에서 매개변수를 이용해 값을 변경해도, 실제로 호출된 변수의 값이 변경되지는 않는다.

반면, 객체와 같은 참조 타입의 경우, 함수를 호출할 때 call by reference(틀림!)로 동작한다. 즉, 함수를 호출할 때, 객체의 참조값이 전달되고 함수 내부에서 참조값을 이용해 인자로 넘긴 실제 객체의 값을 변경할 수 있다.

•

> JS에서 call by reference가 틀린 이유?

JS는 항상 call by value다. 왜냐하면 cbr이 불완전하기 때문이다.

c나 c++ 같은 언어에서 포인터를 예로 들면, 함수 내에서 obj2 = 10;을 하는 경우 obj1의 값이 10이 된다. 완전한 주소값 참조로 되어 있기 때문이다.

하지만 JS의 경우에는 객체의 프로퍼티 값이 아닌 객체 자체의 변경을 허용하지 않는다. 왜냐하면 겉보기에는 주소값을 참조하는 것 같지만 실제로는 주소값의 복사본을 만들어서 넘기기 때문이다.

https://velog.io/@leo-xee/JS-Call-by-value-reference

이처럼 함수 내부의 obj2 = 10;에서 obj2의 주소값이 10이 저장된 위치의 주소값으로 변경된다. 결론적으로 두 객체는 다른 객체이다. 때문에 JS는 call by sharing이라는 용어를 사용하기도 한다.

•

var 키워드를 사용하지 않고 변수를 선언하면 함수 내에 선언하더라도 그 변수는 자동으로 전역 범위를 갖는다. 함수에서 선언한 변수가 메인 프로그램에 있는 전역 변수의 값을 변경하게 된다.(var : function scope / const, let : block scope)

•

JS에서는 변수 범위가 함수 범위고 블록 범위가 지원되지 않는다고 했으나 ES6(ES2015)에서 let, const가 지원되면서 가능해졌다.

with JavaScripts Study Days 3-4

2Darray

2021/05/02

2021/12/26 10:48

CH1 자바스크립트 프로그래밍 환경과 모델

1.2 자바스크립트 프로그래밍 기초

1.2.1 변수 선언과 초기화 ~ 1.2.5 함수

어제 오전부터 자바스크립트 자료구조와 알고리즘 공부를 다시 시작했고 깃헙에 레포지토리를 만들어 코드를 올렸다.

자바스크립트에서의 함수 예제 코드까지 따라 쳤는데 다른 언어들과 크게 다른 점은 없다. switch문에 테스트 대상 표현식에서 모든 데이터형을 사용할 수 있다는 점이 다른데 switch문 자체가 효율적이지는 않다.

자바스크립트에서 모든 함수의 파라미터는 값으로 전달되며 레퍼런스 전용 파라미터는 없다.(처음에는 확실히 이해가 가지 않은 부분) 하지만 배열처럼 객체 레퍼런스를 함수 파라미터로 사용할 때는 레퍼런스로 전달된다.

번역판이라서 그런 건지 어떤 의미인지 명확히 이해가 잘 되지 않아서 더 자세히 찾아보았다. 레퍼런스 전용 파라미터라든지 객체 레퍼런스가 어떤 의미인지 알아보았다.

자바스크립트는 기본 타입(number, string, boolean, null, undefined)을 제외한 모든 값이 '객체'이다. 따라서 배열, 함수, 정규표현식 등은 모두 객체로 표현된다. 이것은 객체의 모든 연산이 실제 값이 아닌 참조값으로 처리되기 때문이다.(여기서는 이 마지막 문장이 앞선 문장과 어떤 연관 관계가 있다는 것인지 이해되지 않았다.)

"기본 타입과 참조 타입의 경우는 함수 호출 방식도 다르다. 기본 타입은 값에 의한 호출 (Call By Value)방식으로 동작한다. 함수의 인자로 기본 타입이 넘겨질 경우, 함수의 매개변수로 복사된 값이 전달된다. 따라서, 함수 내부에서 매개변수를 이용해 값을 변경해도, 실제로 호출된 변수의 값이 위 예제처럼 100에서 변경되지 않는다.반면 객체와 같은 참조 타입의 경우, 함수를 호출할 때 참조에 의한 호출( Call By Reference ) 방식으로 동작한다. 즉, 함수를 호출할 때, 객체의 참조값이 전달되고, 함수 내부에서 참조값을 이용해서 인자로 넘긴 실제 객체의 값을 200으로 변경할 수 있다."

https://velog.io/@smp2103/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%B0%B8%EC%A1%B0-%ED%83%80%EC%9E%85%EA%B0%9D%EC%B2%B4

자바스크립트 참조 타입(객체) 객체 velog.io

이처럼 call by value, call by reference 방식에 대해서는 많이 들었기 때문에 알고 있었다.

기본 타입의 값을 함수의 파라미터로 넘겨주었을 때 그 파라미터에 어떤 다른 값을 할당하더라도 그 함수 내에서만 영향이 있는 것이다. 하지만 객체와 같은 참조 타입의 파라미터를 함수로 넘겨 주었을 경우에는 함수 안에서 객체의 속성값들을 변경할 수 있고 함수가 종료되더라도 원래 데이터에 영향을 미친다.