Devlog_by_0giru

다익스트라는 그래프에서 한 노드로부터 각 노드까지의 최소 거리(간선 가중치의 합)을 구하는 알고리즘이다. 다익스트라 알고리즘은 각 노드를 방문하면서 전진할 수 있는 노드의 거리를 계산하고, 해당하는 노드에 대해 지금까지 구한 거리보다 작다면 갱신해주는 방법을 이용한다. 그래프가 주어지고 각각의 간선의 가중치가 주어졌을 때, 아래와 같은 방법을 따라 동작한다. 1. 출발 노드를 설정한다 2. 최단 거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다. 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다. 5. 3번과 4번 과정을 반복한다. 글로만 알고리즘을 이해하기는 어렵고, 그림으로 이해해보자. 아래와 같은 그래프가 있다고 가정하자...

아이폰과 아이패드를 사용하며 충동적으로 맥북을 질러버렸다. 그리고 쓰던 윈도우 노트북을 팔아치웠다. 최근 M1 칩셋의 맥북이 아주 핫하지만 지갑씨와의 타협을 통해 2017 13인치 프로 모델로 타협을 봤다. 맥 OS는 처음 써봤는데 생각보다 어렵지 않게 적응하고 있다. 오늘은 맥 OS의 homebrew라는 패키지 관리자에 대해 알아보자. 생활코딩 egoing님의 강의를 적극 참고했다. 사실 이 글도 아래 영상을 보고 정리한 것이기 때문에 아래 영상을 보면 더 깔끔한 설명을 들을 수 있다... 생활코딩 hombrew : opentutorials.org/course/128/11129 homebrew - 생활코딩 시스템 엔지니어나 프로그래머들은 명령어로 제어하는 프로그램을 많이 사용합니다. GUI는 줄 수 없..

이전에 포스팅 했던 깊이우선 탐색(DFS)와 또 다르게 널리 이용되는 탐색 이론이다. DFS가 이름 처럼 하나의 노드에서 도달 가능한 깊은 노드까지 먼저 탐색한다면, 넓이우선 탐색 BFS는 하나의 노드로부터 주변의 모든 노드로 뻗어나가며 탐색하는 방법이다. 넓이 우선 탐색은 큐 자료구조를 이용한다. 큐의 선입선출 특성을 이용하는데, 큐의 가장 첫 번째 노드와 연결된 노드를 큐에 집어넣고, 첫 번째 노드를 큐에서 빼낸 후 방문처리를 하는 것을 반복한다. 아래와 같은 그래프가 있고 1번 노드로부터 BFS를 이용해 탐색을 시작한다고 하자. +) 탐색을 시작하는 노드는 어디로 해도 상관없지만 숫자가 작은 노드부터 오름차순으로 하는 것이 편하고 또 그것을 관례적으로 따르기도 한다. 시작 노드인 1번 노드를 큐에 ..

가장 긴 증가하는 부분 수열1 에 이은 시리즈 문제다. 처음에는 11053번처럼 dp로 접근하려고 했지만 입력 데이터의 수가 너무 많아 dp로 해결할 수 없는 문제임을 깨달았다. dp를 이용하려면 전체 리스트(배열)에서 i번째와 i-1번째까지의 데이터를 중복해서 탐색해 O(N^2)의 시간 복잡도를 가지게 된다. 11053번의 경우 입력 데이터의 개수가 1000개 까지라 시간 초과에 걸리지 않지만 12015번의 경우 입력 데이터가 훨씬 많아 O(N^2)의 시간복잡도를 가진 알고리즘을 사용할 경우 시간 초과가 발생한다. 따라서 O(NlogN)의 시간 복잡도로 해결해야 하고 이를 위해 i-1번째까지의 데이터를 이진탐색을 통해 시간을 단축해줘야 했다. 사실 위 부분까지는 이해가 되는 부분이나, 아래 부터 나오게..

이진 탐색은 탐색 알고리즘 중 하나로, 이분 탐색이라고도 한다. 이진탐색 혹은 이분 탐색은 말 그대로 탐색하고자 하는 데이터를 반으로 나누어 탐색해간다는 의미이다. 위와 같은 데이터에서 17이라는 데이터를 찾는다고 가정하자. for 혹은 while과 같은 반복문을 통해서도 빠른 시간 내에 값을 찾을 수 있겠지만, 이진 탐색을 적용해 찾는 과정을 살펴보자. 이진 탐색을 적용하기 위해 array 데이터를 정렬해주었다. 이진 탐색은 반드시 정렬된 데이터에서만 사용할 수 있다. 그리고 우리는 이 array에서 17이라는 데이터를 찾고자 한다고 가정하자. 먼저 위에서 언급한 대로 반복문을 통해 0번 인덱스부터 탐색을 한다면 9번만에 찾을 수 있다. 지금은 array 데이터의 크기가 작아 충분히 작은 시간이지만, ..

처음 이 문제를 봤을 때에는 dfs를 이용해 해결하려고 했으나, 최솟값을 구해주기 위해선 백트래킹 알고리즘을 생각해줘야 했는데 이 부분이 어려워 bfs를 이용해 해결했다. bfs는 큐를 이용해 문제를 해결하는데, 기초적인 이론으로 bfs를 설명하면 보통 그래프를 이용해 설명한다.(bfs알고리즘 포스팅 링크 첨부 예정) 이 문제는 x, y좌표를 이용한 이중 배열(리스트)를 이용하여 해결하는 문제였기 때문에 bfs 알고리즘을 실제로 코드에 녹여내기가 조금 어려웠다. 이런 문제처럼 x, y좌표를 통해 이중 배열(리스트)로 나타내는 모양을 이용하는 문제 유형이 대표적이니 반드시 익숙해져야 겠다고 느꼈다. 백준 예제 2번을 이용해 설명하겠다. 처음에 주어진 그래프가 있고 빈 큐를 선언했다. 처음 시작 부분의 좌표..

최장 공통 부분 수열이라고 부르는 알고리즘이다. 영어로 LCS(Longest Common Subsequence) 라고 하는데, 최장 공통 부분 문자열도 LCS라고 부르는 모양이다. 둘의 차이점은 공통 부분이 연속하느냐, 마느냐인 것 같다. 이 부분에 대해서는 나중에 후자인 LCS를 공부할 때 다시 수정할 계획이다. 백준 9252번을 풀기 위해 필요한 알고리즘인데, 아주 클래식한 알고리즘이기도 하니 필수적으로 알고 있어야 한다. https://www.acmicpc.net/problem/9252 LCS 알고리즘을 풀기 위해서는 검사할 두 문자열의 앞에 공백 문자열(혹은 더미 문자열)을 하나씩 붙여주어야 한다. 검사할 문자열이 ACAYKP, CAPCAK라고 하자. (백준 9252번의 테스트 케이스이다.) 위 ..

# 퇴사 https://www.acmicpc.net/problem/14501 time_cost = list() price_earn = list() max_val = 0 N = int(input()) dp = [0 for i in range(N+1)] for _ in range(N): T, P = map(int, input().split()) time_cost.append(T) price_earn.append(P) # dp[i] = i일부터 마지막까지 상담 시 얻을 수 있는 최대 이득 # dp[i] = p[i] + dp[i+t[i]] # N일부터 1일까지 거꾸로 계산 for i in range(N-1, -1, -1): temp = i + time_cost[i] if temp