algorithm

어느 한 지점에서 다른 한 지점까지의 최단 시간을 구해야 하므로 다익스트라를 먼저 생각한다.다익스트라를 구현하되, 최단 시간의 경로에 포함된 간선들 중(역 추적을 이용해 경로 파악) 하나를 골라 검문을 세우고 다익스트라를 다시 돌려 최단 시간을 구한다. 이 과정을 모든

0,0에서 10000, 10000으로 가야하는데 이분탐색으로 연료통의 용량을 정하고 정한 연료통의 용량을 토대로 bfs를 돌려 최대 k번을 경유할 때 10000, 10000로 갈 수 있는지 없는지를 파악을 한다.현재 지점 x1, y1에서 x2, y2로 갈 때에 거리는d

내일로 티켓을 이용했을때와 이용하지 않았을때의 요금을 비교해서 내일로 티켓을 사는것이 더 좋으면 'Yes' 출력 그 외의 경우는 'No' 출력하는 문제.내일로는 ITX-새마을, ITX-청춘 무료이용, S-Train, V-Train 반값 이용 가능하다.각 도시 이름에 m

벡터에 'A'로 n개 만큼 할당을 하고 맨 뒤에서부터 Z로 교체할 수 있으면 교체하고 교체하지 못한다면 현재 위치보다 앞에 있는 A의 개수들과 현재까지의 채운 가중치를 통해 현재에 어떤 알파벳이 들어가야할지 알 수 있다.boj/17828PS/17828.cpp

선분들을 오름차순으로 정렬을 먼저 하고, 출발점과 도착점이 작은 선분 부터 순서대로 각각 순회하는데 도착점을 기준으로 도착점보다 출발점이 같거나 크다면 겹치지 않는 것이고, 도착점보다 출발점이 작다면 겹치는 선분이다.출발점과 도착점이 작은 순서대로 순회하기 때문에 앞으

한번에 사각형을 그릴때 최대 몇번을 연필을 올려야하는지 구하는 문제.사각형의 각 모서리를 사각형의 인덱스로 마킹하고 이미 마킹되어있다면(겹쳐서 한번에 그릴 수 있다면) 마킹되어있는 인덱스와 현재 인덱스를 유니온하여 최대 몇개의 부모 노드로 나뉘어지는지만 구하면 된다 유

각 도시에서 각 면접장까지의 거리를 구하려면 각 도시마다 다익스트라를 돌려야하므로 그래프를 역방향으로 입력해서 각 면접장에서 각 도시까지의 거리를 구하도록하고 그중에 최대값을 구한다.boj/17835PS/17835.cpp

하나는 사용 중인 컴퓨터의 끝나는 시간과 그 컴퓨터의 번호의 정보를 가지고 있는 큐와, 지금 사용 중이지 않은 컴퓨터의 번호의 정보를 갖는 두 개의 우선순위 큐를 사용하여 문제를 해결한다.처음 입력받은 데이터들을 오름 차순으로 정렬을 하고 차례대로 끝나는 시간과 현재

벡터에 x1, x2, 통나무 번호를 저장하고 오름차순으로 정렬을해서 우선 순위 큐를 사용하여 pq.top()에 있는 통나무와 현재 확인하고 있는 통나무가 겹치는지 아닌지 확인할 수 있고반약에 겹친다면 유니온 파인드를 이용해서 하나의 집합에 합쳐준다. 그렇게되면 같은 집

싸지방에 간 준하의 심화 버전인 것 같다.먼저 우선 순위 큐 두개를 사용하는건 마찬가지. 하나는 계산을 하고 있는 사람들의 정보이고 하나는 계산을 하고 있지 않은 빈 계산대의 정보다.계산을 하고 있는 사람들의 정보인 pq는 끝나는 시간, 계산대 번호, 회원 번호의 정보

플로이드 와샬 알고리즘으로 i에서 j 까지가는 최소 거리를 구해주고n의 제한이 최대 10이므로 10! = 3,628,800 으로 완전탐색으로 풀이가 가능하다.외판원 순회알고리즘으로 최대 16!까지 풀이가 가능하다고 하지만 잘 모르므로 추후에 공부하기로 했다.boj/17

