let's get IT with DAVINA 💻

BFS(Breadth First Search) 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행 3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입 4. 큐가 빌 때까지 2번을 반복 모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N) 이 때, x가 행 & y가 열 구현 const graph = { A: ["B", "C"], B: ["A", "D"], C: ["A", "G", "H", "I"], D: ["B", "E", "F"], E: ["D"], F: ["D"], G:..

Deque (Double Ended Queue) 양쪽 끝에서 삽입/삭제가 전부 가능한 자료구조 덱의 성질 원소의 추가 → O(1) 원소의 제거 → O(1) 제일 앞/뒤의 원소 확인 → O(1) 제알 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 구현 const int MX = 1000005; int dat[2*MX+1]; //앞뒤로 다 삽입이 가능해서 양쪽으로 확장하기 때문에 배열의 크기는 2*MX+1 int head=MX, tail=MX;

연결 리스트 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조 연결 리스트의 성질 k번째 원소를 확인/변경하기 위해 O(k)가 필요함 우리는 첫 번째 원소의 주소만 알고 있기 때문, 차근차근 다음 주소로 넘어가며 찾아야 함 임의의 위치에 원소를 추가/제거는 O(1) 이전 원소에 다음 주소를 변경만 해주면 되기 때문에 단, 추가/제거 하고 싶은 위치의 주소를 알고 있을 경우에만 O(1) 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 연결 리스트의 종류 단일 연결 리스트 : 각 원소가 자신의 다음 원소의 주소를 들고 있음 이중 연결 리스트 : 각 원소가 자신의 이전 & 다음 주소를 둘 다 들고 있음 원형 연결 리스트 : 끝이 처..

배열 메모리 상에 원소를 연속하게 배치한 자료구조 배열의 성질 O(1)에 k번째 원소를 확인/변경 가능 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 Cache hit rate가 높음 cache hit rate: 캐시가 적중되는 정도 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 기능과 구현 임의의 위치에 있는 원소를 확인/변경 → O(1) 원소를 끝에 추가 → O(1) 마지막 원소를 제거 → O(1) 임의의 위치에 원소를 추가/제거 → O(N) ex) 마치 책장에 책이 연속해서 꽂혀있을 때 중간에 책을 넣기 위해선 나머지 책들을 밀어야하는 것과 같은 상황 insert 함수 void insert(int idx, int num, int arr[], int&len){ for(l..

Greedy Algorithm (탐욕 알고리즘) 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법 Greedy Algorithm 문제 해결 단계 🔽 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합니다. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다. - 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않습니다. - 최적 부분 구조(Optimal Substructure) : 문제에 대한 ..

공간 복잡도 (Space Complexity) 알고리즘이 수행되는 데에 필요한 메모리의 총량 프로그램이 요구하는 공간 ⇒ 고정적인 공간 + 가변적인 공간 고정적인 공간: 처리할 데이터의 양에 무관하게 항상 요구되는 공간으로서, 프로그램의 성능에 큰 영향을 주지 않음 가변적인 공간: 처리할 테이터의 양에 따라 다르게 요구되는 공간으로서 프로그램의 성능에 큰 영향을 줌! 공간 복잡도 계산은 시간 복잡도 계산과 비슷하게 빅 오(Big-O) 표기법으로 표현 보통 공간 복잡도는 시간 복잡도보다 중요성이 떨어진다. WHY? 시간이 적으면서 메모리까지 지속적으로 증가하는 경우는 거의 없기 때문에.. BUT! 동적 계획법(Dynamic Programming)과 같이 알고리즘이나 하드웨어 환경이 매우 한정되어 있는 경우..

시간 복잡도 (Time Complextity) 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계 Big-O 표기법 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법 Big-O(빅-오) 최악의 경우 프로그램이 실행되는 과정에서 “이 정도 시간까지 걸릴 수 있다”를 고려해야 한다! Big-Ω(빅-오메가) 최선의 경우 Big-θ(빅-세타) 중간(평균)의 경우 O(1) constant complexity 입력값이 증가하더라도 시간이 늘어나지 않는다. 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다. function O_1_algorithm(arr, index) { return arr[index]; } let arr = [1, 2..

알고리즘이란? 어떤 문제를 해결하기 위해서 일련의 절차를 정의하고, 공식화한 형태로 표현한 일종의 문제 풀이 방법 프로그래밍에선? input값을 통해 output값을 얻기 위한 계산 과정 입력(Input) 알고리즘은 출력에 필요한 자료를 입력받을 수 있어야 합니다. (꼭 입력값이 없을 수도 있음) 출력(Output) 알고리즘은 실행이 되면 적어도 한 가지 이상의 결과를 반드시 출력해야 합니다. 유한성(Finiteness) 알고리즘은 유한한 명령어를 수행한 후, 유한한 시간 내에 종료해야 합니다. 명확성(Definiteness) 알고리즘의 각 단계는 단순하고 명확해야 하며, 모호해서는 안됩니다. 효율성(Efficiency) 알고리즘은 가능한 한 효율적이어야 합니다. (시간 복잡도와 공간 복잡도가 낮을수록 ..