분류 전체보기 (30) 썸네일형 리스트형 [ACMICPC] 13469 . 시간표 짜기 14569번 시간표 짜기 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? BruteForce 모든 과목의 수업 시간을 하나씩 체크하면서 그 시간이 비는지 체크한다. 이 경우 O(N*k*M) = O(500,000,000)으로 시간 제한을 넘긴다. 다른 방법이 필요하다. BitMask 결국 어떤 과목과 학생의 시간을 탐색하는 방법의 최적화가 필요하다. 시간이 1 50 사이로 주어지므로, 64Bit 자료형을 사용하여 1 50 사이의 주어지는 시간의 Bit를 켜두고 &연산자를 활용하면 50번의 비교를 1번의 비교로 줄일 수 있다. 2. BitMask 코드 1 2 3 4 5 6 7 8 9 N = Integer.parseInt(br.readLine()); long[] lectures = new long[N.. [ACMICPC] 18111 . 마인크래프트 18111번 마인크래프트 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? 땅의 높이가 최대 256이므로 0부터 256까지 높이를 한 번씩 설정해보고 그 높이로 평탄화하는 방법을 생각할 수 있다. 맵의 크기는 최대 500이므로 250,000이다. 250,000*257 = 64,250,000이므로 1초 제한인 이 문제에서 모든 블럭을 한 번씩 돌면서 높이를 체크하는 방법을 쓰기는 불안하다. 모든 맵을 돌지 않아도 땅의 최대 높이가 256이므로 각 높이에 해당하는 블록의 개수를 미리 저장해둘 수 있다. 그리고 0~256까지 높이를 한 번씩 시도해보면서 현재 가지고있는 블럭들의 높이에 대해서 현재 설정한 높이를 만드는데 드는 비용을 계산할 수 있다. 2. 전체 코드 12345678910111213141.. [ACMICPC] 2468 . 안전 영역 2468번 안전 영역 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? 맵이 주어지고 4방탐색을 하는 간단한 방법으로 DFS,BFS가 있다. 이 문제의 경우에는 최단거리 측정이 필요 없고 반복되는 탐색을 재귀로 쉽게 구현이 가능하므로 DFS를 사용하기로 한다. 2. DFS 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 // main ... for(int i=1;i<=max_height;i++){ ans = Math.max(ans,solveByDfs(i)); } // main ... static int solveByDfs(int rain){ chk = new boolean[N+2][N+2]; in.. [ACMICPC] 2470 . 두 용액 2470번 두 용액 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? 바로 떠오르는 방법은 이중 포문을 이용하여 두 원소를 선택하는 방법으로 O(N^2)안에 답을 찾을 수 있다. 그러나 N의 최대 제한이 10만이기 때문에 O(N^2)의 방법은 불가능하다. 다음으로 두 가지의 방법을 더 떠올릴 수 있다. 이분탐색 1부터 N까지 모든 원소에 대해서 해당 원소를 정해놓고, 그 원소와의 합이 0에 가까운 다른 원소를 찾을 때 정렬이 되어있는 배열에서는 이분탐색을 사용할 수 있다. 투포인터 l=0, r=N-1부터 시작하여 두 위치에 있는 원소의 합이 0보다 작거나 같으면 l의 인덱스값을 올리고, 반대의 경우 r의 인덱스값을 줄이면서 답을 갱신하면 답을 찾을 수 있다. 2. 이분탐색 코드 1234567891.. [Web / Spring] EntityManager로 JPQL 사용 시 단일 Entity 찾기 ( No entity found for query ) 문제 상황 회원 가입을 할 때, 원래 PK로 설정된 name으로 중복 검사를 했는데 email로 검사하는 것으로 바꿨다. 그런데 이전에 회원가입한 회원은 로그인이 되는데, 신규 회원가입은 되지 않는 상황이 발생했다. findByEmail 메소드에서 에러를 뿜고 있었다. No entity found for query라는 것을 보고 두 가지 생각이 났다. 1. query가 잘못됐다. 2. query는 정상이고 말 그대로 query에 맞는 entity를 찾지 못했다. 신규 회원가입자는 DB에 없는 email을 넣어야 회원 가입이 되므로 당연히 query의 결과로는 아무것도 없어야 한다. 결국 No entity found for query라는 에러의 의미는 query의 결과 중복되는 email이 없다는 것이다... [CS / Regex] 정규표현식의 엔진과 성능 정규표현식이란? 정규표현식은 특정 문자열 규칙을 가진 문자열의 집합을 찾는 언어이다. 정규표현식의 동작 모든 정규표현식은 그 정규표현식에 맞는 Finite Automaton(FA)로 만들 수 있다. 정규표현식을 컴파일한다는 것은 원래 정규표현식을 정규표현식 엔진이 쉽게 실행할 수 있는 Finite Automaton으로 변환한다는 것이다. 몇몇 구현에서는 Preprocessor를 이용하기도 하는데, 이는 \p{alpha}와 같은 것을 [a-zA-Z]로 변환시켜주는 것과 같은 일들을 한다. 1. 컴파일 정규식 패턴을 정규식 패턴 객체로 변환하는 과정이 필요하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import java.util.regex.*; public class RegexEx.. [ACMICPC] 5525 . IOIOI 5525번 IOIOI 문제 보러가기 🅰 설계 1. 어떤 방법을 쓸 것인가? 가장 간단한 방법으로 모든 index 위치에서 Pn이 포함되어 있는지 확인하는 방법을 생각할 수 있다. 약 O((2N+1)*M) = O(NM) 정도의 시간이 걸린다. 이 방법으로 서브태스크1은 통과할 수 있다. 그러나 서브태스크2는 O(NM) = O(10^6 * 10^6) = O(10^12) 정도가 걸려 위의 방법을 사용하여 통과할 수 없다. 다음으로 생각할 수 있는 것은 '확인한 지점을 다시 확인해야하나?'라는 의문을 가질 수 있다. 예를 들어 IOIOIOI라는 문자열이 있을 때 0번째 indexI부터 IOIOI까지 확인했다면 그 후로는 5번째 이전의 index는 확인할 필요가 없다. 이후에 OI가 붙는지 아닌지만 확인하면 된다.. [ACMICPC] 1389 . 케빈 베이컨의 6단계 법칙 1389번 케빈 베이컨의 6단계 법칙 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? 각 번호에서 다른 번호로 이동하는 데 얼마나 걸리는지 확인하는 법으로 크게 두 가지로 생각했다. BFS 1부터 N까지의 점에서 각각 시작해서 다른 모든 점까지 도착하는 시간을 계산하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738static int solveByBfs(){ int ansval = Integer.MAX_VALUE; int ansnum = 0; for(int i=1;i tmp){ ansval = tmp; ansnum = i; } } return an.. 이전 1 2 3 4 다음
