프로그래밍 공부하기

문자열의 각 문자에 접근하는 방법은 charAt과 숫자 인덱스가 있다. 두 방법은 별 차이가 없어 보이지만 빈문자를 접근할 때 차이가 발생한다. 프로그래머스 JadenCase 문제를 풀어보자. JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. "3people unFollowed me" -> "3people Unfollowed Me" const str = " "; const words = str.toLowerCase().split(' '); //words = ['', '']; 먼저 문자를 단어별로 분류하기 위해 공백 기준으로 split해보자. 이 ..

무방향 그래프의 한 정점(start)에서 다른 정점(end)까지 최단거리를 찾는 함수를 작성하세요. 입출력 예시 let num = 4; let edges = [ [1, 2, 6], [1, 3, 2], [2, 3, 3], [2, 4, 1], [3, 4, 5], ]; let start = 1; let end = 4; Dijkstra(num, edges, start, end); // 6 (1 - 3 - 2 - 4) 그래프에서 노드 간의 최단 경로를 찾는 대표적인 알고리즘 중 하나가 다익스트라 알고리즘이다. 위 문제를 다익스트라 알고리즘을 통해 풀어보자. 우선 다익스트라 알고리즘은 다음과 같은 순서로 진행된다. 시작점과 모든 노드와의 거리(비용)를 기록한다. 시작점과 연결된 모든 노드 중 가장 최단거리인 노드(..

HeapSort란 최대 힙 트리나 최소 힙 트리를 만들어 정렬하는 방법이다. 최대 힙은 루트가 트리의 값들 중 가장 큰 값을 갖고, 최소 힙은 루트가 가장 작은 값을 갖는다. 위의 트리는 [0, 2, 1, 5, 3, 4, 8] 이라는 배열과 동일하다. 1. 요소를 추가할 때 새로운 요소가 추가되면 우선 가장 트리의 가장 마지막으로 넣어진다. 그 후 부모노드와 비교해서 작으면 부모와 위치를 교환하고, 이를 반복해나간다. 노드의 자식은 2개까지 가질 수 있다. 따라서 n번째 노드의 부모는 Math.floor((n-1) / 2) 와 동일하다. 예를 들어 배열 인덱스가 0부터 시작하고 값이 [0, 1, 2]일 때 최상위 노드는 0이며, 자식으로 1과 2를 갖는다. 0 = f(1) = f(2) 를 만족시켜야 하므..

내가 푼 문제 코드를 저장한 Git 주소 github.com/ImHyeLim1209/Solve_Algorithm_Problem ImHyeLim1209/Solve_Algorithm_Problem 알고리즘 문제풀이. Contribute to ImHyeLim1209/Solve_Algorithm_Problem development by creating an account on GitHub. github.com

1.Tree 트리는 노드로 구성된 계층적 자료구조로 나무를 거꾸로 세운 모습이다. 트리는 1개 이상의 노드로 구성되며, 최상위 노드인 루트로부터 시작하여 루트의 자식노드가 존재하고 그 자식노드의 자식노드가 존재하는 구조가 반복된다. 따라서 트리는 루트와 전체 트리의 부속트리로 구성된다고 말할 수 있다. 2.용어 노드의 차수(degree): 노드에 연결된 또 다른 노드의 갯수. 즉, 노드의 자식노드 갯수이자 부속트리 개수이다. ex. 위 그림에서 노드 1의 차수는 2이고, 노드 2의 차수는 0이다. 관계에 따른 노드 구분 부모 노드(parend node): 노드를 서브트리로 갖는 노드. ex. 위 그림에서 노드 4의 부모 노드는 노드 1이다. 자식 노드(child node): 부모에 속하는 노드. ex. ..

1. Graph 자료구조에서 그래프란 정점(vertex, node)과 정점 사이를 연결하는 간선(edge)으로 구성된 자료구조이다. 그래프는 간선의 방향유무에 따라 무방향 그래프와 방향 그래프로 나뉜다. 간선은 보통 간선이 연결하고 있는 두 정점의 쌍으로 표시하며 무방향 그래프의 경우 괄호를 사용하여 (A, B), 방향 그래프의 경우 꺽쇠 기호를 사용하여 와 같이 표기한다. 그 외에 간선에 비용이나 가중치가 할당된 가중치 그래프(weighted graph)가 존재한다. 2. 용어 그래프와 관련된 다양한 용어들이 존재한다. 이러한 용어들을 하나씩 알아보자. Vertex(정점): 그래프의 각 정점을 vertex 혹은 node라고 한다. 위 그래프에서는 0, 1, 2 총 3개의 노드가 존재한다. Edge(간선..

1. Hash Table 해시 테이블은 키와 값의 쌍을 저장하는 구조이다. 예를 들어 전화번호부에서 이름(Key)을 통해 전화번호(Value)를 알아낼 수 있는 것처럼 키를 이용하여 값을 얻어낼 수 있다. 해시 테이블은 다음과 같은 구성을 갖고 있다. 1) Key Key는 데이터 저장/탐색을 위한 고유의 값(identifier)이다. 데이터 저장 시 Key는 해시 함수에 입력되어 Data가 해시 테이블의 저장소 어느 곳에 저장될 것인지를 결정한다. 2) Hash Function 해시 함수는 키를 해시로 변환하는 함수이다. 여러가지 값을 갖고 있는 키를 일정한 형식을 갖도록 변환함으로써 저장소를 관리한다. 예를 들어 해시 테이블의 저장소가 2칸(bucket) 이라면 hash function이 fn(){ r..

1. Linked List 연결 리스트(Linked List)는 저장된 데이터 간의 연결이 존재하는 형태로 데이터를 저장하는 자료구조이다. 연결 리스트에 저장되는 데이터 형태를 자세히 들여다보면 다음과 같다. 연결 리스트는 데이터를 그대로 저장하는 것이 아니라 Node라는 형태로 저장한다. 노드는 Data와 다음 노드와의 연결인 Link로 구성되어있다. 링크를 통해 데이터의 연결 및 순서가 발생하며 순서상 가장 앞에 있는 노드는 Head, 가장 뒤에 있는 노드는 Tail이라 한다. 2. vs Array 순서가 있는 데이터라는 점에서 배열과 연결 리스트는 매우 유사한 구조로 보인다. 그러나 몇 가지 차이점이 존재한다. 1) 메모리 배열과 연결 리스트에 각각 1, 2, 3, 4 라는 데이터를 넣었을 때 메모..

1. Stack Stack은 목록의 끝(top/스택포인터)에서만 데이터를 입력(push)과 출력(pop)할 수 있는 자료구조이다. 따라서 나중에 입력된 데이터를 먼저 꺼내며 이를 LIFO(Last In First Out/후입선출) 구조라고 한다. 한편 Stack의 데이터를 담을 수 있는 최대치(limit)가 존재한다. Stack이 담은 데이터량이 한계치에 도달하였을 때(스택이 꽉 찬 상태) 입력(push)을 수행하면 해당 데이터를 입력할 수 없으므로 Overflow가 발생한다. 반대로 Stack에 데이터가 없는 경우 출력(pop)을 수행하면 출력할 데이터가 존재하지 않으므로 Underflow가 발생한다. Overflow와 Underflow라는 상황을 방지하기 위해 Stack에 입출력을 하기 전 full ..