https://heo-it-til.tistory.com/48 [백준] 웜홀 : 1865 Python 이 문제를 봤을 때, 플로이드 와샬로 풀 수 있을까 고민했지만 tc의 개수가 5개, N의 크기가 500인 것을 보고 플로이드와 샬을 포기하고, 음의 가중치라는 점에서 벨만 포드 알고리즘을 시도했다. heo-it-til.tistory.com
CS 기본/자료구조
이분 탐색(binary Search) 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 데이터가 정렬되어야지 사용할 수 있음. 시간복잡도 O(log n) start, mid, end 가 존재 ex) 17, 28, 43, 67 , 88, 92, 100 에서 43을 찾아보자 여기서 끝나면 아쉽다. 위 같은 경우는 쉽지만 이분 탐색 하면 항상 헷갈리는 조건들이 존재 요약 [s, e]가 Check(s) != Check(e)가 되도록 구간을 설정 while (s + 1 < e)동안 mid = (s + e) / 2에서 Check(mid) = Check(s)라면 s = mid, 아니라면 e = mid 구한 경계에서 답이 s인지 e인지 생각해보고 출력 (1에서 경계는 항상 [s, e] 내에 ..
본 포스팅은 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다. 비선형 자료구조 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조 일반적으로 트리나 그래프를 말함 그래프(Graph) 정점과 간선으로 이루어진 자료구조 https://ltsgod.tistory.com/147 그래프 이론 그래프 데이터(노드)들을 잘 정리하는(노드간의 관계를) 방법 중 하나 데이터들과 그 관계를 보여주는 방법 중 하나 서로 연관 있는 노드의 집합 G = (N, E) 네트워크 형태의 관계를 보여주기에 적 ltsgod.tistory.com 트리 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터 집합 https://ltsgod.tistory.com/125 트리(Tree), 이진..
그래프 데이터(노드)들을 잘 정리하는(노드간의 관계를) 방법 중 하나 데이터들과 그 관계를 보여주는 방법 중 하나 서로 연관 있는 노드의 집합 G = (N, E) 네트워크 형태의 관계를 보여주기에 적합 용어 노드(정점, 꼭짓점) 변(간선, 선) 차수(degree) : 나한테 몇개 연결되어 있나 루프(loop): 자기자신한테 돌아오는것 그래프의 종류 방향/무방향(directed/undirected) 그래프 순환/비순환(cyclic/acyclic) 그래프 가중/비가중(weighted/unweighted) 그래프 무방향 그래프의 최대 변 개수 모든 노드가 연결되어 있는 경우 그래프의 표현 방법 인접 행렬 N * N 행렬 G[N][N] N: 그래프 G안에 있는 노드수 서로 인접한 노드를 표현 i → j로 향하는..
본 포스팅은 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다. 선형 자료 구조 요소가 일렬로 나열되어 있는 자료 구조 연결 리스트(Linked List) 데이터를 감싼 노드를 포인터가 연결해서 공간적인 효율성을 극대화 시킨 자료구조 삽입, 삭제 : O(1) 탐색 : O(n) 단일 연결 리스트: next 포인터만 가짐 이중 연결 리스트: next 포인터와 prev 포인터를 가짐 원형 이중 연결 리스트: 이중 연결 리스트와 같지만 마지막 노드의 next포인터가 헤드 노드를 가리키는 것 배열(Array) 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있음. 인접한 메모리 위치에 있는 데이터를 모아놓은 집합 탐색: O(1) 삽입, 삭제 : O(n) 벡터(vector) 동적으로 요소를 할당할 수..
본 포스팅은 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다. 자료구조(Data Structure) 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합 빅오 표기법 시간 복잡도: 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계 입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타냄 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지항을 다 없앰. 시간복잡도 효율적인 코드로 개선하는 데 쓰이는 척도 공간 복잡도 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함. 자료 구조에서의 시간 복잡도
AVL 트리(Adelson-Velsky and Landis tree) BST 트리의 경우 최악의 경우 O(n)의 시간 복잡도를 보이는데 이것을 방지하고자 스스로 균형을 잡는 이진 탐색 트리 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이 난다. 레드 블랙트리와 비슷하나 BF(balance Factor)를 통해 균형을 잡는다. 레드-블랙 트리(red-black tree) 각 노드가 레드 혹은 블랙(노드에 저장하는 데이터 X) 그냥 1비트 짜리 정보 스스로 균형을 잡는(self-balancing) 트리 최소한의 트리 높이를 보장 균형을 잡는 시점-> 삽입, 삭제 그 외 연산은 BST와 동일( 탐색 속도는 더 빠르다) C++ STL의 set, multiset, map, and multimap 이 이 레드 ..
트리 계층적 구조 표현 트리 관련 용어 노드(node): 실제로 저장하는 데이터 루트(root) 노드: 최상위에 위치한 데이터 시작 노드 모든 노드와 직간접적으로 연결됨 리프(leaf) 노드: 마지막에 위치한 데이터들 더 이상 가지 치지 않음 부모-자식: 연결된 노드들 간의 상대적 관계 자식은 없을 수도, 많이 있을 수도 부모는 언제나 1개 트리가 그래프보다 더 제약이 있다. 조부모. 삼촌(uncle). 형제자매(sibling) 등도 있다. 깊이(depth): 노드 -> 루트 경로의 길이 높이(height): 노드-> 리프 경로의 최대 길이 레드 블랙트리에서 사용 하위 트리(subtree): 어떤 노드 아래의 모든 것을 포함하는 트리 재귀적: 하위 트리 그 자체가 트리 트리의 속성 부모와 자식 모두 노드..
Hash Table key, value로 데이터를 저장하는 자료구조 빠르게 검색가능한 자료구조 -> 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문 각각의 key값에 대해 해시함수를 적용해 배열의 고유한 index를 생성하고, index를 활용해 값을 저장하거나 검색 저장/삭제/조회 -> O(1) 해시 함수 임의의 크기를 가진 데이터를 '고정크기'의 값에 대응하게 하는 함수 함수이기 때문에 입력값이 같은면 출력값은 항상 같다. 입력값이 달라도 출력값이 다를 수 있다. 해시 값 어떤 데이터를 해시함수에서 넣어서 나온 결과 해시 충돌 입력값이 같은데 출력값이 같은 경우 없을 수록 좋다 최악의 경우 검색속도 O(n)으로 느려질 수 있다. 1. Seperate Chaining(분리 연결법) 같은 공간에..
