평생공부하는사람

안녕하세요. 오늘은 DFS와 BFS알고리즘에 대해서 알아 보겠습니다. DFS와 BFS는 그래프의 완전탐색 알고리즘입니다. 시간복잡도 두 알고리즘의 시간 복잡도에 대해서 먼저 설명드리겠습니다. 인접리스트형식으로 표현된 그래프와 인접행렬법으로 표현된 그래프에서의 시간복잡도는 다릅니다. 우선 인접행렬법(V by V 행렬 : V은 정점의 개수 입니다.)에서는 O(V^2)입니다. 각각의 노드에서 모든 노드로 간선이 있는지 여부를 알아야 하기 때문입니다. 두번째로 인접리스트형식(V: 정점의 개수, E: 간선의 개수)으로 표현된 그래프에서는 O(V+E)입니다. 각각의 노드에서 다른 노드로 간선이 리스트형식으로 존재함을 알기 때문에 V+E로 모두 탐색 가능합니다. 알고리즘 설명 DFS부터 알고리즘 설명 드리겠습니다. ..

안녕하세요. 오늘은 프로그래머스 큰 수 만들기 문제를 풀어보도록 하겠습니다. 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 우선 탐욕(greedy) 알고리즘에 대해서 알아보겠습니다. 탐욕 알고리즘은 순간순간에서 local한 최적값을 선택하여 global한 최적값을 도출해나가는 알고리즘입니다. 하지만 알고리즘 예시에서 보듯이 완전하게 정렬되지 않은 경우(Heap)에는 최적값을 못찾는 단점이 있습니다. 이제 문제를 풀어보겠습니다. 이 문제는 한 숫자씩 최대값을 찾아서 answer에 넣어주면 되는 문제입니다. 첫 탐색에서는 0 ~ K 번째 까지 탐색하고 최대값은 N1 번째자리수에서 찾았을경우 두번째 탐색에서는 N1 + 1 ~ K+1까지 탐색하고 최대값은 N2번 번째자리수에서 찾았을경우 세번..

