본문 바로가기

CS45

분할 정복 분할 정복 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법입니다. 대표적 예는 정렬 알고리즘 중에서 퀵, 합병 정렬과 이진 탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제가 대표적입니다. 분할정복법의 설계전략? 분할 : 문제 사례를 하나 이상의 작은 사례로 분할(Divide) 합니다. 정복 : 작은 사례들을 각각 정복(Conquer)한다. 작은 사례가 충분히 작지 않은 재귀를 사용합니다. 병합 : 필요하다면, 작은 사례에 대한 해답을 통한(Combine)하여 원래 사례의 해답을 구합니다. 분할정복법의 장단점? 장점 Top-down 재귀 방식으로 구현하기 때문에 코드가 직관적입니다. 문제를 나누어 해결한다는 특징 상 병렬적으로 문제를 해결 단점 재귀 함수 호출로 오버헤드가 발.. 2022. 6. 8.
투 포인터 (Two Pointer) 투포인터 정렬된 리스트를 두 개의 포인터를 가지고 순차적으로 접근하면서, 두 포인터 구간의 값이 타겟 값과 같을 때까지 포인터를 조작하는 기법을 말합니다. 투포인터 알고리즘에 대해서는 검색만 해도 어떻게 로직이 돌아가는 지 쉽게 이해할 수 있을 거 같아서 저는 두 개의 포인터를 함께 활용할 때 얻을 수 있는 이점이 무엇인 지에 대해서 글을 써볼까 했습니다. 사실 이점은 1차원 배열을 한 번의 루프로 문제의 원하는 결과를 얻을 수 있다는 점입니다. 코딩테스트 문제마다 다르겠지만, 저는 수들의 합2(2003) 문제를 가지고 비교를 해보았습니다. 결과는 사실 복잡도에서 큰 차이를 못느꼈습니다. 하지만, 새로운 알고리즘 유형이니 익힐 필요성은 있다고 생각했습니다. 그리고 투포인터 알고리즘은 구현 방식이 문제 별.. 2022. 6. 7.
이진탐색 == 이분탐색 (Binary Search) 이란? 이진탐색 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. (정렬된 배열, 리스트에 적합한) 배열의 중앙에 있는 값을 조사하여, 찾고자하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는 지를 알아내어 탐색의 범위를 반으로 줄입니다. 찾고자 하는 값이 속해있지 않은 부분은 전혀 고려할 필요가 없기 때문에, 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄일 수 있습니다. 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않고, 주로 고정된 데이터에 대한 탐색에 적합합니다. 이진탐색의 시간 복잡도 한 번 확인할 때마다 확인하는 원소의 개수가 절반 씩 줄어든다는 점에서 시간 복잡도가 O(logN)입니다. 예시 1. 10억 명의 어떠한 이름이 저장되어있는 배열에서 이진 탐색을 이용해 특정한 이름을 찾는 경.. 2022. 6. 3.
http VS https 에 대하여 오늘의 주제 http 와 https 에 대한 내용은 http에한 개념적인 내용은 생략하고, http를 알고 있다는 가정하에 설명을하도록 하겠습니다. http 에 대한 내용이 궁금하시거나? 잘 모르시겠다면 아래에 제가 정리한 블로그 글을 읽고 오시면 좋을 거 같습니다 https://devnuts.tistory.com/71?category=1003683 HTTP 란? HTTP(HyperText Transfer Protocol)는 인터넷에서 데이터를 주고 받을 수 있는 프로토콜입니다. 이번 주제를 알아보기 전에, 프로토콜에 대해서 먼저 설명하도록 하겠습니다. 프로토콜 공통 데이터 교환 devnuts.tistory.com https://devnuts.tistory.com/72?category=1003683 HT.. 2022. 4. 30.
TDD란? 테스트 주도 개발(Test Driven Development) 에 대한 프로그래머들의 의견은 늘 엇갈렸습니다. TDD의 실효성을 업무로 경험한 사람들은 TDD를 더 효과적으로 실무에 적용하기 위해 고민을 합니다. 반면, 회사마다 일하는 방식이나 처한 업무 환경이 다르고 편차가 있다보니, 일각에서는 실무에서 TDD를 사용하는 건 사실상 현실과 괴리감이 크다는 의견도 있습니다. 지금부터 TDD가 무엇인지 알아봅시다. TDD 실제 동작하는 코드를 작성하기 전에, 테스트를 먼저 작성함으로 개발의 흐름을 테스트로 끌고 가는 개발 방법입니다. 개발자는 먼저 자신이 구현할 기능에 대해서 테스트를 작성하고, 테스트를 통과하는 코드를 작성함으로 수행 결과가 보증된 소프트웨어를 개발해 갑니다. 반복 테스트를 이용한 소프트.. 2022. 4. 30.
최단거리 문제에 대한 고찰 최단 경로 문제는 가중치 없는 그래프에서는 보통 두 정점을 잇는 가장 적은 간선의 개수를 뜻합니다. 반대로 가중치가 있는 그래프에서는 두 정점을 잇는 간선들의 가중치의 합 중 최소 가중치 합을 의미합니다. 알고리즘 공부하고, 코딩테스트 문제를 접하다보면? 가중치 없는 그래프(unweighted graph)인 경우 BFS를 사용하고, 가중치가 0과 1이 존재할 때 역시 BFS를 사용한다고 생각합니다. 그리고 가중치가 여러 개가 존재한다면 다익스트라 알고리즘을 사용하라고 합니다. 이번 주제에선, 왜 최단거리에선 DFS를 사용하지 않고 BFS를 사용하는 지? 와 간선이 0과 1일 때는 다익스트라 알고리즘을 사용하기보단, 0-1 알고리즘을 사용하는 지? 에대한 설명을 드릴 생각입니다. 최단 경로를 탐색할 때 D.. 2022. 4. 25.
너비 우선 탐색(Breadth-First-Search) BFS 그래프 전체를 탐색하는 방법 중 하나로, 루트 노드 또는 다른 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법입니다. 시작 정점을부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 순회함으로 써 노드를 넓게(wide)하게 탐색을 합니다. 더 설명하자면, BFS는 해를 찾아서 조직적으로 트리의 모든 노드들을 검사하는 무정보 탐색(Uniformed search)입니다. 달리 말하자면, 목표에 대한 고려없이 목표가 발견될 때까지 전체 트리 또는 그래프를 전부 탐색하고, BFS는 휴리스틱을 사용하지 않습니다. (반대로 휴리스틱을 사용하는 알고리즘은 ex) Greedy best-first search 또는 A*) 👇 search 의 두 분류 더보기 Uniformed search .. 2022. 4. 24.
트리의 지름 구하기 [증명] 트리의 지름 트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은, 먼 두 정점을 연결하는 경로를 의미합니다. 선형 시간안에 트리에서 지름을 구하는 방법은 아래 Flow를 기억해두시면 좋습니다. 트리에서 임의의 정점 x를 잡습니다. 정점 x에서 가장 먼 정점 y를 찾습니다. (dfs / bfs 사용) 정점 y에서 가장 먼 정점 z를 찾습니다. (dfs / bfs 재사용) 이렇게 위 flow 대로 생각하면, 트리의 지름은 정점 y와 정점 z를 연결하는 경로가 됩니다. 여기서 이렇게하면 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 일컫게 됩니다. 증명을 하자면, 트리에서 정점 u와 정점 v를 연결하는 경로가 트리의 지름이라고 가정하겠습니다. 임의의 정점 x를 정하고, 정점 x에서 가장 먼 정점 y.. 2022. 4. 22.

티스토리툴바