🔗 Algorithm

[Swift] 프로그래머스 숫자 짝꿍

처음 접근 방법 제한사항을 보면 X,Y의 길이가 꽤나 긴것처럼 보인다. 하지만 어차피 문자열 계산이기 때문에 길이가 7인 문자열이다. 그래서 7**7으로 계산을 했다.. /* 1. X를 기준으로 Y visited[길이 Y] 만들기 2. Y를 반복해서 돌며 같은 숫자가 나오면 visited 여부 확인하고 append 3. 갖고 있는 숫자 없으면 return "-1" 모두 0이면 return "0" 아니면 sort해서 문자열로 변경 */ 그리고 코드 import Foundation func solution(_ X:String, _ Y:String) -> String { var answer = [String]() var x = Array(X).map { String($0) } var y = Array(Y).m..

[Swift] 코테풀때 유용한 Input & Output 정리

INPUT 가장 기본적인 형태 readLine()은 return value가 옵셔널이기 때문에 force unwrapping을 해줘야 사용할 수가 있습니다 ❗️ let str = readLine()! Array로 받기 공백을 두고 문자열을 받는 경우에는 split을 통해 분리하여 저장할 수 있습니다. 💡 주의할 점 : split()한 데이터는 String이 아닌 Substring입니다. (엄연히 다른 type이라 error나는 경우가 있으니 알아두면 좋습니당) let arrString = readLine()!.split(separator: " ") Int로 받기 📌 숫자 하나만 입력받는 경우 let num = Int(readLine()!)! 📌 공백으로 구분하여 여러개를 입력받는 경우 type은 Arra..

[Swift] 백준 2941 : 크로아티아 알파벳

풀이 아주 간단하게 생각했다. 크로아티아 알파벳을 문자 하나로 보기때문에 크로아티아 알파벳과 일치하는 문자열을 하나의 문자(*)로 바꾸고 count한다. 코드 import Foundation var s = readLine()! let croatia = ["c=","c-","dz=","d-","lj","nj","s=","z="] for i in croatia { s = s.replacingOccurrences(of: i, with: "_") } print(s.count) 문자열에서 of: 와 일치하는 문자열을 두 with: 으로 바꿉니다. 그리고 그 문자열을 return 합니다. 즉, 기존 문자열을 참조하지 않고 새로운 문자열을 생성합니다.

[Python] 다이나믹 프로그래밍 (DP)

다이나믹 프로그래밍의 핵심은 점화식과 memoization 이다. DP는 주로 bottom-up 방식을 사용하지만, top-down으로도 구현 가능하다. top-down은 재귀+memoization을 통해 구현한다. 대표적인 DP문제로, 피보나치 수열이 있다. https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 📍 피보나치 수의 점화식은 f(n) = f(n-1) + f(n-2) (n>=2) 📌 Bottom-Up ..

[Python] 최소힙(MIN heap) / 최대힙(MAX heap)

힙은 자료구조 트리를 사용하여 구현한다. 트리 중에서도 완전 이진트리이다. 최대 트리는 항상 부모가 자식보다 값이 크다. 최소 트리는 항상 부모가 자식보다 값이 작다. (자식끼리는 상관X) python으로 어떻게 구현할 것인가? 고민할 필요 없이 module을 쓰도록 하겠다. 최소(Min) heap python은 기본적으로 최소 heap을 구현할 수 있는 모듈을 제공한다. import heapq heap으로 선언하는 것은 아니고, 일반적인 배열을 heap으로 만들 수 있다. 예를 들어 정렬되지 않은 arr 배열을 heapify로 정렬할 수 있다. heapify(정렬할리스트) import heapq arr = [1,5,3,6,2] heapq.heapify(arr) print(arr) # [1,2,3,6,5..

[Algorithm] LCA 알고리즘

LCA는 "Lowest Common Ancestor" 가장 가까운 공통 조상을 찾는 알고리즘이다. 백준 3584번을 풀면서 이해해보장 www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 해당 트리에서 3번과 2번의 가장 가까운 공통 조상은 10번이라는 것을 바로 알 수 있다. 그렇다면 a와b가 주어졌을 때 알고리즘으로 최소 공통 조상을 찾아보자. Rule 📌 a의 조상을 모두 찾아 리스트로 만든다. 📌 b의 조..

[Python] 프로그래머스 지형 이동

문제 programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 계속 틀려서 다른 사람의 풀이를 보고 푼 문제이다. 어떻게 이런생각을 떠올리지...? heap을 사용해서 풀었다. 상,하,좌,우 칸 중에 방문하지 않은 칸과의 길이가 height보다 크다면 heap에 차이와 점을 기록한다. height보다 작다면 0과 점을 기록한다. 이를 이용해서 min heap으로..

[Python] 프로그래머스 합승 택시 요금

문제에 대한 자세한 설명은 아래 링크 참조 programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr Dijkstra 알고리즘을 사용해서 풀었다. (최단거리..

[Algorithm] Dijkstra 다익스트라 최단 경로 알고리즘

다익스트라 알고리즘은 A에서 B까지의 최단 경로를 찾고자 할 때 사용한다. 먼저, 알고리즘을 직관적으로 살펴보자 다음과 같은 그래프에서 A->C로 가고자 할 때 최단 경로를 구해보자. 우선 출발지로부터 인접한 노드들과의 거리를 갱신한다. (빨간색) 그 다음 노드로 이동한다. 해당 노드에서 인접한 노드들 중에 방문하지 않은 노드들 과의 거리를 갱신한다. 다음과 같이 D의 거리가 5에서 3으로 갱신 되었다. (최단 거리) C가 5에서 4로 갱신되었다. 현재 방문한 노드가 도착지라면 알고리즘을 종료한다. 그림처럼 A->C의 최단경로는 4가 된다. 위와 같이 동작하는 알고리즘이 다익스트라 알고리즘이다. 📌 Rule 1. 출발 노드로부터 인접한 노드들 사이의 거리를 갱신한다. 2. 다음 노드로 방문하여 인접 노드..

[Python] 백준 7453

세상 복잡하고 까다로웠다.. 이것 저것 시도해보았는데 12초나 주어진 시간이 자꾸 초과돼서 이틀이나 걸린 문제,, 비슷한 유형의 문제가 많다. 백준 1208번 문제도 같은 유형이므로 유형에 대한 설명은 아래 링크에서 참조 📌https://990427.tistory.com/48 [Python] 백준 1208 구글링이 잘 안돼서...직접 쓰는 리뷰 😅 1182번 부분수열의 합과 같은 유형의 문제이지만 범위와 시간제한 등으로 다른 풀이 방법을 적용해야한다. n개의 원소를 가진 수열의 부분 수열을 구하 990427.tistory.com 우선 1208번과 같이 딕셔너리를 사용해서 문제를 풀었더니 시간초과가 났다. 이유는 정말 모르겠다... 딕셔너리의 시간복잡도가 O(1)이긴 하지만 숨어있는 상수가 매우 크다고 한..