유혁스쿨

블로그에는 잘못된 코드 및 설정 정보가 많은것 같다. 오류가 난 개발 환경은 인텔리제이, Maven, 외장 Tomcat이다. 우선 잘못된 정보는 아래와 같다. -Duser.language=en -Duser.region=us Tomcat Edit Configuration에서 VM Options에 위와같이 입력하면 로그는 영어로, 데이터는 한글로 출력되며, 깨지지 않는다. 그러나 AWS RDS로 오라클 DataBase 사용시 ORA-01861이라는 오류를 직면하게 된다. HTML 삽입 미리보기할 수 없는 소스 예를들어 WHERE조건절에 아래와 같은 쿼리를 작성했을 때 오류가 발생한다. WHERE AT_DATE = TO_CHAR(SYSDATE,'YYYY-MM-DD') ## AT_DATE는 Date타입이다. 해..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 동적계획법 큰 문제를 작은 문제로 나누어 푸는 방법. 복잡한 문제를 풀기 위해 작게 조각내어 문제를 풀고 합치면 된다. 정수삼각형 숫자로 구해진 삼각형이 있고 위에서부터 대각선으로만 내려올 수 있다. 내려오면서 숫자를 더했을 때 어떤 경로로 이동했을 때 가장 큰 숫자가 나오는지 가장 큰 최대값을 구하는것이 문제이다. 굉장히 많은 경우의수가 나올수 있기 때문에 어렵게 느껴질 수 있지만, 이중 하나만 때어놓고 생각해보면 7에서 3으로 가는것과 7에서 8로 가는것 둘중 어느것이 최대값으로 가는것인지 생각해보면 굉장히 단순하다. 이 작은 조각의 단위가 여러개 있는것 뿐이다. 중간의 경우 8 1 0 2 7 4 4 처음 2는 ..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 올바른 괄호의 갯수 A 입력값으로 괄호쌍의 갯수가 주어지고 이 괄호의 조합중에 올바르게 닫힌 괄호의 갯수가 몇개인지 구하는 문제 모든 케이스를 다 순회하면서 조건에 맞는 경우만 카운트한다. 괄호가 열렸다가, 닫혔다가 하면서 점점 증가하며 여러 케이스가 생기고 각 케이스에서 열리고 닫히는 순서를 달리하면서 또 다른 케이스들이 파생되기 때문에 선형적으로 증가하지 않게되므로 비 선형구조 탐색에서는 너비,깊이 우선 탐색이 있다. N = 2라고 가정 주어진 괄호를 하나씩 차근차근 쌓아나가것으로 문제를 접근한다. 열리는괄호 닫히는괄호 각각 N개씩있다. N이 2일때 열리는것 혹은 닫히는것 각각의 기준을 놓고 시작할 수 있다. 그..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 게임 맵 최단거리 미로의 시작 점에서 시작해서 목적지까지 찾아가는 최단 거리를 구하는 문제이다. 최단거리 탐색 중 BFS - 너비우선 탐색에 대한 전형적인 문제이다. 현재 시점에 움직일 수 있는 여러가지 경우의 수 중 모든 경우를 다 확인해야 한다. 맵에서 player가 특정 위치에 있을 때 대각선을 제외한 이동가능 경우의 수는 4가지 경우의 수가 나온다. 이 4가지 경우를 모두 가본다. 각 방향대로 1칸씩 움직인 이후에 다음 위치를 경우의 수 대로 생각하는 방식이다. 현재 시작점 위치를 0으로 두고 각각의 이동할 수 있는 경우의 수를 모두 가보는 것이다. 현재 위치의 수보다 1씩 더해서 이동하게 된다. 만약 벽이 ..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 의상(위장) 스파이가 위장할 수 있는 아이템들의 종류가 있다. 각 종류들을 조합해서 위장을 하게 되는데, 그 모든 경우의 수가 몇가지가 되는가 위장 용품은 착용을 할 수 있고 안할 수도 있다. 쉽게 접근하면 위장용품들의 각 갯수를 서로 곱하면 모든 경우의 수가 나온다. 하지만 착용 안할 수도 있다. 경우의 수에 1을 더해서 모두 곱해주면 된다. 모든 위장용품을 하나도 착용하지 않은 경우가 포함되기 때문에 추후 1을 빼주면 된다. 문제의 핵심은 경우의 수를 구하는 것이 아니라 아이템의 종류별로 갯수를 카운트하는데에 있다. 문제에서는 헤드기어 2종류, 아이웨어 1종류가 있다. 종류별로 총 몇개가 나오는지를 카운트 하는것..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 숫자게임 A B 두 팀의 숫자를 순서대로 내서 큰 수를 낸 팀이 승점을 갖게 된다. 숫자가 같은경우 비기는경우는 승점이 없다. A팀은 숫자와 순서가 정해져 있다. (실제 게임상에서는 B팀이 A팀의 순서는 알지만 순서에 매핑되어있는 숫자는 모른다.) B팀의 순서를 여러가지로 조합했을 때 얻을 수 있는 최대 승점이 몇인지 구한다. B팀이 배열될 수 있는 모든 경우의 수를 다 비교해 보고 그 상황에서의 승점들을 구해서 최대값을 구하면 된다. 만약 전체 모든 경우의 수를 다 확인하고, 그 안에서 내가 원하는 값을 찾는 탐색 법으로 풀수 있다. 하지만 B가 최대 승점으로 이긴다는 조건이 있고, 이 조건에 맞는 조합을 재연해 ..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 예산 각 지방에서 신청한 예산안 들이 있는데, 국가의 총 예산을 넘지 않는 선에서 수용 가능한 최대 상한가를 구하라는 문제이다. 예산의 상한가가 정해지면, 요청된 예산이 상한가보다 크거나 같을 경우 상한가 만큼만 지급하고, 상한값보다 작으면 신청된 예산값만 지급한다. 각 지방에서 신청한 예산 액이 있고, 이 예산액의 총 합이 국가에서 지정한 총예산값을 넘기면 안된다. 특정 상한값을 정하고 상한값보다 큰 경우 상한값 만큼만 제공한다. 상한값을 찾아내는것이 문제의 핵심이다. 이진탐색 주어진 데이터에서 내가 원하는 특정 데이터를 찾아내는것을 `탐색` 이라고 한다. 가장 단순한 방법은 모든 경우의 수 0에서부터 최대값 사이..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 정렬 여러개의 정수가 주어지는데, 이 정수들의 숫자를 이어붙혀 만들 수 있는 수중 가장 큰 숫자를 구한다. 6, 10 2 세개의 숫자가 주어졌다고 가정, 이때 가능한 조합은 6가지가 나온다. 그중 가장 큰 수는 6210이 된다. 핵심은 배열의 모든 요소를 사용하는 경우의 수를 모두 구하고 그중 가장 큰 값을 구하는것이며, 이때 함정은 한자릿수 두자리수 한자릿수 합치면 4자리밖에 되지 않지만 만약 배열이 3자리수 10개로 구성된다면 총 30자리의 숫자가 만들어 진다. 이는 integer의 범위가 넘어간다. double을 사용한다고 하더라도 배열이 조금만 길어진다고 하더라도 범위를 넘어가므로 Long을 사용해야 한다. ..