d31을 선언하고 다이나믹 프로그래밍으로 문제를 풀이한다.di (인덱스 i부터 j까지 팰린드롬이 되는 부분 수열의 개수) 라고 생각했을 때길이가 1인 문자열은 팰린드롬이고길이가 2인 문자열은 팰린드롬이 2개 또는 3개(ab와 같이 문자가 다른경우 2개, aa와 같이 문

n == 1 일때 답이 여러개로 나올 수 있으므로 A출력 .n == 2 일때 arr0과 arr1이 같다면 arr2도 같을것 이므로 arr0 출력 그게아니라면 답이 여러개일 수 있으므로 A 출력.ax0+b=x1, ax1+b=x2→a(x1−x0)=x2−x1 이므로a = (

10^16을 2진수로 바꿨을때 55자리의 2진수로 바뀐다.배열 d는 자리수가 i+1개인 2진수의 1의개수의 누적합이다. (i == 2일 경우 3자리 2진수 까지의 1의 개수 누적합)1자리는 1 하나로 d0 = 12자리는 1011d1 = 1 + 33자리는100101110

s1을 짧은 기어, s2를 긴 기어로 두고 s2를 중심으로 s1을 가지고 s2의 왼쪽에서, 오른쪽에서, 안쪽에서 슬라이딩 해보면서 기어가 맞물릴 수 있는지 확인한다.단순히 2와 2가 만나는 경우를 제외하고는 다 맞물릴 수 있다고 간주한다.ans의 기본 최대값은 s1의길

백트래킹 형식으로 푼 문제, 맨 앞쪽 자리수부터 채워나가면서 진행해준다.크게 최대 자리수가 한 자리 수이고 맨 앞자리 수를 채워야할 때, 최대 자리수가 한 자리 수가 아니고 맨 앞자리 수 를 채워야할 때, 그 외 맨 앞자리 수를 채울 때가 아닐 때로 나누어,최대 자리수

N이 1,000,000이므로 O(n^2)이 아닌 O(nlogn)의 방법으로 풀어야 되는 문제이다.LIS를 nlogn으로 푸는 방법은 lower_bound를 이용하면 간단하다.원리는 가장 마지막 원소가 작으면 작을수록 같은 길이의 수열중에서도 LIS가 가장 길 수 있다는

트리의 중위 순회 후위 순회를 입력 받아서 전위 순회의 결과를 출력하는 문제분할 정복으로 풀이를 한다.위 트리에서 후위 순회로 각 서브트리에 대해서 마지막 원소는 트리의 부모 노드가 된다.ex) 후위 순회 - 8 9 4 5 2 6 7 3 (1) <- 부모 노드이자

최소 스패닝 트리를 구성하는 문제, 먼저 Edge라는 구조체를 만들어 간선의 양 정점과 거리를 저장할 수 있도록한다우선 순위큐를 사용하고 정점간의 거리를 기준으로 오름차순으로 정렬할것이기 때문에 cmp함수를 작성해준다.크루스칼 알고리즘을 사용할 것이기 때문에 유니온파인

딱 봐도 DP냄새를 풍기는 문제int di의 이차원 배열로 i번째 포도주 까지 j번 연속해서 마셨을 때 포도주의 최대 양이라고 했을 때di은 i번째 포도주를 안마셨을경우고이전에 2번 연속으로 마셨을때 최대량이전에 1번 마셨을 때 최대량이전에 안마셨을 때 최대량중에 최대

먼저 입력을 양수, 음수 각각 따로 벡터에 저장을하고 0입력의 개수는 따로 변수에 저장한다.그리고 음수는 내림차순으로 정렬, 양수는 오름차순으로 정렬한다.정렬했으므로 양수는 큰수부터 두개씩 묶어서 곱하면되는데, 1과 2같은 경우에는 더하는게 더 값이 크므로 더한값과 곱

숫자가 최대 50만 자리이기때문에 string 형태로 입력을 받아야한다.스택을 사용하여 먼저 맨처음에는 입력받은 문자열 s의 front -> s0을 스택에 넣어주고 시작한다.이후 si가 스택의 top보다 작거나 같으면 그냥 스택에 넣어주고si가 스택의 top보다 크다면

고객의 수를 최대 1000명 늘이기 위해 투자해야하는 돈의 최소값을 구하기위해 dp의 배열의 인덱스의 최대 값은 홍보당 비용이 최대 100이므로 1000 x 100 = 100,000으로 잡는다.d비용 = 해당 비용으로 얻을 수 있는 고객의 최대 수예제 입력12 23 5

한 면만 보이는 경우, 두 면만 보이는 경우, 세 면이 보이는 경우를 나누어서 생각을 해야한다.한 면만 보이는 경우는 $$5 (n - 2) (n - 2) + 4 (n - 2)$$개 이고두 면만 보이는 경우는 $$8 (n - 2) + 4$$개 이고.세 면이 보이는

김지민의 번호와 임한수의 번호를 토대로 그림을 그려서 잘 보면 짝수 번호는 그 다음 라운드에서 절반이 되고 홀수 번호는 그 다음 라운드에서 절반 + 1이 된다.그리고 만나서 서로 같이 경기를 치루면 둘의 번호는 같아진다.그러므로 번호가 같아 질 때 까지 위의 규칙대로

정수 1을 1, 2, 3으로 나타내는 방법은 1로 1개 이고정수 2를 1, 2, 3으로 나타내는 방법은1 + 12로 2개 이고정수 3을 1, 2, 3으로 나타내는 방법은1 + 1 + 12 + 11 + 23으로 4개 이다.4부터는 di-3에서 각각에 3을 덧붙여 주면 되

BFS를 통해서 $$A10 +1$$과 $$A 2$$를 반복 push해서 cnt값을 세어주면 된다.boj/15988PS/15988.cpp

최소의 강의실을 사용하려면 최대한 겹치지 않게 강의들을 배치해야된다.먼저 강의 시간들을 오름차순으로 정렬을해서 끝 지점을 기준으로 문제를 해결한다.정렬된 강의들을 하나씩 순회하면서 현재 강의의 시작 시간이 우선 순위 큐에 들어있는 강의의 끝 시간 보다 크다면 이미 강의

입력 받은 값들을 정렬을하고 중복을 제거하여 따로 저장을 해두면입력 받은 값보다 작은 값들의 개수를 lower_bound(이진 탐색)을 통해 찾을 수있다.처음에는 map을 통해서 작은 값부터 idx를 매겼지만 시간초과로 인해 바꿨다.아마 lower_bound와는 다르게

회의의 시작시간을 기준으로 정렬을 하고 우선 순위 큐를 사용하여 그리디하게 문제를 풀어나간다.먼저 정렬을 한 후 첫번째 회의(가장 빠르게 시작하는 회의)의 회의 종료시간을 우선 순위 큐에 push하고그 다음 회의를 순서대로 순회하면서 q.top() <= vi.fi

빙산의 높이를 입력받을 배열(arr) 하나와 해당 빙산의 주변의 0의 개수를 저장해둘 배열(arr2)을 추가로 활용한다.먼저 dfs를 돌아 dfs가 몇번에 나누어서 돌았는지(divide)를 체크해주고dfs를 도는 동안 해당 빙산의 주변에 바다가 몇 방향이나 있는지 체크

먼저 입력 값들을 알파벳 순서대로 정렬을 해주고 백트래킹을 통해서 완전 탐색을 실시한다.적당히 값들을 다 뽑아주었으면 알파벳 순서대로 정렬되어있는지 체크를 하고, 모음이 1개 이상이고 자음이 2개 이상인지 체크를하고 모두 통과되면 출력해주는 방식으로 풀었다.boj/17

3차원 배열을 선언한다.dik 에서 i,j,k 각각은 i초에 j번 움직였을경우에 k에 위치해 있다는 뜻이다.i초에 1번에서 자두가 떨어질 경우에는1번 위치에 있을 경우는 i-1초에 1번에 있을 경우와 i-1초에 2번에있다가 1번으로 왔다는 것으로$$di1 = max(d

오름차순으로 정렬을 하면 첫번째 원소와 마지막원소의 차이가 최대가 되므로 난이도가 높아진다.높이의 차가 최소가 되려면 대략적으로 이런 양상의 높이 분배가 되어야한다.이것은 가장 작은 수를 기준으로 오름차순으로 가장 작은 수의 왼쪽, 오른쪽에 번갈아 가면서 추가하는 것과

이차원 배열을 이용해 풀이한다.di에서 i번째 음악에 j번째 볼륨이 될 수 있는지 없는지 1과 0으로 나타낼 것이다.초기엔 s의 볼륨으로 시작하므로 d0 = 1로 설정해주고, 그 이후로는 0이상 m이하의 볼륨을 모두 순회하면서 0 미만 또는 m이 넘지 않는 선에서 가능

최장증가수열, 최장감소수열을 구하면된다.연속한 수열에 대해 길이를 구해야 하므로 바로 전 원소만 체크해주면된다.boj/2491PS/2491.cpp

dpi로 i챕터까지 j일이 남았을 때 읽을 수 있는 최대 페이지 수로 정의한다.이중 for문을 사용해서 i챕터를 읽을 경우와 읽지 않을 경우를 모두 확인한다.i챕터를 읽을 경우에는 i-1 챕터까지 확인한 결과 중 j-arri일을 사용해서 읽은 최대 페이지 수 + i챕터

돌 게임 3의 반대로 생각하면 된다. boj/9658 PS/9658.cpp

숫자의 합이 1로 끝나는 경우의수, 2로 끝나는 경우의 수, 3으로 끝나는 경우의 수를 저장하기 위한 2차원 배열을 사용한다.di = i의 숫자를 만들기 위한 j로 끝나는 숫자의 경우의 수라고 생각한다.d1 = 1 -> 1개d2 = (1 + 1) -> 1개d2 = 2

문제를 풀면서 좌절감을 크게 느꼈던 문제. 오랫동안 알고리즘 문제를 풀어오면서 실력이 늘지않았다는것을 다시한번 느끼게 됐다. 바텀업 방식을 버리고 탑다운 방식으로 연습을 해보기로 했다.dp배열은 이차원 배열로 dpi 일때 i까지 j번을 걸쳐서 갔을 경우 최대 기내식 점

Top-Down DP 연습을 위한 문제DP배열은 DPW로 W,H는 각각 남은 한 조각짜리 알약, 반 조각짜리 알약이다.n개의 한 조각짜리 알약으로 시작해서, 한 조각 짜리를 반으로 쪼갤지, 반 조각 짜리를 먹을지 나눈다.한 조각짜리를 모두 먹었다면 반 조각짜리 밖에 먹

문제를 모두 B로 칠할 때와 R로 칠할 때 두 가지 경우의 수를 고려하여 최소값을 출력한다.이전 색깔이 어땠는지에 따라 arr배열에 +1을 해주는지 아닌지 정한다.B로 먼저 색칠하고 필요 부분에 R을 색칠할 경우시작 지점이 R이면 B로 색칠했다가 R로 색칠해야하므로 a

다익스트라 알고리즘을 활용해 a위치에서 b위치까지의 최단거리를 구해주면 풀 수 있다.요구르트 아줌마의 이동경로를 순회하면서 요구르트 아줌마의 현재 위치를 갱신해주며 다익스트라 알고리즘을 이용해 누적된 시간(거리)를 구한다. 그 시간과 내 시작위치에서 요구르트 아줌마의

l과 r을 지정해서 경우에 따라 조정해가면서 문제를 풀어나간다.sl과 sr이 다를 경우에는 왼쪽, 오른쪽 각각 하나씩 제거 해보면서 팰린드롬이 되는지 확인을 한다.sl과 sr이 다를 경우에 각각 제거해서 확인한 후 cnt가 여전히 0이면 유사회문도 되지 않는 것이므로

idx가 n-2까지 도착했을때 val이 n-1번째 피연산자 값과 같다면 그 등식은 올바른 등식이므로 return 1을해주고 아니면 0을 해준다.val이 20이 넘어가거나 음수가 나올경우는 성립하지 않으므로 0을 반환한다.idx번째에서 계산 값이 val일때 올바른 등식의

이분탐색을 통해 공정 라인을 몇개로 둘지 결정을 하고 결정한 라인으로 모두 소화할 수 있으면 true를 반환하고 소화하지 못한다면 false를 반환하는 방식으로 문제를 해결한다.그 과정에서 가장 사용시간이 적은 공정 라인을 선택해야 하므로 우선 순위 큐를 이용해서 계속

map과 우선순위 큐를 사용하면 간단히 풀리는 문제, 작은 실수로 계속 풀리지 않아 고생했었다.type 1을 입력받으면 map을 사용해서 map에 등록된 상인이 아니라면 idx를 부여해준다.그리고 그 이름에 부여된 idx를 통해서 우선순위큐에 정보의 값들을 넣어준다.t

괜히 어렵게 생각해서 훨씬 간단히 풀 수 있는 문제를 어렵게 풀었다.출제자가 권장하는 풀이방법과 아이디어는 거의 비슷하지만, 먼저 입력 숫자들을 쪼개서 백트래킹 형식으로 푸는 방법을 택했지만 상당히 코드가 지저분해지고 복잡해졌다.핵심은 숫자 0, 1, 2, 3, 4,

이분탐색을 통해 각 높이에 몇개의 석순, 종유석이 파괴될지 구한다.석순, 종유석 따로 입력을받아 이분탐색을 위해 정렬을 하고, 1부터 최대 높이 h까지 이분탐색을 통해 몇개가 파괴될지 각각 구해주면 된다.석순이 몇개 부숴질지 구하는 이분탐색에서는 r+1에 부숴지는 석순

오른쪽, 아래, 오른쪽 위 대각선, 오른쪽 아래 대각선에 대한 오목 여부를 체크하는 함수를 만든다육목일 경우에는 승리에서 제외하기위해 처음(cnt == 1)일 경우에 반대편 즉, 오른쪽일 경우 왼쪽편에, 아래쪽일 경우 위쪽편에 같은 색깔의 돌이 있는지 확인해서 존재한다

1년 전쯤에 한번 풀고 다시 푸니까 어떻게 풀었는지 기억이 안났던 문제, 직감상 우선순위 큐를 두 개를 사용해서 풀어야한다고 생각했다.최대힙, 최소힙을 이용해서최대힙의 top, 최소힙의 top에 중간값을 후보를 위치할 수 있도록 구현을 한다.그렇게하려면 최대힙의 원소

한 줄로 입력된 문자열을 3X3으로 먼저 바꿔준다.그리고나서 O가 이겼는지 X가 이겼는지, O는 몇개가 나왔는지 X는 몇개가 나왔는지 체크를 해준다.O와 X는 동시에 이길수가 없다.그리고 X가 이길 경우에는 X의 개수가 O의 개수보다 1개 많아야한다.O가 이길 경우에는

모든 개미가 가장 빨리 떨어지려면 막대를 절반 부분을 기준으로 왼쪽 오른쪽으로 각각 떨어지면 된다. 그 중 가장 안쪽에 있는 개미가 떨어지게 되는 시간이다.모든 개미가 가장 느리게 떨어지려면 절반을 기준으로 오른쪽에있는 개미가 왼쪽으로 가서 떨어지거나 왼쪽에 있는 개미

문제 풀이 예를들어 강연의 데드라인이 2일이라면 굳이 1일에 강연을 할 필요가없다. 1일에 하든 2일에 하든 강연을 하면된다. ㄱ 문제 링크 boj/2109 소스코드 PS/2109.java

세그먼트트리 유형이 코테에서 몇번 나오는 것을 봤기때문에 이참에 세그먼트 트리에대해서 완벽하게 알고 넘어가고자 공부를 했다.세그먼트 트리는 이진트리로 배열의 구간에 대한 문제를 빠르게 해결할 수 있다.이진트리이므로 O(logN)의 시간복잡도로 성능이 굉장히 좋다.이번

지난 포스팅에서 다루었던 세그먼트 트리(구간합)의 응용 문제다.특정 구간내의 최솟값과 최댓값을 찾는것이므로 이번에는 구간 합이아닌 구간 최소,최대값을 구할 것이고, 구간의 최솟값을 저장할 세그먼트 트리와, 최댓값을 저장할 세그먼트 트리를 따로 만든다.그 후, findM

이전에 풀었던 백준 2357번 - 최솟값과 최댓값에서 최솟값만 구하는 문제로 구체적인 설명은 이전 포스팅을 확인하면 된다. boj/10868 PS/10868.java

세그먼트 트리를 이용해서 푸는 문제.세그먼트트리에는 구간의 곱을 저장해준다. % 1000000007는 잊지않고 꼭 해준다.find 함수에서는 구간의 곱을 찾는데 이전에 풀었던 구간 합 구하는 문제에서는 범위를 벗어나는 경우에 0을 반환했지만 이번에는 '곱'을 하는 것이

약속의 기대 행복값이 $H{i}$라면 이 행복값으로 기분을 음수가 되지 않게 유지할수 있는 날짜는 $H{i}$ + 1일 이다.(행복값이 2라면 2, 1, 0으로 3일을 유지할 수 있음)그러면 유지할 수 있는 날짜를 모두 더하고 방학의 기간 m에서 빼면 인호가 기분이 우

플로이드 와샬 알고리즘으로 풀이 가능하다.먼저 각 지점에서 각 지점까지의 거리를 저장하는데 이때 거리가 1000이하인것만 저장하고 그 이상은 갈 수 없으므로 987654321등 큰값으로 지정해두고플로이드 와샬 알고리즘을 통해서 시작 지점에서 도착지점까지의 거리를 구해서

문제에서 연속한 K의 신호등이 존재하길 원하므로 연속한 6개를 확인하면 된다대신, 처음부터 6개의 신호등을 확인해서 몇개의 신호등이 고장났는지 확인해주고, 이 구간을 창문 밀듯이 오른쪽으로 밀어주면서 왼쪽끝지점 오른쪽 끝지점을 확인해주면서 수리할 신호등의 개수를 더하거

두개의 C중 하나를 시작지점으로 두고 BFS를 진행한다. 큐에는 좌표, 레이더 개수, 방향을 넣어둔다. BFS를 진행하면서 만약 가야하는 방향이 현재 저장되어있는 방향과 다르다면 꺾는다는 뜻이므로 거울을 하나 늘리는것이다. 그러므로 다음 큐에 삽입할때는 레이더 개수를

어떤 한 지점에서 8방향에 그 지점의 높이보다 높은곳이 없다면 산봉우리라고 간주하는데, 그 산봉우리의 개수가 주어진 입력에서 몇개인지 구하는 문제.dfs와 산봉우리가 되는지 안되는지 찾아주는 flag를 이용해서 풀이한다.먼저 내 코드에서는 flag가 false를 반환한

반지름이 큰 순서대로 내림차순으로 정렬을 해서 배치해주고 가장 최근에 배치해준 원과 지금 배치해야하는 원이 겹치는지 안겹치는지 확인만 하면된다정렬을 하기위해서 우선순위큐를 사용했고 일반 배열 + Sort를 사용해도 될 것이다.가장 최근에 배치해준 원의 정보를 담기 위해

먼저 1에서 15까지의 숫자에 대응하는 이진 딸기 문자열을 만들어줬다.숫자를 이진수로 바꾸고 1에는 딸기 0에는 V를 붙이면된다.이제 N을 입력받는데, N이 1~15라면 그냥 리스트에서 바로 찾아서 쓰면된다.만약에 16을 넘어간다면 순서는 15에서 1로 내려가고 2에서

문제 설명이 잘 이해가 안됐었다.이 부분이 무슨말인지 잘 몰라서 예제를 보고 대충 짐작을 해서 풀었다.그냥 잘 배치해서 모두 강화를 눌러도 강화의 영향을 제일 적게(시계 방향으로 제일 적게 퍼지게)즉 중복이 많게 만들어란 말이었다.중복이 가장 많게 만드려면 가장 강화력

다익스트라 알고리즘을 활용해서 친구집으로부터 각 지점까지의 최단거리를 구해 풀면된다.각 친구 집으로부터 각 지점까지의 최단 거리를 구하고난 후특정 지점에서 각 친구집까지의 3개의 거리 중 최소 거리들을 구하고 그 중 가장 먼 거리인 지점을 출력하면 된다. boj/22

에라토스테네스의 체로 먼저 소수리스트를 만들고, 그 소수들을 모두 조합해서 소수끼리 더해서 만들 수 있는 수, 소수끼리 곱해서 만들 수 있는 수인지 아닌지의 여부를 check배열과 check2배열에 각각 저장을한다.그리고 재귀를 통해서 숫자를 만들어 주고 그 숫자가 문

투 포인터 활용 문제이다.데이터를 입력받고 오름차순으로 정렬을 한다.최소값을 구하기위해서 최소값을 초기화 해주는데 약 10억 이상의 숫자를 해야될 것같다.(처음에 습관처럼 987654321 -> 9억정도의 값으로 했다가 틀림, 문제를 잘 읽어보자)먼저 l=0, r=0

투 포인터를 활용한 문제, 연속된 k개의 구간에서 어떤 종류의 초밥이 선택되었는지 기록하는 check배열을 활용한다.먼저 처음 k개의 구간에서 어떤 종류의 초밥이 선택되었는지 체크하고, 구간을 한칸씩 옮기면서옮겨진 후 새로운 r의 접시에는 어떤 초밥이 들어있는지, 옮겨

이번 주말에 코딩테스트를 쳤는데 히스토그램과 유사한 느낌의 문제가 나와서 한번 풀어 봤다.도저히 내 머리로는 풀진 못하고 다른분들의 글들을 참고해서 풀었다.분할 정복방식과 스택을 이용한 방식이있는데 나는 스택을 이용한 방식으로 풀어봤다.배열을 처음부터 순회하면서 현재

숨바꼭질 1과 비슷하지만 방법의 개수까지 세어줘야 하므로 방문 처리를 push할 때 말고 pop할 때 해줘야한다.push할 때 방문 체크를 해준다면 다음과 같은 문제가 발생한다.예를 들어 n=1, k=4일때, 아래와 같은 상황에서 첫번째 경우에 4를 만나 방문 체크를하

숨바꼭질 2와는 다르게 순간이동 소요시간이 0초다.그냥 cur_pos(현재 위치)가 k일때 큐에 담고있는 pos(위치), cnt(소요시간) 정보를 이용해서가장 최소 소요 시간을 갱신하며 마지막에 출력하면된다. boj/13549 PS/13549.java

도둑루피를 통해 잃은 돈이 가장 적게 n-1칸에 도착해야 하므로, 최소 비용을 구할 수 있는 다익스트라 알고리즘을 사용해야함을 유추할 수 있다.다익스트라 알고리즘을 사용하면 간단하게 풀린다. boj/13549 PS/13549.java

n이 최대 500이기때문에 dfs로 풀면 시간초과가 발생한다.그렇기 때문에 특정 지점에서 특정 지점까지 거리를 구하면서 해당 거리를 현재 가지고 있는 체력과 우산의 내구도로 갈 수 있는지, 갈 수 있다면 얼만큼 소비해서 가는지 등을 구해서 일일이 좌표를 한칸씩 움직이지

부분합 + 이분탐색으로 풀 수 있다.먼저 presum 배열에 i번째 까지의 홀수의 개수를 저장한다.그리고 for문으로 n의 인덱스를 순회하면서 이분탐색을 수행한다.이 이분탐색은 i번째 인덱스를 r로 두고 r과 가장 멀리떨어진 l 즉 최소 l값을 구하는 역할을 한다.l이

이 문제 또한 가장 긴 짝수 연속한 부분 수열 (small)과 같이 부분합 + 이분탐색으로 풀 수 있다. 이번에는 좀 다르게 풀어볼 것이니 부분합 + 이분탐색의 풀이를 보고싶다면 가장 긴 짝수 연속한 부분 수열 (small) 풀이 포스팅을 확인하면 된다.또 다른 풀이

이 문제는 어떤 호선에 어떤 역이 있는지, 어떤역은 어떤 호선에 포함되는지의 정보를 모두 가지고 있어야한다.그러므로 두개의 배열을 사용했는데 배열 a에는 어떤 호선에 어떤 역들이 있는지를 저장하고배열 b에는 어떤 역이 어떤 호선에 포함되어있는지 역번호에 따른 호선의 정

문자열 끝을 확인하면서 사전순으로 더 앞서는 문자를 추가해주는데, 만약 같은 문자가 나왔다면 더 깊게 파고들어서 사전순으로 앞서는 문자가 나오는쪽을 추가해주면된다.만약 더 파고들었는데 문자가 양쪽 모두 같아서 결국 추가가 안됐다면 어느 한쪽이든 넣어주면된다. boj/

스택을 두개를 사용해서 커서의 왼쪽에 있는 문자, 오른쪽에 있는 문자를 담는다.커서가 왼쪽으로가면 왼쪽에 있던거를 오른쪽으로 옮기면되고오른쪽으로 가면 오른쪽에 있던거를 왼쪽으로 옮기면된다. boj/1406 PS/1406.java

이분 탐색을 통해 선분의 시작지점 전으로는 몇개의 점이 있는지, 선분의 끝지점 이전으로는 몇개의 점이 있는지 확인하고 둘을 빼주면 선분의 시작과 끝을 포함한 부분에 몇개의 점이 있는지 구할 수 있다. boj/11663 PS/11663.java

입력되는 숫자들의 제한을 보면 10만, 10억.. "칭호는 전투력 상한값의 비내림차순으로 주어진다" 등 이분탐색으로 풀어야 한다는 힌트가 조금씩 보인다그러므로 이분탐색으로 풀면된다. boj/19637 PS/19637.java

입력되는 숫자들의 제한이 100만, 10억 등 O($$N^2$$) O(N) 등으로는 풀기 어려울 것 같아 다른 방법을 먼저 생각해야한다.이분탐색을 사용해서 푼다면 풀 수 있다.먼저 팀 목표레벨을 먼저 정하고 그 목표레벨을 달성할 수 있는지 체크를 하고, 팀 목표 레벨의

n이 최대 5000이므로 단순히 재귀를 통해서 조합을 구하는 것은 무리라고 판단된다.1개, 2개, 3개를 선택할 때마다 각각 이분탐색을 사용한다면 O(logN) , O(nlogN), O($$N^2logN$$) 으로 시간안에 통과할 수 있을것 같다.먼저 정렬을 한 후,1

S에서 T를 만들려고하면 DFS형식이든 BFS형식이든 불가능하다.규칙을 이용해서 T를 S로 만들 수 있는지 확인하는 방식으로 푼다.대부분 재귀로 풀었던데 나는 BFS로 풀었다.맨 앞에 B가 있다면 이전에 규칙2를 적용해서 B를 추가하고 뒤집었다는 소리이므로반대로 맨 앞

해시맵을 이용해서 키워드가 있는지 없는지 알아내고 있다면 카운트를 하나씩 까주는식으로 구현하면 된다. boj/22233 PS/22233.java

백준 18114번 블랙 프라이데이 문제와 살짝 비슷하다고 생각이 들었다.어떤 수(A)를 만들지 선택하고 A를 만드는 두 개의 수의 조합을 찾으면된다. 두 개의 수 중 하나는 for문, 다른 하나는 (A에서 for문에서 고른 수를 뺀 수) 이분탐색으로 찾으면 O($$N^

간단한 구현문제.차례대로 들어갈 수 있는 방을 찾고 들어갈 수 있는 방이없다면 방을 만든다.이제 각 방을 출력할건데 방의 인원은 사전순으로 정렬을 해야한다.먼저 방이 꽉찼다면 Started!, 꽉 차지 않았다면 Waiting!을 먼저 출력하고, 닉네임을 사전순으로 정렬

슬라이딩 윈도우 기법을 이용하면 간단하게 풀리는 문제.먼저 1일차부터 X일동안 방문자 수를 체크하고, 그 후에 오른쪽으로 창문을 밀듯이 밀면서 양끝 값을 더해주고 빼면서 확인하면된다. 최대값이 같으면 횟수 또한 세어주면 된다. boj/21921 PS/21921.ja

0부터 W-1초까지 은행 직원이 어떤 손님을 담당하고 있는지 출력하는 문제.먼저 0초에 대기중인 N명의 손님들을 큐에 넣어주고, 1초 이후로 오게될 손님들은 해시맵을 이용해서 몇초에 어떤 손님이 들어올지 저장하게 했다. 굳이 이렇게 해시맵을 사용할 필요 없이 들어오는

문제를 본 순간 투포인터를 사용해야될 것 같다는 느낌이 들었다.어떤 숫자가 몇번이 사용됐는지 체크하는 cnt배열을 사용하면 풀 수 있다.l=0, r=0 부터 시작해서 r번째에 있는 숫자가 k번 미만으로 사용됐다면 이 숫자는 부분 수열에 포함되도 되기때문에 사용했다는 표

투포인터 또는 슬라이딩 윈도우를 활용하면 풀 수 있다.먼저 a의 개수를 세어주고 a개수만큼 인덱스 0부터 시작해서 0 ~ a의 개수의 구간에 b가 몇개인지 세어준다.그러면 0 ~ a의 구간에서는 방금 세어준 b개를 교환을 해야지 a가 연속되게 배치될 수 있다.그렇다면

단순한 구현문제, 별 다른 기술이 필요한 것이 아니고 문제를 잘 이해하고 구현하는게 핵심인 듯하다.각 칸의 hp를 저장할 배열 하나, 각 칸에 로봇이 있는지 없는지 나타낼 배열 하나, 컨베이어 벨트 위에 올라간 로봇의 위치 정보를 차례대로 담을 큐 하나를 활용한다.로봇

map을 이용해서 외울 단어의 나오는 횟수를 저장한다.외울 단어들은 Set 형식으로 저장해둔다.외울 단어와 등장 횟수를 묶어 리스트에 추가한다.문제에서 제시한 우선순위 대로 정렬함수를 짜고 정렬한다.그 후 차례대로 출력한다. boj/20920 PS/20920.jav

문제에서 개발자의 능력치가 다 다르다고 했는데 n은 10만이고 x는 최대 1만이다.실제로 x는 최대 10만이 아닌가 싶다.어쨌든 10000 x 10000으로는 문제가 풀리지 않아서 투포인터를 활용 했어야 했다.시작점과 끝점에 각각 l과 r을 두고 l, r 위치의 능력치

처음에 착각하기 쉬운게 트리를 구성해서 리프노드 까지 dfs로 파고 들어서 자식노드들의 수익을 모두 더해서 부모노드로 수익들을 올려줘야하나? 생각을 했지만 문제를 좀 더 꼼꼼하게 읽어보면 그럴 필요 없이 각 판매 내역마다 수익을 올려주기만 하면 된다.HashMap을 이

문제에 나와있는대로 구현을 했지만 시간초과가 날 줄 알고 일단 제출해보고 커팅을 해보자 하고 제출했는데 시간초과가 나지 않았다.문자열들을 백트래킹을 통해서 길이가 ordersi인 문자열의 조합을 구하고 HashMap의 key값으로 사용하고 value는 몇번 나오는지 빈

일반적인 이차원 그래프의 최단거리 찾는 문제에서 조금 더 진화해 3차원 공간에서의 최단 거리를 찾는 문제, BFS를 활용하면 간단히 풀 수 있다. boj/6593 PS/6593.java

서로 다른 용액을 섞어 0과 가장 가까운 조합을 찾는 문제 투포인터를 이용하면 풀 수 있다.양 끝에서 시작해서 l과 r을 조절하면서 최적의 조합을 찾으면된다.일단 min의 초기값은 10억 + 10억의 조합이 있을 수 있으므로 대충 21억으로 설정해둔다.두 용액을 섞은

전형적인 다익스트라 문제, 비용이 있고 최소비용에 관련된 언급이 있으면 다익스트라를 먼저 생각해보면 좋다.다익스트라 알고리즘을 사용해서 문제를 푸는 것은 다른 문제에서도 설명을 많이 했었으니까 별도의 설명은 하지 않는다.다익스트라 알고리즘의 정형화된 방식으로 코드를 짜

가장 큰 수의 위치부터 배열의 시작까지 이동하면서 제대로 정렬 되어있는 수의 개수는 몇개인지 찾으면 나머지 숫자는 무조건 이동해야한다.예를들어, 입력이 n=5이고 4 1 5 2 3이라면 4와 5는 이동할 필요가없다. 1, 2, 3만 이동하면된다. 즉 순서를 잘 정해서

bfs를 통해서 넓이를 구하고 거기에 더불어 둘레를 구해주는 방식으로 해결하면 된다.둘레는 bfs 루프의 각 지점에서 cnt = 4로 시작해서 동서남북 각 방향마다 \`넓이가 최대인 구역과 그 둘레를 구하되, 넓이가 같은 구역이 여러 군데 있다면 그중 둘레가 더 작은

단순 구현문제다.학생의 번호를 기록할 students 배열,학생 i가 j를 좋아하는지를 기록하기 위한 2차원배열 like,학생이 어디 배치되었는지 기록하는 2차원배열 map 등을 이용하여 풀이한다.규칙을 보면 아래와 같이 배치를 하라고 되어있는데 말 그대로 배치하면된다

문제에 나와있는 것처럼 왼쪽아래에서부터 오른쪽위 까지 성장 정보를 담을 배열을 사용한다.(2\*m - 1 개)문제에서 조건을 잘 살펴보면 성장도는 감소하지 않는다고 했으므로 어떤 한 위치의 성장도는 무조건 그 위치 바로 위쪽의 성장도를 따른다.0열을 제외한 모든 열은

물건 간의 대소관계를 그래프로 만들면 간단하다.1번 물건을 2번 물건과 비교할 수 있는지 판단하려면 그래프로 대소관계를 그래프로 만들어 1에서 2, 또는 2에서 1로 갈 수 있는지 확인하면된다.그렇게 하기 위해서는 플로이드 와샬 알고리즘을 사용한다.플로이드 와샬알고리즘

물건 간의 대소관계를 그래프로 만들면 간단하다.1번 물건을 2번 물건과 비교할 수 있는지 판단하려면 그래프로 대소관계를 그래프로 만들어 1에서 2, 또는 2에서 1로 갈 수 있는지 확인하면된다.그렇게 하기 위해서는 플로이드 와샬 알고리즘을 사용한다.플로이드 와샬알고리즘

BFS로 풀이할 수 있는 문제이다.불의 위치를 먼저 큐에 넣고, 마지막에 상근이의 위치를 넣어줘야한다.불을 먼저 큐에 넣어줘서 불이 있는 번지는 곳에 사람이 갈 수 없도록 해야한다.나는 실수로 상근이의 위치를 마지막에 넣어주지 않아서 문제가 있었다.그리고 각 테스트 케

문제를 느낌을 보자마자 다이나믹 프로그래밍으로 풀어야 된다는것을 알아야한다.dp 배열은 d사용된 소형 기관차의 수(dj)로 두었다.이 의미는 i번째 객차까지 확인하고, j개의 소형 기관차를 소모했을 때 태울 수 있는 최대 승객 수다.즉, 예제 문제의 예제735 40 5

탑 다운 dp 연습 겸 탑 다운 방식으로 풀이했다.최대 값, 최소 값을 모두 구해야 하므로 두 개의 dp배열, 최대 값을 구하는 함수, 최소 값을 구하는 함수 두가지를 작성했다.d배열은 최대 값을 저장하는 배열, d2배열은 최소 값을 저장할 배열이다.최대 최소를 저장해

배낭 문제 알고리즘으로 풀이할 수 있는 문제다.앱이 차지하는 메모리 용량이 $A{i}$ 소요되는 비용이 $C{i}$라고 쳤을 때 확보해야하는 메모리 용량 M 이상을 확보 했을 때 최소 비용을 구하는 문제다.그러므로 배낭 문제에 대응 해보았을 때 소요되는 비용이 배낭의

bfs로도 풀 수 있어 보이나 일단은 바텀 업 dp방식으로 풀어봤다.dpi = 첫 문자열에서 i개 만큼 사용하고, 두 번째 문자열에서 j개 만큼 사용했을 때 세 번째 문자열의 i+j까지 사용할 수 있는지 여부를 저장하는 dp 배열이다.예제cat tree tcraete에