이번 주 알고리즘 스터디 주제는 dfs && bfs였다. 워낙 방대하고 나에게는 어려운 부분이라 그래프부터 정리를 해보려 한다. 그래프 그래프는 어떤 자료나 개념을 표현하는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조이다. 이 때, 정점의 위치나 간선의 순서는 그래프의 정의에 포함되지 않는다. 따라서 다른 모양임에도 같은 그래프를 표현할 수도 있다. 그래프의 종류 그래프의 정의는 위처럼 간단하지만, 표현하고자 하는 대상에 따라 여러가지 변형된 형태를 가질 수 있다. 정점이나 간선에 추가적인 속성을 부여할 수도 있고, 제약을 둘 수도 있다. 대표적으로는 방향 그래프가 있으며, 각 간선이 방향이라는 새로운 속성을 가진다. 반대로 무향 그래프는 각 간선에 방향이 없는 그래프를 뜻한다. 또..
이번 주는 그리디 알고리즘에 대해 문제를 풀어보았다. 한 주간 풀어볼 문제는 다음과 같았다. 필수로 풀어야 하는 문제들 ATM 게임을 만든 동준이 팰린드롬 만들기 주식 통나무 건너뛰기 추가적으로 풀어볼만한 문제들 가장 긴 증가하는 부분 수열 2 입국심사 스터디원들이 모두 다 잘 풀어왔고, 각자 코드 리뷰를 하면서 서로 부족한 부분을 채워주는 시간을 가졌다. 그리디 알고리즘 그리디 알고리즘은 단순하지만 강력한 알고리즘이다. 현재 상황에서 지금 당장 할 수 있는 최선의 선택을하는 방법을 의미하며, 현재의 선택이 향후에 미치는 영향에 대해서는 고려하지 않는다. 위의 그림을 보면, 서울에서 부산까지 갈 수 있는 최적의 경로를 찾는다고 할 때, 대구를 중간점으로 서울 - 대구의 가장 최적 경로 (200km) + ..
이분 탐색 이분탐색은 가장 기초적인 알고리즘으로 꼽힌다. 검색 범위를 줄여 나가면서 원하는 데이터를 찾는 알고리즘이다. 위와 같은 방식으로 순차적으로 리스트를 순화하는 for문이나 while문보다 빠르게 탐색할 수 있다. 이 방식이 매우 유용한 이유는 for문을 통한 반복문으로 리스트 탐색을 수행할 경우 시간복잡도가 O(n)이라면, 이분탐색을 통해서는 O(lb n)의 복잡도를 가진다. O(lb n)이라는 말은, int형의 크기(-2,147,483,648 ~ 2,147,483,647)에서 탐색을 한다면, 약 43억개의 원소가 담긴 리스트를 탐색해야하는 상황에서, for문을 통한 탐색은 최악의 경우 43억개를 전부 탐색하는 경우가 될 것이다. 하지만 이진탐색을 활용한다면, 탐색 범위를 반으로 나누며 범위를 ..
