코딩테스트-ALL-IN-ONE (파이썬)

데이터를 저장하고 관리하는 방식선형 자료구조arraydynamic arraylinked listqueuestackhash table비선형 자료구조treegraphBFS -> Queue다익스트라 -> heap자료구조를 배워야 어떤 알고리즘을 쓸지 알 수 있다.결과가 많이

데이터를 저장하고 관리하는 방식데이터는 메모리에 저장한다.메모리에는 HDD와 RAM코드는 HDD에 저장코드 실행시 RAM에 올라감비효율적인 코드는 RAM 메모리 낭비데이터를 순차적으로 나열해 놓은 집합메모리상 연속적으로 저장데이터 접근이 쉽다.메모리상 불연속 저장다음

문제 상황: 공 5개 오름차순 정렬해결 방법:(1) 가장 작은 숫자를 찾아서 맨 앞에 놓는다(2) 남은 공들에 대해서 (1) 방법 반복이 때, 해결방법이 알고리즘프로그램 실행 시간시간과 입력값 n의 함수 관계최고차수만을 이용해 Big - O(접근표기법) 사용시간복잡도(

for - while 중첩 되었다고 O(n^2)이 아니다.계산이 가능은 하지만, 엄밀하진 못하다.overhead가 크다.따라서 보수적으로 계산해야한다.계산이 불가한 영역이 있다nqueen기준점: 10^8시간복잡도는 만능이 아니다. (70%는 계산하면 도움이 된다.)풀이

set과 비교가 되지만, set은 순서는 중요하지않다list는 순서가 중요하다Array로 만들어진 list메모리상에서 비연속적으로 연결된 노드python의 list는 다르다 (Array List)python은 dynamic array로 구현, 그런데 dynamic ar

(static) array고정된 저장 공간(fixed-size)순차적인 데이터 저장(order)

선언 이후에 size를 변경할 수 없는 정적배열(Static Array)와 다르게 동적배열(Dynamic Array)는 size를 늘릴 수 있습니다O(n)보통 2배 (더블링)

n^2보다 시간복잡도가 작은 코드로 짜야한다.int -> 4byte -> 32int형 변수 10^9 + 10^9 -1단순화 -> {1,2}

정렬 -> O(nlogn)two pointer: 두 개의 포인터로 왔다갔다하면서 문제 해결, 정렬이 된 상황에서만 씀n번만 실행되겠구나O(nlogn) + O(n)

Linked List Linked List는 Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조입니다. Node는 데이터 값과 Next Node의 주소값을 저장합니다. Linked List는 메모리상에서는 비연속적으로 저장이 되어있지만, 각각의 Node가

Linked List의 다양한 활용1\. Linked List 자유자재로 구현 (선형 자료구조 + 중간에 데이터 추가/삭제 해야하는 문제)2\. Tree or Graph에 활용input, output 확인input 값의 특징 (정수인가? 값 크기의 범위는? 마이너스도

구현방법 Array list based (시간 복잡도 문제) array Dynamic array Linked list based (요걸로 구현) Queue queue는 시간 순서상 먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO (First In Fir

Array list based (리스트 쓰듯이 쓰면 된다)Linked list based (❌)stack은 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO (Last In First Out)형식으로 데이터를 저장하는 자료구조입니다. stac

코테 적용 방법 Stack의 다양한 활용 LIFO 특성을 활용한 문제 ⭐ DFS(깊이 우선 탐색)에 사용 ⭐ 문제 풀이 방법 문제 이해하기 접근 방법 코드 설계 코드 구현 기본 문제

출처 : 인프런 - 코딩테스트 [ ALL IN ONE ] 코테 적용 방법 Stack의 다양한 활용 LIFO 특성을 활용한 문제 ⭐ DFS(깊이 우선 탐색)에 사용 ⭐ 문제 풀이 방법 문제 이해하기 접근 방법 코드 설계 코드 구현 문제 (https://leetcod

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]Array list based (Open addressing) - 파이썬Array list + Linked list based (Seperate chaining)() 괄호 안 내용은 충돌 해결 방법Find ke

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]딕셔너리는 시간복잡도를 줄이기 위해 메모리를 사용하는 것이다.in 오퍼레이션은 랜덤액세스처럼 작동한다.

출처 : 인프런 - 코딩테스트 [ ALL IN ONE ] 문제 (https://leetcode.com/problems/two-sum/) 접근 방법 메모리를 사용하는 방법 이용 한번 보면 바로 기억하는 뇌를 가지고 있을 때, 한번 보면 다 기억함. 업로드중..

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]해시테이블의 활용메모리를 사용해서 시간복잡도를 줄일 때 사용key in { } 가 핵심(https://leetcode.com/problems/longest-consecutive-sequence/)dict

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]자기 자신을 정의할 때 자기 자신을 재참조하는 함수반복문과 비슷함

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]Tree는 서로 연결된 Node의 계층형 자료구조로써, root와 부모-자식 관계의 subtree로 구성되어있습니다.모든 노드의 차수가 n이하일 때, n진 트리라고 한다.노드바이너리트리

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]레벨에 따라서 0 -> 1 -> 2접근은 여러번 할 수 있지만 방문은 다르다. (딱 1번만 방문, 방명록)접근은 current_node로 방문dequeue로 해서BFS - Queue

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]stack 반복문recursion 재귀접근과 방문은 다르다.접근은 여러 번 가능하지만 방문은 1번씩만 진행접근순서: A -> B -> A -> C -> A BFSDFS루트만 주면 루트가 가르키는 트리에 속한 모든

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]DFS전위순회 (preorder)중위순회 (inorder)후위순회 (postorder)접근하기 전에 방문을 먼저 한다.left -> 나 -> rightright -> 나 -> left중간에 자기 자신 방문자식 먼

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]Tree 구현 여부트리 순회(https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/)아무 빔 안 들어올떄나 자

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]Tree 구현Tree 순회a. level orderb. postorder(https://leetcode.com/problems/maximum-depth-of-binary-tree/)level order는

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]그래프 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조입니다.\-트리는 계층적으로 연결되는 일방향방향 그래프vs무향 그

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]트리에서 봤듯이 BFS는 큐를 사용시작 노드 start방문큐방문 후 예약예약한 곳 FIFO 접근A(시작 노드)부터 가까운 순으로 탐방

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]트리의 DFS와 원리는 동일

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ](https://leetcode.com/problems/number-of-islands/)눈으로는 바로 알 수 있지만 컴퓨터한테 시켜야한다.어떻게 내가 인식했지라고 생각사고방식을 쪼개서 직관적으로 생각하

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]Graph 활용 입문편Graph 구현DFS 깊이 우선 탐색BFS 너비 우선 탐색(https://leetcode.com/problems/shortest-path-in-binary-matrix/descrip

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]Graph 활용Graph 구현DFS 깊이 우선 탐색BFS 너비 우선 탐색(https://leetcode.com/problems/keys-and-rooms/)그래프로 추상화 할 수 있다.다른 예시DFS -

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]문제에 대한 정답이 될 가능성이 있는 모든 해결책을 "체계적"이고 "효율적"으로 탐색하는 풀이법완전 탐색은 체계적이지 않다.중복 계산해야하는 중복 하위 문제가 발생한다.완전탐색이기때문에 일일히 다 구해줌중복값이

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]위-> 아래로 뻗어나감 (재귀)아래 -> 위로 뻗어나감 (반복문)

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]Top downDP table5층의 입장에서 3층에서 올 수 있는 방법의 수 와 4층에서 올 수 있는 방법의 수를 더한다. 하위 문제로 나눈다.Bottom upmemoization

출처 : 인프런 - 코딩테스트 \[ ALL IN ONE ]Overlapping subproblemProblem을 작은 subproblem으로 분해재귀와 차이점은 subproblem에 중복되는 문제가 발생하고, subproblem의 계산값을 재사용Optimal subst