CS/Algorithm 썸네일형 리스트형 그래프 탐색 알고리즘 - DFS 와 BFS 비교 정의 어떤 한 그래프와 해당 그래프의 시작 정점이 주어졌을때, 시작점에서 간선(Edge, E)을 타고 이동할 수 있는 정점(Node/Vertex, V)을 모두 찾아야 하는 문제이미 지난 정점은 다시 방문하지 않는다. DFS(Depth First Search)그래프에서 한 노드에서 시작해서 모든 노드까지 방문하는 알고리즘 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 깊이가 무한히 깊어지면 스택오버플로우 발생하기에 깊이 제한을 두는 방법으로 처리 가능재귀함수로 짤 경우 Stack 메모리 초과날 수 있기 때문에 주의재귀함수 호출마다 함수와 매개변수를 생성하는 작업이 있기 때문에 시간이 조금 더 걸린다. BFS(Breadth FIrst Search) 다차원 배열에서 각 칸을 방문할 때 .. 더보기 그래프 탐색의 인접행렬과 인접리스트 비교 1. 인접행렬장점행렬을 사용하기 때문에 공간지역성 특징으로 탐색 속도가 더 빠르다. 연결된 노드 중 특정 노드를 탐색하는 접근 속도 O(1) 단점 위 그림처럼 O(N^2) 크기로 모든 노드 간에 간선 유무를 저장하게 된다. 방향성 있는 그래프라면 더욱 공간 낭비가 심해진다. 2. 인접리스트장점 꼭 필요한 간선만 표시하기 때문에 공간을 아낀다.단점 리스트로 관리하에 속도가 느리다. 연결된 노드 중 특정 노드를 탐색하는 접근 속도 O(N) 3. 비교 노드 수보다 간선의 수가 많아질수록 추천 인접행렬 추천간선이 많아질수록 인접리스트의 공간을 아끼는 장점이 줄어든다. 노드의 수가 노드 수보다 많을 때 인접 리스트 추천 공간을 아끼는 장점이 더욱 커진다.기업 알고리즘 테스트에서는? 아직까지는 위 차이를 구분해서.. 더보기 이진 탐색 ( + 하한 lower_bound, 상한upper_bound ) 1. 이진 탐색 정렬된 데이터에서 특정 값을 찾는 알고리즘탐색 범위를 반으로 줄여가며 찾기 떄문에 O(lgN) 으로 빠르게 동작한다. 만약 정렬된 데이터에 찾고자하는 수가 중복으로 있다면 가장 왼쪽의 원소를 찾는 방법을 lower bound 라 하며, 가장 오른쪽 원소의 다음 위치를 반환하는 방법을 upper bound라고 한다. 수열 {1, 2, 3, 3, 3, 4} 에서 3의 lower bound는 인덱스 2, uppder bound는 5다. 비슷하게 데이터를 반으로 분할하는 알고리즘으로 분할정복이 있다.하지만 분할정복은 문제를 부분적으로 해결하는 알고리즘으로 탐색이 목적이 아니다. 2. 탐색 과정탐색 범위 low ~ high를 정하고 low 루프에서 탐색 범위가 low > high 될 때까지 범위를.. 더보기 투 포인터 투 포인터 배열에서 이중 for 문으로 O(N^2) 에 처리되는 작업을 2개 포인터의 움직임으로 O(N) 으로 해결하는 알고리즘 리스트에 순차적으로 접근해야 할 때 2개 점의 위치를 기록하며 처리 이 포인터는 c의 포인터가 아닌 가리키는 역할 머지소트에서 정렬되어 있는 두 리스트의 병합의 기초가 되기도 함. 정렬된 2개 리스트를 포인터를 이용해서 하나의 정렬된 리스트 완성 투 포인터는 블로그 설명들을 보면 구현이 조금씩 다양한 것을 알 수 있는데, 이는 포인터와 구간에 대한 문제정의를 맞게 했으면 구현을 어떻게 했던지 간에 풀 수 있는 것을 알 수 있다. 초기 단계 2개 포인터는 리스트에서 시작 s, 끝 e 를 의미 s와 e는 첫 번째 원소를 가리킴 초기에 s와 e가 동일 원소를 가리키기 때문에 문제에 .. 더보기 다이나믹 프로그래밍 동적프로그래밍이란 동적계획법이라고도 부르는데 문제를 풀기위해 필요한 알고리즘이라기보다 문제를 푸는 방식을 말한다. 동적프로그래밍은 아래와 같은 특성이 있다. 복잡한 문제(complex problem)를 작은 문제(subproblems)로 나눈다. 작은 문제의 해는 복잡한 문제를 풀기위한 부분 해가 된다. 복잡한 문제를 풀기위한 작은 문제들은 자주 등장하기(중복) 때문에 작은 문제가 나타날때 마다 계산할 필요 없이 해를 저장해놨다가 동일한 문제가 나오면 재 활용하여 시간을 절약한다. 그럼 어떤 알고리즘 문제가 나왔을때 이것을 재귀(recursion)로 풀어야할지, 분할 & 정복(divide & conquer)으로 풀어야할지, 그리디 알고리즘(greey algorithm)으로 풀어야할지 아니면 동적프로그래밍.. 더보기 배열 회전 백준에서 Maaaaaaaaaze 문제를 풀고 다른 사람 풀이를 봤었다. 그런데, 배열 회전에서 차이가 있었다 처음 배열 회전 시킬 때, 그냥 한 칸씩 이동하는 과정을 여러 번 반복했었다. 하지만, 회전의 특징? 을 고려하면 더 빠르고 깔끔하게 코드를 짤 수 있었다. 말로 설명하는 것보단 그림을 보는 것이 바로 이해하기 좋기 때문에 그림으로 대체.. 이 그림대로 모든 좌표 ( y, x) 를 ( x, height - y - 1 )로 바꾸면 간단하게 90 회전한 배열을 구할 수 있다. 사실 이걸 몰라도 어떻게든 회전할 수 있지만, 이 방법을 알아두는게 좋을 것 같아 따로 정리했다. 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 .. 더보기 Binary Search Tree binary tree에서 검색 효율이 좋은 자료구조다. 장점 이진 탐색과 링크드 리스트 자료구조를 결합한 형태로 각 장단점을 보완한 것이 BST 이진탐색 : O(logn) 으로 탐색한다. 매번 원소를 비교 시, 비교 대상이 절반으로 줄어든다. 링크드 리스트 : 추가 삭제 시 O(1) 시간 복잡도 트리 높이에 비례한다. 따라서, balanced/unbalanced인지에 영향을 받는다. balanced경우, 탐색이 O(logn)이지만, unbalanced 되면 O(n)이 된다. 이 경우, 다시 rebalancing이 필요하다. 이 기법을 갖는 자료구조가 AVL, red black tree 특징 1 모든 key값은 unique. 그렇지 않으면 조건 2,3 번에 위배된다. 그래서 중복된 key입력이 보이면 co.. 더보기 tree 자료구조 tree 자료구조 tree는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조다. 큐, 스택, 리스트와 같은 서형 자료구조와 다르다. parent, child로 노드간의 상위/하위 노드를 표현한다. root노드를 제외한 나머지 노드는 단 하나의 부모노드만 갖는다. 1 tree에는 사이클이 없다. 2 모든 노드는 모두 연결되어 있다. 3 임의의 노드에서 다른 노드로 가는 경로가 유일하다. 쓰임 1 현실 세계 개념을 추상화 2 탐색형 자료구조 구성 Node(노드) : tree를 구성 요소 Edge(간선) : Node간에 연결하는 선 Root Node : 트리에서 최상위 노드 Leaf Node : 트리에서 최하위 노드들로 다른 하위 노드가 없다. Internal Node : Le.. 더보기 이전 1 2 다음
