![]()
https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 사용한 알고리즘 : DFS 풀이전략 1. 입력에 대응되는 그래프를 2차원 배열에 저장한다. 2. (0,0)에서 (n-1,m-1) 까지의 점에서 동서남북 모든 방향으로 dfs 탐색을 한다. 3. dfs 탐색 중 한 번이라도 방문하지 않은 지점을 통과하면 paintingCount를 증가시킨다. 4. 하나의 지점에서 최대로 방문한 횟수를 maxCount에 저장한다. 5. paintingCount와 ma..
![]()
https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 사용한 알고리즘 : 백트래킹 풀이전략 아래는 입력으로 {1,2,3}이 주어졌을 경우의 상태 트리이다. 루트 노드부터 설명하면, depth=1에서는 1이라는 원소가 삽입되는 경우 왼쪽 노드, 삽입되지 않는 경우 오른쪽 노드로 표시한다. 이와 같이 특정 원소가 삽입되는 경우는 왼쪽노드로, 삽입되지 않는 경우를 오른쪽 노드로 확장해나가면 위와같은 상태트리가 그려..
![]()
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 사용한 알고리즘 : BFS, 트리구조 풀이전략 1. 주이진 입력을 BFS를 사용하여 트리로 만든다. 2. BFS로 탐색 중, 특정 노드의 부모 노드를 저장해둔다. 3. 저장해뒀던 부모 노드들을 출력한다. 제출코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util..
![]()
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 사용한 알고리즘 : 다이나믹 프로그래밍(DP) 풀이전략 d[i] 는 2xi 직사각형을 2x1, 1x2 타일로 채우는 방법의 수를 담은 변수이다. 2x1 타일은 d[i-1] 에 하나의 타일을 덧붙인 것과 같은 결과이고, 1x2 타일은 d[i-2] 에 두개의 타일을 덧붙인 것과 같은 결과이다. 따라서 d[i] = d[i-1]+d[i-2]라는 식이 도출된다. 만약 2x2 타일도 존재했다면, d[i-2]에서 덧붙일 수 ..
![]()
https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 사용한 알고리즘: 다이나믹 프로그래밍 풀이전략 아래의 표는 n 입력에 따라 합으로 나타낼 수 있는 경우의 수들을 나타낸다. 빨간선을 기준으로 첫번째 문단은 1 + [이전의 경우의수] 두번째 문단은 2 + [2번째 전의 경우의수] 세번째 문단은 3 + [3번째 전의 경우의수] 가 출력되는 것을 확인할 수 있다. 따라서 d[i]를 i 입력 시 합으로 나타낼 수 있는 수의 개수라고 할 때 d[i]=d[i-1]+d[i-2]+d[i-3] 라는 식이 도출된다. 제출코드 import java.io.Bu..
![]()
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 사용한 알고리즘: 다이나믹 프로그래밍 풀이전략 마지막 계단을 반드시 밟아야하므로 방법은 2가지로 나뉜다. 1. 마지막에서 2번째 전 계단을 밟고 마지막 계단을 밟는 경우 2. 마지막에서 바로 전 계단을 밟고 마지막 계단을 밟는 경우 하지만 2번의 경우에는 전전 계단을 밟았을 가능성이 있다. 이를 피하기 위해 수정을 하면 (수정후) 2. 마지막에서 3번째 전 계단을 밟고, 마지막 직전 계단과 마지막 계단을..
![]()
https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 사용한 알고리즘 : 다이나믹 프로그래밍(DP) 풀이전략 1~5000까지의 입력이 주어진다고 했으므로 바텀업 방식으로 1kg부터 5000kg까지의 결과값을 미리 구한다. i kg일 때 최소의 설탕 봉지 수는, i-3 kg에서와 i-5 kg에서의 최소 봉지수에 1을 더한 값 중 더 작은 값이다. 단, i-3 kg에서와 i-5 kg에서 3kg와 5kg 봉지를 갖고 모두 담을 수 있는 경우에서 적용된다. 1)..
Version check Spring boot 2.74 MySql 8.0.33 Maven 기본 설정 1. Maven 추가 org.springframework.boot spring-boot-starter-data-jpa mysql mysql-connector-java 8.0.33 runtime mysql은 사용 버전에 따라 다르게 작성해줘야 한다. mysql에서 SELECT VERSION(); 을 입력하면 현재 사용하고 있는 버전이 출력된다. 2. application.properties 작성 # jpa common spring.jpa.show-sql=true spring.jpa.database-platform=org.hibernate.dialect.MySQL5InnoDBDialect spring.jpa...
![]()
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 사용한 알고리즘 : BFS 풀이전략 전형적인 BFS문제였다. 한 정사각형에서 가로, 세로, 대각선 모두를 탐색해야 하므로, dx, dy를 총 8개 두어 모든 방향으로의 탐색이 가능하도록 했다. 제출코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java..
Maven 설정 com.googlecode.json-simple json-simple 1.1.1 (https://mvnrepository.com/artifact/com.googlecode.json-simple/json-simple) React에서 JSON 전송 { axios( { url: '/login', method: 'post', data: [ {email:'test@naver.com',aaa:'aaa222'}, {email:'test2@naver.com',aaa:'aaa333'}], baseURL: 'http://localhost:8080', //withCredentials: true, } ).then(function (response) { console.log(response) console.lo..
