msmn

배운 점 스프링 부트를 활용해서 CRUD 기능이 포함된 블로그를 만들었다. GET, POST, PUT, DELETE로 매핑하는 REST API에 대한 실습을 하며 지식을 쌓았다. html, css, js와의 연동을 하며 원하는 데이터를 화면에 배치할 수 있도록 학습했다. 쿼리 스트링에 대해 알게 되었고, id에 따른 상세페이지에 접근하는 방법을 알게 되었다. 여러 실습을 통해 controller, service, repository 3 계층의 구조를 알게 되었다. 느낀 점 플라스크보다 스프링이 활용법이 상대적으로 어렵다는 것을 느꼈다. 숙련도의 차이도 있겠지만, 파이썬이 자바보다 편리한 것도 한 몫하는 것 같다. 스프링과 자바에 많은 시간을 투자해서 환경 자체에 익숙해져야겠다고 생각했다.

배운 점 알고리즘 문제를 집중적으로 복습하며 실력을 쌓았다. 기본적인 웹 페이지에 대한 작동원리와 스프링에 대한 공부를 했다. 느낀 점 알고리즘에 대한 공부는 많이 해도 부족함을 계속 느끼게 되는 것 같다. 앞으로 부족한 부분을 채우기 위해 열심히 정진해야겠다고 느꼈다. 자바와 스프링에 대한 공부도 꾸준히 해서 주특기를 다져야겠다.

알고리즘 분류: DP 문제 링크: www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net DP[i]: 길이가 i인 모든 2진 수열의 개수라고 정의한다. 주어진 조건대로 나열해보면 DP[i] = DP[i-2] + DP[i-1]이라는 점화식을 도출해낼 수 있다. DP[i-1]의 개수(1 하나가 붙은 경우) + DP[i-2]의 개수(00 붙은 경우)이기 때문이다. #include #include #include #include #include #include #include ..

알고리즘 분류: 백트래킹 문제 링크: www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 먼저, 한 행에 한 개의 퀸만 놓는 방식으로 진행하면 가로 방향은 체크할 필요가 없다. 그렇기 때문에 세로, 슬래시, 역슬래시 방향으로 방문 확인을 해줄 배열을 3개 만들어서 해결했다. 재귀를 돌며 x+1이 되므로 행이 한 칸씩 내려가고 방문확인을 통해 퀸을 놓을 수 있는 좌표인지 확인한다. 놓을 수 있는 곳이면 정답을 +1 하는 방식으로 백트래킹이 진행된다. 예를 들어 n=3일 때를 표로..

알고리즘 분류: 수학, 분할 정복, 재귀 문제 링크: www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net O(logb)로 구현하기 위해서는 수학의 거듭제곱의 규칙을 활용해야 한다. (a^b)% c == (a^b/2)% c * (a^b/2)% c이다. 매 번 지수(b)의 홀수 여부를 판별해서 a를 한번 더 곱해준다. 재귀를 도는 동안 b가 절반씩 줄어드므로 O(logb)라 할 수 있다. #include #include #include #include #include #include #include #include #include..

알고리즘 분류: 다익스트라 문제 링크: www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 기본 다익스트라 유형이다. priority queue를 사용해서 다음 방문할 곳의 정보를 O(n) -> O(logn)만에 알아낼 수 있다. 총 시간복잡도는 O((E+V)logV)가 된다. dist배열에 시작 지점부터 도착 정점까지 현재까지의 최소비용을 저장하며 갱신하는 방식이다. 새로운 정점을 거쳐서 도착했을 때, 저장된 값(dist[nxt])과..

알고리즘 분류: DFS 문제 링크: www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 2차원 배열에 입력을 받고 2중 포문을 돌면서 집을 발견하면 인접한(상하좌우)부분을 0으로 처리한다. 이 때, DFS 함수를 호출하여 각 단지의 집의 갯수를 반환받아 벡터에 저장한 후, 마지막에 정렬하여 출력하면 풀린다! #include #include #include #include #include #include #include #include #include #includ..

알고리즘 분류: DP, LIS 문제 링크: www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net LIS를 활용하면 간단하게 구현할 수 있는 DP문제이다. 왼쪽부터 LIS, 오른쪽부터 r_LIS배열에 저장한 후 최대 길이(두 LIS의 합-1)를 구하면 된다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #i..

알고리즘 분류: 재귀, 분할정복 문제 링크: www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 재귀로 구현할 때 여는 괄호 위치를 잘 잡아줘야한다. 사이즈 만큼 정사각형을 압축 성공했으면 다시 재귀가 돌지 않도록 함수를 끝내주어야 한다.(return으로 종료) #include #include #include #include #include #include #include #include #include #include #include #includ..

알고리즘 분류: 자료구조, 큐 문제 링크: www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net deque를 활용한 풀이 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define INF 1e9 using namespace std; //https://www.acmicpc.net/prob..