코딩테스트 썸네일형 리스트형 알고리즘 3. DFS(깊이 우선 탐색) 트리의 순회, 점화식 구현 등 DFS(재귀 구조)에 특화된 문제인 경우 깊이 우선 탐색(DFS) 사용1. 깊이 우선 탐색(DFS)이란?① 그래프 혹은 트리에서 모든 노드를 한 번씩 탐색하기 위한 기본적인 방법이다.② [완전 탐색]을 수행하기 위해 사용할 수 있는 가장 간단한 방법 중 하나다③ 스택(stack) 자료구조를 사용한다. 2. 깊이 우선 탐색(DFS) 기본 동작 방식1) 시작 노드를 큐에 넣고 [방문 처리]한다.2) 스택에 마지막으로 들어 온 노드에 방문하지 않은 인접 노드가 있는지 확인한다. 있다면, 방문하지 않은 인접 노드를 스택에 삽입하고 [방문 처리]한다. 없다면, 현재 노드(스택에 마지막으로 들어 온 노드)를 스택에서 추출한다.3) 2번 과정을 더 이상 반복할 수 없을 때까지 반복한다.. 더보기 알고리즘 2. BFS(너비 우선 탐색) 시작 정점에서 인접한 정점을 먼저 탐색하는 너비 우선 탐색을 통해 가중치가 없는 그래프에서 두 정점 사이의 최단 경로를 구하기1. 너비 우선 탐색(BFS)이란?① 그래프 혹은 트리에서 모든 노드를 한 번씩 탐색하기 위한 기본적인 방법이다.② [완전 탐색]을 수행하기 위해 사용할 수 있는 방법 중 하나다.③ (모든 간선의 길이가 동일할 때) 최단 거리를 탐색하기 위한 목적으로 사용할 수 있다.④ 큐(queue) 자료구조를 사용한다.👉 기본적으로 DFS는 스택, BFS는 큐를 사용한다. 2. 너비 우선 탐색(BFS) 기본 동작 방식1) 시작 노드를 큐에 넣고 [방문 처리]한다.2) 큐에서 아무 노드가 없을 때까지: a. 큐 가장 앞 노드를 꺼낸다. b. 꺼낸 노드에 인접한 노드들을 모두 보면서: .. 더보기 알고리즘 1. 완전 탐색 반복문 or 재귀 함수로 모든 경우를 처리하기1. 완전 탐색① 완전 탐색이란 가능한 모든 경우를 탐색하면서 정답을 찾는 방법이다.② 두 가지 방법으로 구현 a. 반복문을 통해 가능한 모든 방법을 단순히 찾는 방법 b. 재귀(자기 호출) 함수를 이용하여 현재 상태에서 가능한 후보군으로 가지를 치며 탐색하는 방법4. 온라인 저지 문제 풀이2024.01.30 - [JS 코딩테스트/문제풀이] - [자바스크립트] 15649 N과 M (1)2024.01.30 - [JS 코딩테스트/문제풀이] - [자바스크립트] 15650 N과 M (2)2024.01.30 - [JS 코딩테스트/문제풀이] - [자바스크립트] 2231 분해합2024.01.31 - [JS 코딩테스트/문제풀이] - [자바스크립트] 1436 영화.. 더보기 자료구조 4. 큐 데이터를 추가한 순서대로 처리하기1. 큐(Queue)① 큐(queue)는 먼저 삽입된 데이터가 먼저 추출되는 자료구조(data structure)다. ② 큐는 주로 데이터를 추가, 삭제하는 상황에서 먼저 추가된 데이터를 먼저 삭제할 때 사용한다. 2. 연결 리스트로 큐 구현하기 ① 큐를 연결 리스트로 구현하면, 삽입과 삭제에 있어서 $O(1)$을 보장할 수 있다. ② 연결 리스트로 구현할 때는 머리(head)와 꼬리(tail) 두 개의 포인터를 가진다. ③ 머리(head): 남아있는 원소 중 가장 먼저 들어 온 데이터를 가리키는 포인터 ④ 꼬리(tail): 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터 3. JavaScript 큐(Queue) 배열로 구현하기class Queue {.. 더보기 자료구조 3. 객체 문자열과 숫자를 한쌍으로 처리하기 1. 객체(Object) ① 데이터를 {키(key): 값(value)} 형식으로 저장하는 자료 구조 ② 객체는 주로 문자열과 숫자를 한 쌍으로 처리할 때 사용한다. 2. 온라인 저지 문제 풀이 2024.01.23 - [JS 코딩테스트/문제풀이] - [자바스크립트] 5089 Travelling Salesman 2024.01.23 - [JS 코딩테스트/문제풀이] - [자바스크립트] 10816 숫자 카드 2 2024.01.24 - [JS 코딩테스트/문제풀이] - [자바스크립트] 14425 문자열 집합 2024.01.24 - [JS 코딩테스트/문제풀이] - [자바스크립트] 1764 듣보잡 2024.01.24 - [JS 코딩테스트/문제풀이] - [자바스크립트] 15098 No D.. 더보기 자료구조 2. 문자열 문자를 모아서 처리하는 문자열 1. 문자열(String) ① 문자, 단어 등으로 구성된 문자들의 집합이다. ② 인덱스(index)가 존재하고 인덱스는 0부터 시작한다. 3. 온라인 저지 문제 풀이 2024.01.19 - [JS 코딩테스트/문제풀이] - [자바스크립트] 10808 알파벳 개수 2024.01.20 - [JS 코딩테스트/문제풀이] - [자바스크립트] 9086 문자열 2024.01.20 - [JS 코딩테스트/문제풀이] - [자바스크립트] 2675 문자열 반복 2024.01.21 - [JS 코딩테스트/문제풀이] - [자바스크립트] 4458 첫 글자를 대문자로 2024.01.21 - [JS 코딩테스트/문제풀이] - [자바스크립트] 11721 열 개씩 끊어 출력하기 2024.01.21 - [JS 코딩.. 더보기 자료구조 1. 배열 숫자를 모아서 처리하는 배열 1. 배열(Array) ① 같은 자료형을 갖는 여러 요소(데이터)를 하나의 변수 이름으로 모아 놓은 데이터 집합 ② 하나의 자료 뒤에 하나의 자료가 존재하는 선형 자료 구조 ③ 열 번호를 가리키는 인덱스(index)가 존재하고 인덱스는 0부터 시작한다. ④ 장점 a. 특정한 인덱스에 직접적으로 접근 가능해서 조회가 빠르다. b. 수행시간: \(O(1)\) ⑤ 단점 a. 배열의 크기를 미리 지정해야 하는 것이 일반적 b. 데이터의 추가 및 삭제에 한계가 있다. c. 그러나, 자바스크립트는 동적배열이다. 2. 코딩테스트를 위한 자바스크립트의 배열 ① 자바스크립트에서는 동적 배열로 추가, 삭제가 가능 ② 데이터를 한 칸씩 shift해야 하기 때문에 중간 추가, 삭제는 \(O(n)\.. 더보기 코딩테스트에 대한 모든 것 시작하기 코딩테스트의 이해 1. 기업에서 개발자의 소양을 보는 두 가지 방법 ① 코딩테스트 ② 과제테스트 하지만 이러한 수단 중 개발자의 개발 실력을 단기간 평가하는 방법은 코딩테스트이다. 코딩테스트란 주어진 시간 내에 사고력이 필요한 문제를 프로그래밍 언어로 구현한다. 2. 코딩테스트 해결 방법 ① 문제를 자료구조로 정의 ② 자료구조를 알고리즘으로 설계 사고력이 필요한 문제는 알고리즘과 자료 구조를 이용하여 해결할 수 있다. a. 자료구조: 자료를 효율적으로 저장하고 관리하기 위해 사용된다. 실행 시간↓ b. 알고리즘: 주어진 문제를 해결하기 위해 입력을 받아 원하는 출력을 만들어내는 과정 3. 코딩테스트 사이트 (저지 사이트) ① 국내: 백준(BOJ) 프로그래머스(Programmers) ② 해외: 릿코드(Le.. 더보기 이전 1 다음
