8주차의 문제 주제는 트리였다. 문제 선정에 있어, 트리 구조에 대해 배워보고싶기도 했고, 트리 카테고리에서 문제를 많이 풀어본 경험이 없어서 선정했다. 그런데, 생각보다 알고리즘 문제를 푸는 입장에서는 트리를 구현해서 문제를 해결하는게 아닌, 다른 방법들을 통해서 문제를 푸는게 더 효율적이었다. 대체로 그래프 쪽 문제와 많이 연관되어있던것 같았다. BOJ.2078 무한이진트리 문제 링크 BOJ.11725 트리의 부모 찾기 문제 링크 BOJ.1240 노드사이의 거리 문제 링크 BOJ.15805 트리나라 관광 가이드 문제 링크 BOJ.22856 트리 순회 문제 링크
이번 주 알고리즘 스터디 주제는 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억개를 전부 탐색하는 경우가 될 것이다. 하지만 이진탐색을 활용한다면, 탐색 범위를 반으로 나누며 범위를 ..
