[나만의 노트] 코딩 테스트

묘공노트정오표(https://docs.google.com/spreadsheets/d/1BPAmoaDmn-RRBjk8O468M_v3WnI46UaX0N_0vs0pZCk/edit디스코드카카오톡 오픈 채팅방묘공파티

시간 복잡도 : 알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미빅오 표기법 : 최악의 경우 시간 복잡도를 표현하는 방법코딩 테스트에 활용하는 방법 : 빅오 표기법을 활용해서 해당 알고리즘을 적용했을 때 제한 시간 내에 출력값이 나올 수 있

선입후출(FILO;First In Last Out) : 먼저 들어간 것이 마지막에 나오는 규칙push : 스택에 삽입하는 연산pop : 스택에서 꺼내는 연산ADP(Abstract data type; 추상 자료형) : 인터페이스만 있고 실제로 구현은 되지 않은 자료형스택

해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조단방향으로 동작찾고자 하는 값을 O(1)에서 바로 찾기 가능비밀번호 관리 : 해싱한 비밀번호를 저장데이터베이스 인덱싱 : 효율적으로 검색블록체인 : 이전 블록의 해시

순서와 중복이 없는 원소들을 갖는 자료구조이미지 분할도로 네트워크 구성최소 신장 트리 알고리즘 구현게임 개발클러스터링 작업집합은 배열을 활용한 트리로 구현집합 알고리즘에 많이 쓰이는 연산(합치기와 탐색)

데이터를 저장하고 탐색하기에 유용한 구조트리의 특성을 활용하는 분야 : 인공지능, 자동 완성 기능, 데이터베이스트리를 구성하는 노드노드를 연결하는 에지부모-자식, 형제 관계를 가지는 노드자식이 없는 말단 노드아래로 향하는 간선의 개수, 차수배열이나 포인터로 구현 가능아

노드와 간선을 이용한 비선형 데이터 구조보통 데이터 간의 관계를 표현하는데 사용데이터를 노드로, 노드 간의 관계나 흐름을 간선으로 표현간선은 방향이 있는 경우, 없는 경우 모두 가능관계나 흐름에서 정도를 표현할 필요가 있다면 가중치 추가하여 표현흐름을 표현하는 방향성(

12장. 백트래킹 12-1. 백트래킹과 백트래킹 알고리즘 개념 1) 백트래킹(backtracking)이란? 어떤 가능성이 없는 곳을 알아보고 되돌아 가는 것 2) 백트래킹 알고리즘이란? 가능성이 없는 곳에서는 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘 3)

사용자가 정의한 순서로 데이터를 나열하는 것원하는 데이터를 쉽게 찾는 것 가능데이터의 전체 영역에서 정렬된 영역과 정렬되지 않은 영역으로 구분정렬되지 않은 영역의 값을 정렬된 영역의 적절한 위치에 넣으며 정렬시간 복잡도 : 최악인 경우 O(N^2), 최선인 경우 O(N

시뮬레이션 : 문제에 주어진 상황을 완벽하게 이해하고 이를 코드로 구현하는 과정다른 알고리즘은 성능에 중점을 둔 반면, 시뮬레이션은 구현에 중점접근방법1) 하나의 문제를 최대한 여러 개로 분리접근방법2) 예외 처리가 필요하다면 독립 함수로 구현시뮬레이션 문제에 많이 활

전체 문제를 한 번에 해결하는 것이 아니라 작은 부분 문제들을 해결하고 이것들을 활용하여 전체 문제를 해결하는 방법동적 계획법을 효율적으로 활용하기 위해 충족 되어야 하는 조건큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제 반복 등장큰 문제의 해결책은 작은 문제의

문제 해결 과정에서 결정 순간마다 눈 앞에 보이는 최선의 선택을 하며 선택은 번복하지 않는 알고리즘지역 최적해 추구(전체에서의 최적해 보장 X)아래와 같은 특정 상황에서 최적해 보장최적 부분 구조 : 부분해를 푸는 과정이 최적해를 구하는 과정과 일치그리디 선택 속성 :