이번 주에 배운 것 Spring initializr 을 이용해서 Spring 프로젝트를 시작 스프링에서 제공하는 기능을 이용해 간단한 CRUD 게시판 만들기 Jdbc template를 이용해서 쿼리문을 이용해 MySQL에 데이터 저장 및 불러오기 Jpa를 이용해 간단한 메서드나 애너테이션으로 엔티티 생성 및 데이터 저장, 불러오기 jwt를 이용한 로그인 기능 구현 이번 주에 느낀 것 이번 주차부터는 스프링에 대한 본격적인 공부가 시작되었는데, 강의에서 배운 내용을 응용해서 API설계부터 프로그램을 짜기까지의 과정을 반복했다. 모든 내용이 처음 배운 내용에서 조금씩 어떤 부분에서 개선되었고 바뀌는 것이 있었다. 예를들어 jdbc template에서는 직접 쿼리문을 사용해서 데이터 베이스에 접근했다면, Jp..

https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 이진 탐색 문제다. 주어지는 N과 M이 둘 다 10^5 까지의 범위기 때문에, if문으로 전부 비교하게 되면 10^10으로 1초의 시간제한을 벗어나게 된다. 처음에 문제에 접근할 때는, 이진탐색으로 칭호를 기준으로 이진탐색하면서 ~칭호 이하의 개수만큼 ~칭호를 출력, 그 초과, 다음 이하의 개수만큼 ~칭호를 출력 하려고 생각했는데, 거꾸로 생각하면 더 편..

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..