[ 문제 링크 ] HTML 삽입 미리보기할 수 없는 소스 [ 문제 설명 이미지 ] 더보기 탐욕법 현재(초기) 위치에서부터 모든 아파트를 순회한다. 현재 위치가 전파범위에 속하는지 확인하고 전파 범위가 아니라면 일단 기지국을 세운다. 이때, 전파 범위의 효과가 최대가 되도록 전파 유효범위 만큼 이동하여 기지국을 설치한다. 전파가 끝나는 지점 이후부터 한칸씩 이동하면서 기지국을 설치한다. 설치 도중, 만약 이미 세워진 기지국의 점파범위 안으로 들어갈 경우 일단 해당 위치에도 설치한다. 다음 위치로 이동했는데, 이미 설치되어있는 기지국의 전파범위에 포함된다면 기지국의 범위 바깥으로 이동한다. 벗어난 뒤 계속해서 마지막 아파트까지 같은 작업을 반복한다. [풀이 1] Queue사용 import java.util...

모든 알고리즘 문제들은 완전탐색을 이용해도 정답 도출이 가능하지만 비효율적인 연산과 시간을 생략하고 답을 효율적으로 도출하기 위해 여러 알고리즘을 사용한다. 동적계획법 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써, 최종적으로 복잡한 문제의 답을 구하는 방법이다. 핵심이론 원리와 구현 방식 큰 문제를 작은(부분) 문제로 나눌 수 있어야 함 작은(부분) 문제들이 반복돼 나타나고 사용되며 그들의 결괏값은 항상 같아야함 모든 작은(부분) 문제들은 한번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP테이블을 이용 이를 메모이제이션 이라고 함(시간복잡도 측면에서 유리) DP는 탑-다운, 바텀-업 방식으로 구현가능함 대표문제 피보나치수열 D[N] = D[N-1] + D[N..

조합 Combination ₙCᵣ 로 표현하고, 이는 n개의 숫자에서 r개의를 뽑는 경우의 수를 뜻한다. 조합과 비교되는 순열은 ₙPᵣ 로 표현되고 n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수로 말한다. 순열과 조합의 차이는 순서 고려 유무이다. 즉, 조합에서는 데이터 1, 2, 3과 3, 2,1을 동일한 경우로 판단하고 순열은 다른 경우로 판단한다. 일반적으로 코딩테스트의 핵심 알고리즘은 아래와 같다 그래프 DP (동적계획법) 인덱스트리 조합은 동적계획법(DP)를 이해하는데 기초가되는 알고리즘으로 코딩테스트에 자주 출제된다. 순열과 조합의 핵심이론 순열 순열의 수학적 공식 ₙPᵣ = n! / (n-r)! 예를들어 데이터 5개 중 2개를 순서대로 선택하는 경우의 수를 구한다고 가정한다. ..

① 서로의 깊이를 맞추거나, ②같아지는 노드를 찾을 때, 기존 한단계씩 올려주는 방식에서 2ᵏ씩 올라가 비교하는 방식 → 기존 자신의 부모노드만 저장해 놓던 방식에서 2ᵏ 번째 위치의 부모노드까지 저장해 둬야한다. (미리 배열로 저장해야 탐색이 가능하다.) Step 01) 부모노드 저장 배열 만들기 점화식 활용 부모노드 배열 정의 P[K][N] = N번 노드의 2ᵏ 번째 부모의 노드번호 → P[2][13] = 노드 13의 2² 번째 부모노드 점화식 (동적계획법) P[K][N] = P[K-1][ P[K-1][N] ] → P[2][13] = P[1][ P[1][13] ] 점화식에서 N의 2ᵏ 번째 부모노드는 N의 2ᵏ⁻¹번째 부모노드의 2ᵏ⁻¹번째 라는 의미 즉, k=4라고 가정한다면 K의 16번째 부모노드..

