본문 바로가기

알고리즘24

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 의 개념과 차이 알고리즘을 풀다보면 그래프를 탐색해야하는 상황이 많이 발생한다. 그래프를 탐색하는 방법에는 크게 깊이 우선 탐색 (DFS)과 너비 우선 탐색 (BFS)가 있다. 두개의 알고리즘을 그림으로 보면 다음과 같다. 1. 깊이 우선 탐색 (DFS) ✅ 깊이 우선 탐색의 개념 한 노드로 부터 시작해서 다음 분기(다른 경로)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 예를 들어서, 미로찾기를 한다고 가정해보자. 최대한 한 방향으로 가다가 해당 방향의 막다른 길에 다다랐을때, 다시 갈림길로 돌아와서 다른 경로를 똑같이 탐색하고, 이를 탈출구를 찾을 때까지 반복하는 것이 바로 DFS 깊이 우선 탐색이다. 그런데, 만약 잘못 선택한 경로가 올바른 경로에 비해 매우 깊은 (시간이 많이 걸리는) 경로라면?.. 2022. 6. 27.
[BOJ 1715 파이썬] 카드 정렬하기 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶.. 2022. 6. 25.
[Programmers 파이썬] 124 나라의 숫자 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 문제 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 10진법 124나라 10진법 124 나라 1 1 6 14 2 2 7 21 3 4 8 22 4 11 9 24 5 12 10 41 자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요. 처음엔 그냥 3진법으로 변환하면 되지 않을까??해서 왜 level2지 라고 생각했던.. 2022. 6. 23.
[BOJ 11000 파이썬] 강의실 배정 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 그리디 알고리즘에서 자주 보이는 유형이고, 2022. 6. 22.

티스토리툴바