지민 개발 블로그

DFS/BFS 는 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘이다. 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS가 있다. DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다. 자료구조란 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미한다. 그중 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다. 삽입(Push): 데이터를 삽입한다. 삭제(Pop): 데이터를 삭제한다. 스택 (~=박스 쌓기) 스택은 선입후출(First In Last Out)구조 또는 후입선출(Last In ..

그리디 알고리즘이란, 단순하지만 강력한 문제 해결 방법이다. 이 유형은 "탐욕법"이라 소개되기도 하는데, 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 "탐욕적"이라는 말은 '현재 상황에서 지금 당장 가장 좋은 것만 고르는 방법"을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 출제 동향 이 유형은 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있다. 다만, 그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓기 때문에, 다익스트라 알고리즘과 같이 특이 케이스를 제외하고는 단순 암기를 통해 모든 문제를 대처하기는 어렵다. 그리디 알고리즘 유형의 ..

이진 탐색이란, 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘이다. 이진탐색 vs 순차탐색 1) 순차탐색 순차탐색이란, 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 즉, 이진탐색과는 구분되는 방법이다. 순차탐색은 주로 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용된다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있다는 장점이 있다. 구현도 매우 간단하다. /*논외로, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서는 순차 탐색이 수행된다.*/ 2) 이진탐색 이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 이진 탐..

Brute Force Algorism은 "완전탐색알고리즘"으로 Brute는 "무식한"을 뜻한다. 무식하다? : "가능한 모든 경우의 수를 '모두' 탐색하면서 요구조건에 충족되는 결과만을 가져온다"라는 특징에 존재한다. *해가 존재할 것이라고 예상되는 영역을 모두 탐색!!* Solution step 1.주어진 문제를 선형으로 구조화하기 step 2.구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다. step 3.구성된 해를 정리한다. 브루트 포스 문제의 종류 자료의 구조가 1) 선형구조 ->순차 탐색 2) 비선형구조 -> BFS, DFS 활용 문항 #2798_블랙잭 Solution) 1. 모든 Card를 List안에 넣는다. 2. Itertools 의 Combination함수를 활용해서 3개..