알고리즘 (12) 썸네일형 리스트형 [알고리즘 이론] 2. 그리디 알고리즘 안녕하세요? 닉네임 간편입니다. 이번 시간에는 그리디 알고리즘에 대해서 알아보겠습니다. 1. 그리디란? 탐욕법으로도 불리는 그리디(Greedy) 알고리즘은 답을 도출하기 위해서 수행되어야 할 동작들을 여러 부분으로 나눈 후, 각 부분마다 최선의 경우만 선택하는 알고리즘입니다. 즉, 어떤 선택을 할 때 지금 당장의 경우만 고려해 가장 최적의 답을 찾아내는 알고리즘입니다. 예를 들어 목표 액수를 지불할 때 필요한 최소 화폐 개수를 구하는 문제를 생각해볼 수 있습니다. 우리에게 5000원, 1000원, 500원, 100원이 있고, 7000원을 지불해야 한다고 가정하겠습니다. 그렇다면 이때 5000원을 선택하면 가장 금액이 높으면서 가장 적은 화폐 개수로 지불할 수 있으므로, 5000원을 선택해 지불합니다. 그.. [알고리즘 이론] 1. 브루트포스 알고리즘 안녕하세요? 닉네임간편입니다. 이번 시간에는 브루트 포스 알고리즘에 대해 알아보겠습니다. 1. 브루트 포스란? 브루트 포스(Brute Force)는 짐승과 힘을 뜻하는 단어를 결합한 것으로, 말 그대로 짐승처럼 원시적으로 가능한 모든 경우를 탐색하는 것입니다. 이를 무차별 대입이라고도 합니다. 예를 들어 전화번호부에서 원하는 이름을 찾고 싶다면, 전화번호부 전체에서 하나씩 이름을 살펴보며 모든 곳을 다 탐색하는 것이 있겠습니다. 이렇게 가능한 모든 곳을 탐색하거나 가능한 모든 조합을 만드는 알고리즘을 완전 탐색(exhaustive search)이라고 합니다. 이 완전 탐색 기법을 사용하는 방법에는 일반 브루트 포스, 그래프 자료구조에 사용되는 DFS와 BFS, 재귀, 순열, 비트 마스크가 있습니다. 다른.. [백준] 17136 색종이 붙이기 파이썬(Python3) 풀이 안녕하세요? 닉네임간편입니다. 이번 시간에는 색종이 붙이기 문제를 풀어보겠습니다. [문제 링크] https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 1. 접근 방식 1x1부터 5x5까지의 색종이로 모든 1을 덮는데 필요한 색종이의 최소 개수를 찾아야 합니다. 따라서 BFS 방식으로 접근할 수 있지만, 매번 동작을 반복할 때마다 배열의 상태를 깊은 복사 하여 전달해야 한다는 점 때문에 시간적, 공간적으로 효율적이지 않습니다. 물론 다른 방식.. [백준] 7576번 토마토 파이썬(python) 풀이 안녕하세요? 닉네임간편입니다. 이번 시간에는 토마토 문제를 풀어보겠습니다. [문제 링크] https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 1. 접근 방식 우선 이 문제에서 요구하는 것이 주어진 토마토가 모두 익을 수 있는 최소 일수를 구하는 것이므로, 너비 우선 탐색(BFS)으로 접근하면 되겠습니다. 또한 익은 토마토는 인접한 익지 않은 토마토를 익게 하기 때문에, 상하좌우 방향키처럼 토마토를 익게 하면서 모든 토마토를 익게 하.. 이전 1 2 다음
