분류 전체보기 (89) 썸네일형 리스트형 [알고리즘 이론] 5. 너비 우선 탐색(BFS) 안녕하세요? 닉네임간편입니다. 이번 시간에는 너비 우선 탐색에 대해 알아보겠습니다. 1. 너비 우선 탐색이란? 너비 우선 탐색(Breadth-First Search)은 시작점에서 가까운 정점 순서대로 탐색을 하는 알고리즘입니다. 위 그림을 예시로 들어 설명하겠습니다. 시작점은 정점 1이며, 동일한 거리에 있다면 왼쪽부터 방문하도록 하겠습니다. 1) 1 -> 2 -> 3 정점 1에 인접한 정점 2와 3을 먼저 방문합니다. 정점 3을 방문한 이후 정점 1에 인접한 간선이 없으므로 해당 단계의 탐색을 종료합니다. 2) 3 -> 4 -> 5 -> 6 정점 2와 3에 인접한 정점을 왼쪽부터 순서대로 방문합니다. 정점 6을 방문한 이후 정점 2, 3에 인접한 간선이 없으므로 이 단계의 탐색을 종료합니다. 3) 6 .. [알고리즘 이론] 4. 깊이 우선 탐색(DFS) 안녕하세요? 닉네임간편입니다. 저번 시간에는 그래프에 대해 알아보았습니다. 이번 시간에는 그래프를 이용한 탐색 알고리즘을 배워보겠습니다. 그래프의 탐색 알고리즘에서 가장 많이 사용되는 것에는 깊이 우선 탐색과 너비 우선 탐색이 있으며, 이번 시간에는 깊이 우선 탐색에 대해 알아보겠습니다. 1. 깊이 우선 탐색이란? 깊이 우선 탐색(Depth First Search)은 그래프의 모든 정점을 발견하는 방법 중 하나로, 이름 그대로 최대한 깊이 탐색한 이후 더 이상 탐색할 것이 없다면 그 이전으로 돌아가 탐색을 이어가는 것입니다. 위 그림을 예시로 설명하겠습니다. 현재 탐색을 정점 1에서부터 시작한다고 하겠습니다. 또한 인접한 간선이 여러 개일 경우 왼쪽을 먼저 탐색한다고 설정하겠습니다. 1) 1 -> 2 정.. [알고리즘 이론] 3. 그래프 안녕하세요? 닉네임간편입니다. 이번 시간에는 많이 사용되는 자료구조인 그래프에 대해 알아보겠습니다. 1. 그래프란? 그래프(graph)는 일종의 연결 관계를 나타내는 것으로써, 위 그림처럼 사람 간의 관계나 지하철 노선도 등이 현실에서 사용되는 그래프의 예시입니다. 수직적인 구조가 아니기 때문에 다양한 구조를 표현할 수 있어 많이 사용되는 자료구조입니다. 그래프는 기호로 G(V, E)로 표현되며 이때 V는 정점(vertex)을 의미하고 E는 간선(edge)을 의미합니다. 정점은 어떤 지점을 말하는 것으로, 위 그림에서 사람에 해당됩니다. 간선은 정점을 연결한 선으로, 위 그림에선 점선이 됩니다. 그래프는 정점과 간선들로 구성되어있으며, 정점이나 간선에 가중치 등을 부여해 다양한 방식으로 활용할 수 있습니.. [알고리즘 이론] 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)으로 접근하면 되겠습니다. 또한 익은 토마토는 인접한 익지 않은 토마토를 익게 하기 때문에, 상하좌우 방향키처럼 토마토를 익게 하면서 모든 토마토를 익게 하.. [비전공자도 만들 수 있는 블루투스 무드등] 16. 3D 프린팅 외관 제작 안녕하세요? 닉네임간편입니다. 이번 시간에는 3D 프린팅을 통해 무드등 외관을 만들어보겠습니다. 1. 도안 3D 프린팅을 하기 위해선 우선 도안이 필요합니다. 저는 앞서 소개했던 사이트인 팅커캐드 사이트에서 도안을 제작하였습니다. https://www.tinkercad.com/ Tinkercad | From mind to design in minutes Tinkercad is a free, easy-to-use app for 3D design, electronics, and coding. www.tinkercad.com A. 사용법 이 화면은 첫 화면에서 상자를 하나 만든 화면입니다. 사용법은 정말 간단하기 때문에 중요한 부분부터 차근차근 설명드리겠습니다. 1) 왼쪽 레이아웃 1) 네모난 박스를 클릭한 .. 이전 1 ··· 6 7 8 9 10 11 12 다음
