2020/0215 [leetcode][1329] Sort the Matrix Diagonally 문제 : https://leetcode.com/problems/sort-the-matrix-diagonally/ 입력으로 받은 배열의 대각선 요소들을 오름차순 정렬한 뒤 반환하는 문제 최소힙으로 풀었다. 대각선 요소들을 하나의 힙에 넣어야 한다. 인덱스 0 1 2 3 0 2 3 4 5 1 1 2 3 4 2 0 1 2 3 3x4 배열의 대각선 인덱스를 구하면 위와 같다. (구현에 따라 달라질 수 있음) 대각선 배열의 최대 크기는 n+m-1 이다. (m: 행, n: 열) mat[i][j]의 대각선 인덱스는 i+j-m-1 이다. 위 표를 보았을 때 열의 가장 아래부터 시작하기 때문에 m을 빼주었다. 1은 인덱스는 0부터 시작하기 때문에 뺐다. 따라서 n+m-1 개의 최소 힙을 배열에 저장한뒤, mat 배열을 .. 2020. 2. 15. [hackerrank] Largest Pyramid 문제 : https://www.hackerrank.com/contests/hourrank-23/challenges/largest-pyramid/problem int arr[351][351]; //arr[i][j] : (i,j) 요소 값. (입력값) int max_down[400][351][351] = {0}; //max_down[size][i][j] : j열의 arr[i][j] 부터 arr[i+size-1][j] 중 최대 값 int max_right[400][351][351] = {0}; //max_right[size][i][j] : i행의 arr[i][j] 부터 arr[i][j+size-1] 중 최대 값 int sum[351][351] = {0}; //sum[i][j] : (1,1) ~ (i,j) 까지.. 2020. 2. 15. KMP 알고리즘 만든 사람이 Knuth, Morris, Pratt 여서 Knuth–Morris–Pratt(KMP) 알고리즘이라 합니다. 문자열 알고리즘 중 하나로 문자열 에서 다른 문자열을 검색하는 알고리즘입니다. 단순하게 문자열(S) "ABCABDABCABC" 에서 문자열(P) "ABCABC"를 검색해봅시다. S, P 모두 가장 앞에서부터 같은지 비교합니다. (1) ~ (5) 는 문자가 같기 때문에 다음 문자를 비교합니다. (6) D, C는 다르기 때문에 문자열 P를 찾을 수 없습니다. 이제 S 문자열의 인덱스 1부터 다시 비교합니다. (1) B, A는 다르기 때문에 문자열 P를 찾을 수 없습니다. 문자열 P를 찾을 때까지 이를 반복합니다. 문자열 S 인덱스 6부터 시작하는 부분문자열에서 문자열 P를 찾을 수 있었습니.. 2020. 2. 9. [2020 TODO] 중간점검 (1) 2020 TODO 리스트 중간점검 겸 나름의 점수를 매겨보았다. 마라톤 3번 참여 (3/10) 헬스장에서 런닝머신 3km 정도 꾸준히 달리고는 있다. 그런데 너무 천천히 뛴다는 생각이 듬. 길게 뛰어봤자 15분 정도..? 내가 더 할 수 있는데 이정도 밖에 안하는 거면 연습량을 늘려야 하는데, 기본 체력이 부족해서면 다른걸 해야 되는 걸까나. 주 3일 3km 30분 미만으로 달리기를 하고는 있는데, 주 5일로 변경해야겠다. 주 3일은 좀 적은거 같음. 주 5일 3km 해보고 더해도 괜찮겠다 싶으면 목표 시간을 줄이거나 목표 거리를 늘려야겠다. 4월까지 연습만이 살 길이다. 5kg 감량 (4/10) 먹는 양이 애초에 그렇게 많지 않아서 먹는건 괜찮다고 생각했는데 아니었다. 영양소 부족이다. 흐헝헝 식이섬유.. 2020. 2. 8. FILA x 탬탬버린 콜라보 옷 도차악 예판한거 드디어 왔다. 이쁘자나. 반팔도 살걸 그랬다. 2020. 2. 7. 크루스칼 알고리즘(Kruskal’s algorithm) 신장 트리(Spanning Tree)란, 연결 그래프의 부분 그래프이며 모든 정점과 간선의 부분 집합으로 구성되는 트리입니다. 이 때, 모든 정점에는 하나 이상의 간선에 연결되어 있어야 합니다. 최소 신장 트리(Minimum Spanning Tree. MST)는 만들 수 있는 신장 트리 중에서 간선 비용의 합이 최소인 신장 트리를 말합니다. MST의 간선 개수는 정점의 수 - 1개입니다. 간선들의 비용 합이 최소인 경우는 여러 개 나올 수 있으므로 하나 이상 존재합니다. 이러한 MST를 만드는 대표적인 방법으로는 프림 알고리즘과 크루스칼 알고리즘이 있습니다. 프림 알고리즘은 정점을 선택하여 확장하는 방법이고, 크루스칼 알고리즘은 간선을 선택하여 확장하는 방법입니다. 이번 포스팅에서는 크루스칼(Kruska.. 2020. 2. 6. 이전 1 2 3 다음