최소공통조상이란? 트리 그래프에서 임의의 두 노드를 선택했을 때, 선택한 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모노드를 탐색할 때 처음 공통으로 만나게되는 부모노드를 말한다. 핵심이론 트리의 높이가 크지 않을 때(시간복잡도 ↓)의 예시 ex) 노드4, 노드5의 LCA → 루트노드에서 탐색을 시작해 각 노드의 부모노드와 깊이를 배열에 저장한다. (여기서 탐색은 DFS 혹은 BFS 알고리즘을 사용) index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 부모노드 0 1 1 2 2 3 3 4 4 6 6 7 7 11 11 깊이 1 2 2 3 3 3 3 4 4 4 4 4 4 5 5 Step 01) 깊이가 다를경우 만약 선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부..

세그먼트(인덱스)트리 주어진 데이터의 구간 합(합배열)과 데이터 업데이트를 빠르게 수행하기 위해 고안해 낸 자료구조의 형태 더 큰 범위로 '인덱스 트리' 라고 불리며 이는 코딩테스트 영역에서 큰 차이가 없음. 구간합이 있는데 왜 세그먼트 트리를 학습하여 사용하는가? 합배열의 가장 큰 문제점은 특정 데이터 업데이트시 굉장히 느리다. 만약 1번 인덱스 값 5를 10으로 변경한다면 나머지 모든 구간에 5를 더해줘야 한다. 인덱스 0 1 2 3 4 5 6 데이터 3 5 4 2 3 7 4 합배열 S 3 8 12 14 17 24 28 index 4의 구간합인 17은 index 0 ~ 4까지의 데이터의 합이다. 합배열로는 S[4]로 표현하며 S[4] = S[3] + A[4] 라는 공식이 성립된다. 중간 영역인 ind..