본문 바로가기

Algorithm

 (23)
[알고리즘] BFS? DFS? BFS 너비 우선 순회 Queue로 구현 (큐를 이용하기 때문에 FIFO) 장점) 최적해를 찾을 것을 보장한다. 예를 들어서 지구 상에 존재하는 모든 친구 관계를 그래프로 표현 후, 소깡이와 후리 사이의 관계 경로를 찾는 경우, BFS - 소깡이와 가까운 관계부터 살핀다. DFS - 일단, 지구상의 모든 관계를 살핀다. 어떤 로직으로 구현되는가? - 시작 노드를 큐에 삽입하고 방문처리를 한다. - 큐에서 노드를 꺼낸 후, 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 넣는다. 그리고 방문 처리를 한다. (방문하면 현재 위치를 pop하고 방문 처리 -> 방문'할' 곳은 큐에 넣는다.) 사용 예시 너비 우선 탐색 알고리즘은 많은 문제를 푸는 데 사용된다. 예를 들어, 소스 노드(처음 노드)와 다..
[알고리즘] 깃헙 레포를 만들었습니다. 제곧내 .. 인데 .. 문제를 풀고 정리할 부분들이 많다면 여기에 하겠지만 .. 약간 .. 가볍게 지나가는 문제들 .. 의 경우에는 .. (또는 정리를 하기 귀찮다 .. ) 할 수도 있잖아 .. ? 요 .. ? 몰라 .. 그래서 레포를 만들었다 .. 링크는 .. Git Repository 요기 .. (디스크립션 .. 을 좀 더 참신한 것으로 하고 싶었는데 .. 내 머리 속에서는 알고리즘하면 저 노래밖에 생각 나지 않는걸 워캄.) 아무튼 .. 하루에 한문제를 푸는 것을 목표로 하고 있다 .. 알고리즘. 뽀개주마. 정리도 꾸준히 할 것임. 약간 .. 어려웠다거나 .. 생각하지 못했던 방법이라던가 .. 근데 또 .. 깃헙 디스커션에서도 쓸거라 .. 왔다갔다 해야지 .. (갈팡질팡 ..)
[알고리즘] DFS 구현 개념 깊이 우선 탐색으로, Depth-First-Search의 줄임말인 DFS라고 많이 부른다. 탐색하려는 노드의 자식 노드부터 우선 탐색하는 방식이다. 앞선 글인 BFS와 마찬가지로 숫자가 순서라고 생각하면 된다. 탐색 노드의 인접 노드의 자식 노드들을 모두 탐색하고 다시 돌아가서 탐색 노드의 다른 인접 노드의 자식 노드들을 탐색하는 방법이다. BFS와 마찬가지로, 하나의 노드에 대한 인접 노드들 중에서 왼쪽/오른쪽의 순서는 중요하지 않다. 어디를 먼저하더라도 해당 노드에서 가장 깊은 노드(자식의 .. 자식의 .. 자식 노드)를 다 탐색해야 다음 인접 노드를 탐색할 수 있기 때문이다. 구현 그래프 생성 BFS와 마찬가지로 인접 리스트 방식을 사용해서 그래프를 만들면 아래와 같다. let graph: [..
[알고리즘] BFS 구현 개념 너비 우선 탐색으로, Breadth-First-Search, 줄여서 BFS라고 한다. 인접한 노드들을 우선 탐색하는 방식이다. 위의 이미지에서 숫자가 탐색하는 순서라고 생각하면 된다. 탐색 노드부터 인접한 노드들을 탐색하고 -> 모두 탐색하면 그 노드들의 인접한 노드들부터 탐색하는 것이다. 같은 레벨에 있는 (같은 층에 있는) 노드들부터 탐색하는 것이라고 생각하면 된다. 🤔 오른쪽? 왼쪽? 참고로 너비 우선 탐색에서 하나의 노드에서 인접 노드들 중 오른쪽을 먼저 탐색하는지 / 왼쪽을 먼저 탐색하는지 순서는 중요하지 않다. ➡️ 같은 레벨에 존재하기 때문에, 어디를 먼저 탐색하더라도 같은 레벨에 있는 노드를 먼저 탐색해야 다음 레벨(아래)로 이동할 수 있기 때문이다. 구현 0. 그래프 생성 왼쪽과 같..
[백준] 함수 [함수] 단계에서는 문제가 3개밖에 없어서 기록용으로 정리 .. 4673번 입력) 입력은 없다. 출력) 10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다. 소깡이 풀이 import Foundation func calculateDNumber(value: Int) -> Int { let dNumber = value + (value / 10000) + (value % 10000 / 1000) + (value % 1000 / 100) + (value % 100 / 10) + (value % 10) return dNumber } var arr: [Int] = [] var total: [Int] = [] for i in 0...10000 { total.append(i) arr.app..
[백준] 1712번: 손익분기점 문제 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다. 예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다. 노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 생산 대수를 늘려 가다 보면 어느 순간 총 수입(판매비용)이 총 비용(=고정비용+가변비용)보다 많아지게 된다. 최초로 총 수입이 총 비용보다 많아져 이익이 발생하는 지점을 손익분기점(BREAK-EVEN POINT)이라고 한다. A, B, C가 주어졌..
[백준] 상수 문제 링크 문제 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 개를 칠판에 써주었다. 그 다음에 크기가 큰 수를 말해보라고 했다. 상수는 수를 다른 사람과 다르게 거꾸로 읽는다. 예를 들어, 734와 893을 칠판에 적었다면, 상수는 이 수를 437과 398로 읽는다. 따라서, 상수는 두 수중 큰 수인 437을 큰 수라고 말할 것이다. 두 수가 주어졌을 때, 상수의 대답을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 칠판에 적은 두 수 A와 B가 주어진다. 두 수는 같지 않은 세 자리 수이며, 0이 포함되어 있지 않다. 출력 첫째 줄에 상수의 대답을 출..
[백준] 1157번: 단어 공부 문제 링크 문제 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. 입력 첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다. 출력 첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다. 소깡이 풀이 import Foundation extension Character { var asciiIndex: Int { return Int(self.asciiValue!) - 97 } } var charDic: [Int] = [Int](repeating: 0, c..

티스토리툴바