안녕하세요. 오늘은 프로그래머스 완전탐색 카펫문제를 풀어보겠습니다. 이 문제는 간단한 방정식 문제인데요. 다들 중학교때 배웠던 근의 공식을 이용해서 문제를 쉽게 푸실수 있으니 식을 보시고 천천히 상기해보시기 바랍니다! import Foundation func solution(_ brown:Int, _ yellow:Int) -> [Int] { // 2x + 2y - 4 = brown // x * y - 2x - 2y + 4 = yellow // x * y = brown + yellow // x = (brown + yellow) / y // x + y = (brown + 4) / 2 // y + ((brown + yellow) / y) = (brown / 2) + 1 // y^2 - ((brown + 4) ..

안녕하세요. 오늘은 프로그래머스 H-Index문제를 풀어보겠습니다. 이 문제가 정렬 카테고리에 있지만 정렬로 굳이 안풀어도 문제가 해결 됩니다. 우선 정렬로 문제를 해결하려면 인용횟수를 정렬시키고 h-index를 찾아가는 방법이 best이겠지만 문제 제약 조건을 보면 굳이 그럴 필요가 없어 생구현으로 문제 풀이가 가능합니다. import Foundation func solution(_ citations:[Int]) -> Int { var count:Int = Int() var hIndex = 0 while true { count = 0 hIndex += 1 for i in citations { if i >= hIndex { count += 1 } } print(count) if count < hIndex..

안녕하세요. 오늘은 다리를 지나는 트럭 문제를 풀어보겠습니다. 우선 이 문제는 제약조건에 의해 문제에서 제시해준 방법대로 풀어도 시간 초과가 나지 않으므로 문제의 풀이 방법대로 구현하였습니다. 우선 구조체로 weight와 seconds를 포함한 다리 위의 truckStatus 구조체를 만들어 주었습니다. 그리고 while문에서 시간(answer)을 측정하면서 문제의 풀이처럼 구현해줍니다. 우선 while문 조건으로 "두가지 queue가 모두 비어있으면 탈출합니다"로 설정하였습니다. 그리고 다리위의 queue가 비어있지 않다면 시간을 증가시켜주고 맨앞의 트럭이 다리길이만큼 시간이 지났다면 dequeue해줍니다. 그리고나서 다리위의 트럭의 토탈 무게를 측정하고 대기트럭이 있다면 대기 트럭의 앞트럭이 올라갈수..

안녕하세요. 오늘은 프로그래머스 배달 문제를 풀어보겠습니다. 배달문제는 단순 BFS로 풀게되면 32번에서 timeout이나는 문제이기 때문에 BFS를 다익스트라 알고리즘을 적용하여 문제를 풀어야합니다. 다익스트라 알고리즘은 이름처럼 막 익스트림하게 어려운 알고리즘이 아닙니다. 그냥 노드에 최단거리일 경우 업데이트 해주고 Queue에 넣어주면 됩니다. 이제 문제를 풀어보겠습니다. 1. 이차원 배열을 이용하여 그래프를 만들어줍니다. var graph:[[Int]] = [[Int]](repeating: [Int](repeating: 0, count: N+1), count: N+1) for i in road { if graph[i[0]][i[1]] != 0 { graph[i[0]][i[1]] = i[2] > g..

안녕하세요. 오늘은 프로그래머스 괄호 회전하기 문제를 풀어보겠습니다. 괄호와 관련된 문제는 대부분 Stack 자료구조를 이용하면 문제를 해결하실수 있습니다. Stack은 Swift의 배열을 이용해서 append()와 removeLast()만 이용해서 사용하시면 됩니다! 이 문제도 마찬가지로 Stack 자료구조를 이용해서 문제를 풀어보겠습니다! 1. 문자열을 회전시킨다. var s1 = s[s.index(s.startIndex, offsetBy: i)...s.index(s.endIndex, offsetBy: -1)] if i != 0 { s1 += s[s.startIndex...s.index(s.startIndex, offsetBy: i-1)] } 2. push or pop 결정한다. var isPop =..

안녕하세요!😀 오늘은 XCode 단축키를 정리할 예정입니다! 뷰(UI) 추가 버튼 : ⌘ + ⇧ + L 현재 탭 바꾸기 : ⌘ + ⌃ + 좌우방향키 추가 화면 띄우가 : ⌘ + ⌥ + ⌃ + ⏎ 변수 / 함수명 일괄 변경 : ⌘ + ⇧ + e 들여쓰기 : tab or ⌘ + ] 뒤로 들여쓰기 : ⌘ + [ ⌥ ⏎⌘⇧⌃ 요론 기호들 쓰는법! : fn 앞으로도 알아내면 꾸준히 추가하겠습니다!

안녕하세요. 오늘은 프로그래머스 후보키 문제를 풀어보겠습니다! 후보키 문제는 여러가지 알고리즘을 섞어만든 문제인데요! 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr row&column이 max 8*20이기 때문에 어떤 방법으로해도 전략만 잘 세운다면 시간초과날 일은 없을듯합니다! 처음에는 재귀알고리즘을 이용하여 combination을 하여 후보키 후보조합을 만들어줍니다! 이 후 sort..

안녕하세요! 오늘은 프로그래머스의 예상 대진표 문제를 풀어보겠습니다! 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr 이 문제는 tree의 공통 부모 노드를 찾는 문제입니다! 대진표가 완전 이진트리여서 동일한 부모노드가 나올때까지 ÷2 로 나누어주시면 됩니다! 그러기 위해서는 각각의 Index를 이진트리에 맞춰주어야하는데요. n이 2^x 이기 때문에 n - 1 + a, n - 1 + b로 인덱스를 바꾸어주시면 됩니다! import Foundation func solution(_ n:I..