개발 창고(주인장: 파뱁)

다익스트라 알고리즘(Dijkstra algorithm)이란? 다익스트라 알고리즘은 가중치 그래프에서 SP(최단경로) 문제를 해결하기 위해 등장한 알고리즘이다. 최단경로 문제는 두 정점을 연결하는 여러 경로들 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제로, 다익스트라 알고리즘은 SP문제중 Single Source SP(시작정점 v에서 다른 모든 정점까지의 최단 경로 찾기)를 해결하기 위한 알고리즘이다. (단, 음수 간선에 대해서는 성립하지 않는다.) 문제 해결을 위한 기초 생각 시작 노드 정하기 시작 노드에서 가장 가까운 노드를 계속 탐욕적으로 선택 이미 찾은 최단경로에 그 가까운 노드를 더함 더 꼼꼼히 생각해보기 3번과 같이 생각하다보면 한 노드에 접근 할 수있는 엣지가 많을 경우에는 어떤..

https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 문제 설명에 이미지가 필요한 관계로 위 링크에 직접 접속해서 보는 것이 편할 것이다. 입출력의 예는 다음과 같다. triangle result [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 거쳐온 숫자의 최대값을 리턴해야 하므로 항상 최적의 해를 보장하는 알고리즘인 DP(동적 계획법)을 사용하기로 했다. triangle[0][0]의 위치에서부터 하나씩 내려오면서 가질 수 있는 경..

동적계획법 (Dynamic Programming, DP) 동적 계획법은 처음 진행되는 연산을 기록해두고, 이미 진행했던 연산이라면 다시 연산하는 것이 아니라 기록되어 있는 값을 가져오는 것을 의미한다. 제일 쉽게 예로 들수 있는 것이 피보나치 수열 구하기 이다. 피보나치 수열을 구할 때 제일 쉽게 떠올릴 수 있는 것은 재귀함수로 푸는 것이다. 하지만 재귀로 풀게되면, 이전 숫자를 더하는 계산부가 중복으로 작동하기 때문에, 시간적 손실이 크다. 따라서 이전 계산 결과를 저장해두고 사용하는 동적계획법이 훨씬 시간 복잡도를 낮추는 것에 도움이 된다. 보통 동적 계획법을 사용하는 문제는, 공통된 계산 과정을 찾아내서 진행하는 편으로, 예전 수학을 배웠을 때 기억을 떠올려보면, 점화식으로 문제를 푸는 것과 비슷하..

https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 정수 n 이 주어질때, n!을 출력하면 되는 문제 이다. 입출력의 예는 다음과 같다. 예제 입력 1 10 예제 출력 1 3628800 예제 입력 2 0 예제 출력 2 1 팩토리얼 함수를 재귀함수로 구현해서 해결하면 된다. 같은 로직을 아래 게시글에서 설명하고 있으니 참고하면 된다. https://paabaep.tistory.com/63 [자료구조] 재귀함수 재귀함수란 무엇일까 컴퓨터 과학에 있어서 재귀(Recursion)은 자신을 정의할 때 자가 자신을 재 참조하는 방법을 의미한다. 주로 재귀 호출의..

재귀함수란 무엇일까 컴퓨터 과학에 있어서 재귀(Recursion)은 자신을 정의할 때 자가 자신을 재 참조하는 방법을 의미한다. 주로 재귀 호출의 형태로 많이 사용되며, 반드시 종료 조건이 포함되어야 한다. (무한 루프를 방지 하기 위함) 반복문을 사용하는 코드는 항상 재귀함수를 통해 구현하는 것이 가능하며, 그 반대도 가능하다. 이전에 살펴본 알고리즘 중 DFS 역시 재귀 형식으로 구현이 가능하다. 이외에도 대표적인 예제를 살펴보고자 한다. 재귀함수의 대표적인 예 - 팩토리얼 n!의 형태로 표현되는 팩토리얼은 풀어서 작성하면 다음과 같다. n! = n * (n-1) * ... * 2 * 1 이걸 재귀함수를 이용한 코드(파이썬)을 작성하면 다음과 같다. def fact(n): if n==1: return..

https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인 하면 된다. 입출력 예제는 다음과 같다. phone_book return ["119", "97674223", "1195524421"] false ["123","456","789"] true ["12","123","1235","567","88"] false 딕셔너리를 이용하면 ..

https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 마라톤에 참여한 선수와 완주한 선수의 목록이 주어질 때 완주 하지 못한 선수가 누구인지 찾는 문제이다. 입출력의 예는 다음과 같다. participant completion return ["leo", "kiki", "eden"] ["eden", "kiki"] "leo" ["marina", "josipa", "nikola", "vinko", "..

해시(Hash)는 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값이다. 이를 이용하면, 특정한 배열의 인덱스나 위치, 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. 기존에 사용했던 자료 구조들은 탐색이나 삽입시에 시간복잡도 O(n)이상을 가지지만 해시를 이용하면 즉시 저장하거나 값을 꺼내올 위치를 참조 할 수 있으므로 기존 보다 더 빠른 속도로 탐색이 가능해진다. 해시에는 아래의 특징을 보유하고 있다. 1. 무결성 해시는 key와 value 구조라고 봐도 되는데, 이때 value를 더 짧고 유일한 key 값으로 맵핑해준다는 점에서 무결성을 지키는 데에 많은 도움이 된다. 2. 보안성 해시는 기본적으로 복호화가 불가능하다는 특징이 있다. 처음부터 복호화가 불가능..

https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하면 되는 문제 이다. 입출력의 예는 다음과 같다. 예제 입력 1 ZZZZZ 36 예제 출력 1 60466175 진법의 수가 1234, B진법의 B가 3으로 주어졌다고 가정할때 이 수를 10진법으로 바꾸는 법은 1*3^3+2*3^2+3*3^1+4*3^0 이다 이를 일반화해서 계산하도록 만들면 된다. 다만 알파벳 대문자는 A: 10, B: 11..

https://www.acmicpc.net/problem/5692 5692번: 팩토리얼 진법 상근이는 보통 사람들이 사는 것과는 조금 다른 삶을 사는 사람이다. 상근이는 이런 사람들의 시선이 부담스럽기 때문에, 자신만의 숫자를 개발하기로 했다. 바로 그 이름은 팩토리얼 진법이다. www.acmicpc.net 팩토리얼 진법에서는 i번 자리의 값을 ai×i!로 계산한다. 즉, 팩토리얼 진법에서 719는 10진법에서 53과 같다. 그 이유는 7×3! + 1×2! + 9×1! = 53이기 때문이다. 팩토리얼 진법으로 작성한 숫자가 주어졌을 때, 10진법으로 읽은 값을 리턴하면 되는 문제이다. 입출력의 예는 다음과 같다. 예제 입력 1 719 1 15 110 102 0 예제 출력 1 53 1 7 8 8 n값이 주..