n . n

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 직전에 풀은 이항계수3 에서처럼 분할정복을 이용하여 제곱 연산의 시간복잡도를 줄임. 입력값 B가 int 범위를 넘어선 long 값이었는데 처음에 별 생각 없이 int 변수에 저장시켰다가 numberformat 에러가 났다.. 헷갈리는 행렬의 곱 십자 형태로 곱한다고 생각하면 됨 import java.io.BufferedReader; import java.io.IOException; import java.io.I..

https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 페르마의 정리.. 를 이용하는 문제 A^p A 는 (mod p)에 대하여 동치이다(p로 나누었을 때 같은 나머지 값을 가짐) 라는 정리를 이용함. 더보기 더보기 나머지 연산의 분배 법칙은 분모에 대하여 적용되지 않기 때문에 역원을 이용하여 위와 같은 변환을 함. 또한 분할정복을 이용한 거듭제곱 연산 과정을 통하여 시간복잡도를 O(logN) 으로 하여 계산하여 줌. https://blog.naver.com/raylee00..

계속 h2 데이터베이스만 사용하다가 이번에 처음 mysql 연동을 해보았는데.. 설정 파일만 몇 번 만지작거려서 바꿔주면 되는 줄 알았는데 아니었다.. 삽질삽질을 함 환경 : intellj + maven project 1) 'hibernate_sequence' doesn't exist ID 필드 부분에 @GeneratedValue(strategy = GenerationType.AUTO) 위와 같이 설정하였을 때 나오는 문제이다. 구글링을 해 보니 hibernate5 이후 버전부터 Auto type 생성전략을 TABLE 전략으로 바뀌어 작동하기 때문에 발생하는 오류라고 한다.. 따라서 위의 설정을 @GeneratedValue(strategy = GenerationType.IDENTITY) 이와 같이 수정하..

Repository nullpointerException @Autowired private UserRepository userRepository; @Autowired private HttpSession httpSession; 처음에는 위와 같이 autowrired annotation을 이용하여 필드를 주입하려 했으나... 테스트에서 계속 null 에러가 떴다.. entitymanager에서도 에러 뜨고 하여간 에러 창을 너무 많이 봐서 헷갈린다 쨌든 검색해 보니 필드 주입(위와 같은 방식) 은 권장되는 방식이 아니며.. (불변성 위배, 단일 책임의 원칙 위반 등..) 생성자 주입 방식이 권장되는 방법이라고 한다. (+ 한 번 설정된 Service나 Repository에 대해 어플리케이션 실행 후 변경되지..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 대표적인 0-1 knapsack 문제이다. https://kikikiwiii10.tistory.com/86 knapsack problem 작년.. 이 아니라 재작년 수업 때 배운 건데 완 전 까먹어서 문제 풀 때 써먹지 못했다ㅠ Fractional Knapsack 0-1 Knapsack "배낭 채우기 문제" 로 알려져 있으며 위와 ..

작년.. 이 아니라 재작년 수업 때 배운 건데 완 전 까먹어서 문제 풀 때 써먹지 못했다ㅠ Fractional Knapsack 0-1 Knapsack "배낭 채우기 문제" 로 알려져 있으며 위와 같이 두 종류로 분류될 수 있다. 제한된 무게를 담을 수 있는 배낭에 최대의 가치를 갖도록 보석을 넣어야 하는 문제이다 Fractional Knapsack 보석들이 쪼개질 수 있는(Fractional) 문제이므로 Greedy한 방식으로 풀이 가능. 0-1 Knapsack 보석들을 나눌 수 없는 경우이므로 Greedy로 풀이가 불가능하다. 따라서 이 때 DP(Dynamic Programming)을 사용하여 풀이한다. DP는 기본적으로 큰 문제를 작은 문제로 쪼개어 해결한다 라는 분할 정복 기법의 원리를 따르며, 이..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 백트래킹 문제 -> DFS로 풀이 고려했던 점 - 중복되는 알파벳을 밟을 수 없음 -> set 자료구조를 통하여 해결 - 이미 방문한 지점을 방문할 수 없음 -> isVisited 배열 사용 + 처음에는 Character 자료형을 생각하지 못하고.. String을 substring 함수를 통해 반복문마다 자르는 작업을 했다 -> 시간 초과.. substring은 O(N)의 시간복잡도를 가진..

URL에는 자원만 명시되어야 하며, 동작과 같은 단어를 표시하지 않음 동작은 HTTP method(GET, POST, DELETE ..)를 통하여 표시 응답 코드 반환 작업 중요 RESTful API 설계시 유의 사항 (velog.io) RESTful API 설계시 유의 사항 REST API 설계시 유의 사항 Core Rules URI는 Information의 Resource를 표현한다. Resource에 대한 행위는 HTTP Method로 표현한다. 1번 사용자의 정보 조회 REST API // X GET /users/show/1 // velog.io REST API 제대로 알고 사용하기 : NHN Cloud Meetup (toast.com) REST API 제대로 알고 사용하기 : NHN Cloud ..

https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 대다수가 DFS로 푼 것 같고 나도 DFS 로 풀었음 신경썼던 점 - 이동 확률 고려 확률이 각기 다를 수 있음 -> 이동 시마다 계산하면서 탐색해야 함. 한꺼번에 계산 절대 ㄴ - out of bounds isVisited의 배열 부분에서 해당 에러가 나지 않게 조심해야 함 -> 배열의 크기를 넉넉하게 30*30 으로 정의한 후, count(이동 횟수)를 통하여 에러가 일어나지 않도록 함 i..

https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 수학 문제로 자주 나오던 경로의 수 문제 ..?? 랑 똑같다고 생각해서 고거대로 풀음(예외 제외) 더보기 조금 신경써서 고려했던 점 - puddles=0 인 경우 - 나머지 개수를 return해야 함 - puddle 위치에 따라 갈 수 없는 위치가 추가적으로 생김 (*) + 이동방향이 오른쪽, 아래 두 가지이며 목적지가 오른쪽 하단에 존재하기 때문에 ..