전체 글

조건 문제가 더 작은 문제로 쪼개질 수 있을 때 더 작은 문제의 solution으로 더 큰 문제의 solution을 구할 수 있을 때 : 최적 부분 구조 Optional substructure subproblem들이 겹칠 때 → memoization으로 줄일 수 있음. :중복되는 부분 문제 Overlapping subproblem 접근방법 approach/Technique top -down bottom - up 하향식 상향식 표현1 top-down bottom-up 표현2 memoization tobulation 가능한 에러 recur depth error 구현방식 recursion loop 특징1 직관적 비직관적 빠르기 비교적 느림 빠름 속도차이 이유 함수 호출이 많음 불필요한 함수 호출이 x memo..

Dijkstra 다익스트라 Floyd-Warshall 플로이드 워셜 어떤 문제에 사용할까? 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 노드/간선 갯수 적을 떄 사용 사용처 가중 그래프(weighted graph)에서 하나의 정점으로부터 시작하여 각각의 노드로 가는 각각의 최단경로를 찾는 데 효율적. 가중 그래프에서 정점간 모든 쌍 사이에서 가장 짧은 경로를 찾는데 적합함. (all-pairs shortest path algorithm) source - usecase a single-source shortest path algorithm a multi-source shortest path algorithm 정점 방문 방..

학습 자료 (레퍼런스) https://www.youtube.com/watch?v=xeSz3pROPS8 https://www.geeksforgeeks.org/topological-sorting/ 위상정렬 그래프 정점의 선형적 정렬(ordering)으로, vertex U에서 V로 가는 방향성이 유지된 채 정렬되는 것. 즉, U가 V를 가리킨다면(향한다면) 위상정렬 시 U는 언제나 V보다 먼저 등장해야 한다. 왜냐하면 U를 거쳐야 V를 갈 수 있기 떄문이다. 방향성이 있고 싸이클이 없는 그래프인 DAG(directed acycled graph) 에서만 가능하다. 선형 시간 복잡도를 보임 (O(V+E)) 결과물은 unique하지 않다. (레벨간의 순서 stable은 보장하지만, 결과물이 언제나 동일하지 않다.)..

Memory structure Code segment 실행할 프로그램의 코드와 명령어가 디스크에서 로드되어 저장되는 영역입니다. 이 영역에 저장된 명령어를 CPU가 처리합니다. 아래 두 region을 Data segment local and static data 컴파일 시간 동안 프로그램의 전역 변수와 정적 변수의 주소가 설정되어 저장됩니다. 프로세스 수명 동안 살아있으며, 프로그램 종료 시 사라집니다. global / static 영역은 엄밀히 말해 아래의 영역입니다. Initialized data segment(초기화된 데이터 세그먼트) 기본값으로 선언된 변수가 저장됩니다. bss 아직 값이 할당되지 않은 정적으로 할당된 변수가 포함된 object file, excecutable, assembly l..

DFS vs BFS, 언제 무엇을 써야 할까? 어느 탐색 전략이 좋은지는 그래프의 모양에 따라 효율이 갈리니 모양과 용도를 보고 선택하자! DFS>BFS DFS가 BFS보다 우월한 성능을 낼 때 높은 분기 계수(branching factor)를 가진 두껍게 연결된 그래프에서(thickly connected graphs DFS가 BFS보다 더 좋은 성능을 낸다.[같은 뜻의 비슷한 표현] 그래프의 간선이 많고(=밀도가 높다/dense하다) 평균 인접 노드 수가 노드 수에 비해 높다면 너비 우선 검색은 긴 대기열을 가진다. 그에 비해 DFS는 적은 스택을 가지므로 DFS가 좀 더 성능이 좋을 것이다.) 해답(solution)이 가장 먼 자식 노드에 있을 것 같으면 DFS가 더 좋은 선택이 된다. BFS>DFS..

스택 학습 사이트 leetcode 스택(Stack) 자료구조 개념 | 배열 Vs 연결 리스트 | LIFO(Last In First Out) | push | pop | top | Overflow | Underflow 스택의 개념 :: LIFO 원칙 스택은 "Last-In, First-Out" 원칙을 따르며, 마지막으로 추가된 항목은 가장 먼저 제거되는 형식의 자료구조이다. 스택의 연산 Push(item): 스택 상단에 요소를 추가 Pop(): 스택에서 상단 요소를 제거 Peek()/Top(): 요소를 제거하지 않고 스택 상단에 있는 요소를 봄 IsEmpty(): 스택이 비어 있는지 확인 push pop 삽입 삭제(인출) 스택의 끝 가장 끝 요소 스택과 데이터 구조 배열 배열은 같은 타입의 요소들의 고정된 ..