https://github.com/mingtian-chan/Hang99_Spring_intro/tree/week1_assignment GitHub - mingtian-chan/Hang99_Spring_intro Contribute to mingtian-chan/Hang99_Spring_intro development by creating an account on GitHub. github.com Spring을 이용해서 Restful 하게 CRUD를 구현하는 과제였다. 과제를 하면서 힘들었던 점이 몇 가지 있었기에 공유하고자 한다. 힘들었던 점 MySQL이 갑자기 연결이 안됨 말 그대로 잘 되다가 갑자기 MySQL연결이 안되어서 시간을 많이 빼앗겼다. 컴퓨터 재부팅을 하니까 제대로 잘 작동했는데, 오늘 멘..

이번 주에 배운 것 이번주가 알고리즘을 배우는 마지막 주차였다. 마지막 주라 그런지, 배우는 개념도 어느정도 난이도가 있었다. 정렬 알고리즘 (Quick sort, Merge sort), 이진 탐색(Binary Search), 이진탐색을 이용한 최적화 문제 해결 (파라메트릭 서치 기법), 최단경로찾기 (다익스트라, 플로이드), 동적계획법( Dynamic Programming ) 을 배웠다. 이번 주에 느낀 점 문제를 푸는 것은 크게 두가지의 과정이 있다. 1. 문제를 어떻게 풀어야 할 지를 고민하고 2. 고민한 생각을 실제 코드로 구현 대개는 문제 난이도가 (1,2가 둘다 쉬운 문제) -> (1은 쉽지만 2가 까다로운 문제) -> (2는 쉽지만 1이 까다로운 문제) -> (1,2 둘 다 까다로운 문제) ..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 숫자를 세기만 하면 되는 문제인 줄 알았는데, 숫자의 범위가 꽤나 크고, 입력의 개수도 꽤 많았다. 잘한점: 1. 연산량이 많을 것 같아서 해시맵인 dict자료구조를 이용할 생각을 했음. 문제를 못 푼 요인: 1. 처음에는 count연산을 했는데, count를 하면 한 번 count할 때마다 O(N)의 시간 복잡도로 돌기 때문에, N 번 센다면 O(N^2)의 시..

DP? DP는 우리나라말로 동적계획법이라 하며, 한번에 풀기 어려운 문제를 잘게 쪼개서 (divide) 하나하나 풀어나가며 전체 문제를 푸는 (conquer) 방식이다. 우리가 일반적으로 엥? 재귀랑 다른게 뭔데! 라고 한다면 DP는 결과를 기록해서 똑같은 계산을 하지 않음으로 시간을 아낀다는 것이다. 피보나치 수열 피보나치 수열은 다음 값이 이번 값과 이전 값의 합으로 표현되는 수열이다. 식으로 나타내면 F( n) = F(n-1) + F(n-2) 로 표현할 수 있는데, F(5)를 계산하기 위한 과정을 보면, F(5)를 계산하기 위해서 F(3)은 두번 계산되고 F(2)는 3번이 계산되는 것을 볼 수 있다. 5라는 숫자가 작아서 몇 번 안 되는것 처럼 보이겠지만, 시간복잡도는 O(2^n)의 시간 복잡도를 ..

플로이드? 다익스트라 알고리즘이 한 정점에서 다른 정점까지의 최단거리를 구하는 알고리즘이라면, 플로이드는 어떤 정점에서 다른 정점까지의 최단거리를 모두 구하는 알고리즘이다. 코드로 보도록 하자. INF = int(1e9) n = int(input()) m = int(input()) graph = [[INF] * (n+1) for i in range(n+1)] # 자기 자신으로 가는 노드는 거리가 0 이라고 가정 for i in range(1,n+1): graph[i][i] = 0 # 그래프 입력받기 for _ in range(m): a, b, c = map(int, input().split()) if c < graph[a][b]: graph[a][b] = c # 거리의 최솟값 구하기 for k in ra..

다익스트라? 엄청난 분이시다... 다익스트라 알고리즘을 개발해서 최단경로 문제도 연구하시고 세마포어도 이 분께서 처음 연구하셨다고..! 그럼 간단하게 다익스트라 알고리즘에 대해서 알아보자. 다음과 같은 그래프가 있다고 하면, s에서 다른 노드로 가는 최단거리를 구하려면 1. 바로 갈 수 있는 노드는 그 거리를 저장하고, ( t = 10, y = 5 ) 직접 이어지지 않았다면 거리를 무한으로 저장한다. 2. 갈 수 있는 가장 가까운 노드(y)에서 다른 노드까지 직접 가는 거리를 더해서 만약 작다면 갱신해준다.(t = 10 -> 8 ) 3. 또 s에서 (다른 노드를 거치든 안 거치든) 가장 가까운 노드 (z = 7 , t = 8이므로 z )에서 다른 노드간 거리를 합해서 최단 거리를 갱신한다 4. 반복해서 ..

파라메트릭 서치 기법 이진탐색을 이용해 최적화 문제를 풀 수 있다. 어떤 조건에서 가장 최적의 해를 구할 수 있을 지를 이진탐색을 통해서 해결하는 방식을 파라메트릭 서치 기법이라고 한다. 어떤 조건을 가지고 계속 왼쪽 오른쪽 값을 조절하면서 조건에 가장 최적화 된 답을 찾는 것이다. 끝나는 조건이나 왼쪽오른쪽 값을 바꾸는 조건을 문제에서 잘 확인해서 적용해야해서, 이 조건을 유의해서 풀어야 한다. 백준 2512 예산 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 w..

이진탐색? "정렬된" 배열에서 어떤 값을 찾는다면 어떤 값을 기준으로 큰 지, 작은 지만 알면 굉장히 빠른 속도로 찾을 수 있다. log2(N)의 속도로 어떤 값을 찾는 것인데, 1억개도 27번만 연산하면 원하는 원소를 찾을 수 있다는 거! 구현 두 개의 점과 그 점의 중간 점이 한 직선에 있다고 생각하자. 만약에 중간 점이 우리가 원하는 값보다 크면, 중간점을 왼쪽으로 옮겨줄거고, 작다면 오른쪽으로 옮길 것이다. 중간점을 왼쪽으로 옮기려고 하면 오른쪽 점을 중간 점 위치로 옮기는 것이고, 즁간점을 오른쪽으로 옮기려고 하면 왼쪽 점을 중간 점 바로 다음 위치로 옮기면 된다! def binary_search(nums, target): def bs(start, end): if start > end: retu..

Quick Sort? 퀵소트는 기준(파티션) 을 정한 뒤정해진 기준보다 작으면 파티션의 왼쪽, 크면 오른쪽에 배치하고(분할) 파티션 기준 왼쪽과 오른쪽 배열을 다시 퀵소트를 해서(정복) 재귀적으로 정렬하는 정렬방식이다. 파티션과 원소들의 위치를 서로 왔다갔다 바꾸면서 정렬하기때문에, 원래 배열의 순서를 유지하지 못한다. 그래서 Unstable 정렬방식이다. 파티션을 정하는 방법은 lomuto식이 있고 Hoare식이 있는데, 여기선 lomuto식을 이용했다. def quicksort(lst, start, end): def partition(part, ps, pe): pivot = part[pe] i = ps - 1 for j in range(ps, pe): if part[j] = end: return No..