본문 바로가기

Algorithm/Programmers13

[Algorithm/Programmers] 가장 먼 노드 Swift 가장 먼 노드 Level 3 BFS 문제 풀이: 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하려고 합니다. -> 1번 노드에서 시작한다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. -> 모든 간선의 거리는 동일하다. -> BFS 주어진 간선을 이용해서 노드의 번호와 배열의 인덱스가 같은 배열을 만들어 그래프로 사용하고 노드의 번호와 배열의 인덱스가 같은 배열을 만들어 1번 노드로부터 떨어진 거리를 저장할 용도로 사용한다. 그리고 시작노드를 큐에 넣고 그래프에 연결되고 방문한 적이 없는 다음 노드로 넘어가면서 현재 노드의 거리에 1씩 더해서 다음 노드에 저장한다. 또한 큐에 다음 노드를 넣는다. 큐에 있는 노드를 다 순회할 때까지 반복한다. 코드: .. 2021. 2. 4.
[Algorithm/Programmers] 섬 연결하기 Swift 섬 연결하기 Level 3 문제 풀이: n개의 섬을 최소 비용으로 모든 섬이 통행이 가능하도록 만든다. -> 크루스칼 알고리즘을 이용한다. 🍎 크루스칼 알고리즘 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키는 것이다. 1. 비용을 기준으로 오름차순으로 정렬한다. 2. 간선을 차례로 확인하면서 사이클이 발생하는지 확인한다. 2-1. 사이클이 발생하지 않으면 최소 신장 트리에 포함한다. 2-2. 사이클이 발생하면 PASS 3. 모든 간선에 대하여 2번을 반복한다. 비용으로 정렬을 한 배열: [[0, 1, 1], [1, 3, 1], [0, 2, 2], [1, 2, 5], [2, 3, 8]] 같은 사이클인지 확인하기 위해서 Parent 배열을 만듭니다. 집합에 포함되어 있지 .. 2021. 2. 2.
[Algorithm/Programmers] 베스트앨범 Swift 베스트앨범 Level3 Hash 문제 풀이: 속한 노래가 많이 재생된 장르를 먼저 수록합니다. -> 장르별로 총 재생 횟수 계산하여 내림차순으로 정렬 장르 내에서 많이 재생된 노래를 먼저 수록합니다. -> 재생 횟수 내림차순으로 정렬 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. -> 재생횟수가 같다면 인덱스 오름차순으로 정렬 0 1 2 3 4 classic pop classic classic pop 500 600 150 800 2500 장르에 대한 데이터(장르별 총 재생횟수: total, 고유 번호별 재싱 횟수: (index,play))를 딕셔너리로 생성한다. 스위프트의 딕셔너리는 할당 또는 value 업데이트로밖에 추가하는 방법이 없다. 그래서 장르는 같지만 .. 2021. 1. 29.
[Algorithm/Programmers] 캐시 Swift 캐시 - 2018 카카오 1차 / Level 2 문제 풀이: 캐시 교체 알고리즘인 LRU(Least Recently Used)를 사용한다. 대소문자를 구분하지 않는다. hit일 경우 실행시간은 1로 계산하며, miss일 경우 5로 계산한다. 큐를 이용한다. 1. 대소문자를 구분하지 않기 때문에 도시들을 소문자로 바꿔준다. 2. 캐시의 사이즈가 0일 경우 도시의 수만큼 5를 곱해서 리턴한다. 3. 해당 순서의 도시가 캐시에 없을 경우 (miss) 3-1. 도시를 캐시에 넣어준다. 3-2. 캐시가 가득 찼다면 가장 오래된 데이터를 제거해주고 넣어준다. 3-3. 실행시간을 5만큼 더해준다. 4. 해당 순서의 도시가 캐시에 있을 경우 (hit) 4-1. 캐시에서 해당 도시의 데이터를 꺼내고 제일 앞으로 옮겨준다.. 2021. 1. 27.
[Algorithm/Programmers] 올바른 괄호 Swift 올바른 괄호 Level2 문제 풀이: 다른 방법도 있겠지만 생각나는 방법으로 풀었다. 1. "("이라면 카운트를 1 증가시킨다. 2. ")"이라면 카운트가 0일 경우 괄호 짝이 맞지 않으므로 false 리턴 2-1. 카운트가 0이 아니라면 카운트를 1 감소시킨다. 3. 주어진 문자열을 다 돌았을 때 카운트의 개수가 0 이라면 true 3-1. 아니라면 false 코드: import Foundation func solution(_ s:String) -> Bool { var cnt = 0 for c in s { if c == "(" { cnt += 1 } else { if cnt == 0 { return false } else { cnt -= 1 } } } return cnt == 0 ? true : fal.. 2021. 1. 15.
[Algorithm/Programmers] 다음 큰 숫자 Swift 다음 큰 숫자 Level2 문제 풀이: 1. 주어진 숫자(n)를 2진법으로 바꿔서 1의 숫자 개수를 구한다. 2. n에 1을 더한 값(next)을 2진법으로 바꿔서 1의 숫자 개수를 구한다. 3. 1번과 2번을 비교하면서 숫자가 같을 경우 next값을 리턴한다. 4. 같지 않다면 next에 1을 더해준다. 5. 1-4번까지 무한 반복 코드: import Foundation func solution(_ n:Int) -> Int { var next = n+1 while true { if checkBinary(n) == checkBinary(next) { return next } next += 1 } } func checkBinary(_ n: Int) -> Int { let s = String(n, radix.. 2021. 1. 15.
[Algorithm/Programmers] 가장 큰 정사각형 찾기 Swift 가장 큰 정사각형 찾기 Level2 문제 풀이: 이 문제는 처음에 완전탐색으로 접근했다가 푸는 방법을 모르겠어서 해설을 참고했다. Dynamic Programming을 이용해서 문제를 풀어야 한다. n이라고 써져 있는 1을 기점으로 박스친 곳에서 최소의 숫자를 구해서 n에 더해준다. 그런 식으로 값을 모두 구하면서 제일 큰 값을 구한다. 그리고 그 값의 제곱을 하면 넓이가 나오게 된다. 코드: import Foundation func solution(_ board:[[Int]]) -> Int { var board = board var result = 0 if board.count == 1 { return 1 } for i in 1.. 2021. 1. 14.
[Algorithm/Programmers] 피보나치 수 피보나치 수 Level 2 문제 풀이: n이 2보다 크거나 같다는 전제하에 f(n) = f(n-1) + f(n-2) 공식을 이용해서 n번째 피보나치 수를 구하면 된다. 같지 않다면 n을 리턴한다. 재귀로 풀면 시간초과가 뜨기 때문에 반복으로 풀어야 한다. DP를 공부하고 있기 때문에 DP를 적용하고 forEach문을 써보는 습관을 기르고 있다. 코드: import Foundation func solution(_ n:Int) -> Int { return fibo(n) } func fibo(_ n: Int) -> Int { var nums: [Int] = [0, 1] guard n >= 2 else { return n } (2...n).forEach { nums.append((nums[$0-1]+nums[$.. 2021. 1. 14.
[Algorithm/Programmers] 프린터 프린터 Level2 문제 풀이: 1. 인덱스와 우선순위를 쌍으로 배열에 저장한다. 정렬한 우선순위를 다른 배열에 저장한다. 2. 첫번째 쌍의 우선순위와 정렬한 우선순위의 첫번째 값과 비교한다. 3. 우선순위가 같다면 카운트를 증가시키고 정렬한 우선순위 첫번째를 제거한다. 3-1. 쌍의 인덱스가 원하는 인덱스와 같다면 카운트 값을 리턴한다. 4. 우선순위가 같지 않다면 마지막에 다시 삽입한다. 코드: import Foundation func solution(_ priorities:[Int], _ location:Int) -> Int { var result = 0 var list = [(Int, Int)]() var pList = priorities.sorted(by: >) for (i, priority) .. 2021. 1. 14.
[Algorithm/Programmers] 스킬트리 Level 2 스킬트리 문제 풀이: 1. 나열된 스킬중에서 스킬트리에 있는 문자열만 추출하여 저장한다. 2. 추출한 문자열과 스킬트리의 문자열을 길이만큼 비교한다. 3. 같은 개수를 구해서 리턴한다. 코드: import Foundation func solution(_ skill:String, _ skill_trees:[String]) -> Int { var result = 0 for skills in skill_trees { let lst = skills.filter { skill.contains($0) } let check = skill.prefix(lst.count) result += lst == check ? 1 : 0 } return result } 문제: programmers.co.kr/lear.. 2021. 1. 14.

티스토리툴바