BOJ

N과M(1)1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열. 오름차순으로 출력해야 한다. 출력 예시를 보고 떠오른 생각은 DFS방식의 depth와 방문 배열을 이용하여 재귀 형태로 푸는 것인데 depth는 M, 배열의 크기는 N이다. 가장 어려운 부분이 재귀

N과M(2)1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열. 오름차순으로 출력해야 한다. N과 M(1)과 다른 점은 고른 수열을 오름차순으로 출력 해야 하기 때문에 중복되는 수열이 존재한다는 것이다. 오름차순으로 출력 해야 하는 부분은 바로 전 숫자와 비교하는

N과M(3)1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열. 같은 수를 여러 번 골라도 된다. N과 M(2)와 다른 점은 중복이 허용된다는 것이다. 중복을 체크하기 위해 사용했던 visited배열을 사용하지 않는다. 원래 했던 방식은 System.out.pri

N과M(4)1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. N과 M(3)와 다른 점은 비 내림차순이라

N과M(5) > 문제 풀이 N개의 자연수 중에서 M개를 고른 수열 N과 M 문제는 1~4, 5~8, 9~12마다 문제의 유형이 다르다. 하지만 각 문제번호 -4 의 문제와 비슷한 점을 지니고 있다. N과M(1)의 문제와 다른 점은 숫자가 주어지고 이것을 오름차순으로

N과M(6)N개의 자연수 중에서 M개를 고른 수열고른 수열은 오름차순이어야 한다.N과M(2)와 N과M(5)를 적절하게 섞어서 풀면 된다.Arrays.sort의 시간복잡도는 Dual Pivot Quick Sort를 사용하기 때문에 O(nlogn)을 따르거나 최악의 경우

N과M(7)N개의 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.N과M(3)을 풀었을 때 처럼 중복을 체크하는 visited 배열이 쓸모 없기 때문에 이 부분을 제거하고 코드를 작성한다.

N과M(8)N개의 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.N과M(4)을 풀었을 때 처럼 전 숫자와 비교하는

N과M(9) > 특이 사항 N개의 자연수 중에서 M개를 고른 수열. > 문제 풀이 N과M(5)번과 다른점은 숫자가 주어지지만 중복된 숫자가 주어질 수 있다는 점이다. 중복된 숫자를 어떻게 처리하느냐가 관건이다. 중복을 허용하지않고 오름차순 정렬상태를 유지해야 한다.

N과M(10)N개의 자연수 중에서 M개를 고른 수열.고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.이 문제도 전에 풀었던 것과 같이 비교하는 숫자를 재귀함수에 넣어 비교 하도록

N과M(11)N개의 자연수 중에서 M개를 고른 수열.같은 수를 여러 번 골라도 된다.중복을 체크하는 visited를 사용하지 않는다.

N과M(12)N개의 자연수 중에서 M개를 고른 수열.같은 수를 여러 번 골라도 된다.고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.N과M 시리즈의 마지막 문제이다. 특별한 것은

문제 > 최소 힙 문제 풀이 자료 구조중 하나인 힙(heap)에 관한 문제이다. 이클립스 내에 구현된 우선순위 큐를 import하여 문제를 풀었다.

테트로미노문제에 도형을 돌리는 것 까지 생각하여 depth가 4인 경우를 수집하면 된다고 생각했다. 하지만 ㅗ,ㅜ,ㅓ,ㅏ 같은 경우는 따로 처리를 해야했다. depth가 3일때 4방향 탐색을 하여 이미 지나온 방향으로 한칸씩 더 가면 처리할 수 있다고 생각하여 문제를

덩치전체 사람의 수가 50 이하이기 때문에 한 사람에 대해 모든 사람을 검사하는 방법으로 풀었다. 자신보다 키와 몸무게가 큰사람이 있다면 순위를 한칸씩 내린다.

분해합설명 x

DSLR문제에서 요구한대로 구현을 시작했고 단순하게 bfs를 이용하여 계산된 결과가 답과 같으면 종료되는 식으로 구현을 했지만 예상대로 시간초과가 났다. 구현하면서도 깊이가 깊어질수록 중복된 값이 당연히 많아지고 그것에 대한 처리가 필요했다. dp를 이용하여 이미 저장

로봇 청소기따로 문제를 푸는 방식은 없고, 주어진대로 문제를 해결하기만 하면 되기 때문에 구현 능력이 중요하다. 특히, 시뮬레이션 문제는 주어진 조건을 제대로 짚고 넘어가야 한다. 코드가 길어질 수 있기 때문에 변수의 이름을 처음부터 제대로 작성하는 습관을 길러야 겠다

뱀이 문제 역시 시뮬레이션이다. 자료구조 덱을 이용해 뱀이 차지하고 있는 공간을 담아 맵에 처리해 주었고, 시간을 계속 체크해 주어 방향전환이 이뤄져야 하는 시간에 방향 전환만 이뤄지게 해주면 된다. 게임이 정확히 언제 종료되는지 종료조건에 대해서 파악하는 것이 중요하

시험 감독시험장마다 총 시험감독이 반드시 딱 한명 있어야 하므로 시험장 인원에서 B를 빼준다. 풀이가 쉬워서 다른 사람의 풀이도 봤는데, 다른 사람의 풀이는 math를 쓰지 않고 C로 나눴을때 나머지가 없으면 그대로 return하고 있으면 +1해서 return 하는 방

점프 게임두개의 리스트가 주어지고 한칸씩 이동불가 지역으로 변하면서 반드시 앞, 뒤 혹은 옆 리스트로 이동해 나가는 게임이다. 이동을 할 수 있다면 좌표와 왼쪽, 오른쪽 리스트인지 판단하는 변수를 큐에 삽입하여 해결했다. 조금 신경써야 하는 것은 두 리스트가 한 칸씩

최단 경로이 문제는 다익스트라 알고리즘을 활용하여 해결할 수 있는 문제이다. 최단 경로를 찾을 때 사용하는 알고리즘으로 구현 방법에 따라 O(V^2) 혹은 O(VlogE)의 시간복잡도를 가지는 알고리즘이다. (V = 노드의 수 E = 간선의 수) 원리는 다음과 같다.출

미세먼지 안녕!문제의 요구사항은 다음과 같다.1\. 미세먼지가 확산된다.2\. 공기 청정기가 가동된다.구현에 관한 문제는 제한사항을 잘 읽어야 한다. 그렇지 않으면 본인처럼 다시 구현해야 한다..예시다음과 같이 공기 청정기는 항상 위, 아래에서 2칸이상 띄워져 있어 C

N-Queen백트래킹에 관한 대표적인 문제이다. 퀸은 각 줄 마다 반드시 하나씩 들어가야 한다.퀸이 있는 자리에 대각선, 세로선에는 다른 퀸이 존재할 수 없다.처음엔 퀸들의 위치가 저장되있는 리스트를 만들어 x,y 좌표를 저장했는데 시간초과가 나면서 생각을 해봤지만,

문제 > 좋은수열 문제 해설 문제를 이해하기는 쉽지만 어떻게 적용해야할지 난감한 문제였습니다. n = 8일때, 12131231 인것을 보고 백트래킹으로 해결될 문제라고 생각했습니다. 문자열에 1,2,3을 순서대로 추가해 봅니다.(가장 작은 좋은수열을 찾기 위함) 추가

사다리 조작문제를 이해하는데 오래걸렸던 문제입니다. 크게 생각하면 두가지 조작을 해야합니다.사다리 놓기자신의 번호로 가는지 확인사다리를 놓으려면 사다리를 놓을수 있는지 확인해야합니다. 이미 연결되어있는 경우는 불가합니다. 저는 연결정보가 들어있는 2차원 리스트를 활용했

연구소구현력이 필요한 문제입니다. 문제에서 요구하는 것은 간단합니다.벽을 3개 세우세요.바이러스를 퍼트리고 안전 영역을 검사하세요.벽을 3개 세우는 것은 벽을 세울 수 있는 영역을 모두 리스트에 넣고 combination 돌렸습니다. 그렇게 3개의 조합이 나오면 벽을

연구소조건이 많이 달려있고, 구현력이 요구되는 문제입니다. 크게 보자면 요구사항은 두가지 입니다.먹을 수 있는 물고기를 탐색합니다.상어가 이동합니다.하지만 상어의 스펙과 제한 사항은 다음과 같습니다.초기 크기는 2입니다.크기가 작은 고기만 먹습니다.자신의 크기만큼 고기

치즈BFS 또는 DFS를 활용하는 문제입니다. 치즈로 부터 BFS,DFS를 시작하면 답이 안나오고, 가장자리에는 반드시 치즈가 비어있다는 것을 이용해 가장자리 부터 탐색을 활용하는 것이 핵심입니다. 이렇게하면 치즈 내부의 공간을 체크하지 않습니다.가장자리에서 4방향 탐

안전 영역BFS 또는 DFS를 활용하는 문제입니다. DFS로 풀었지만 백준 내 재귀 함수의 깊이가 1000으로 고정되어있어 DFS로 푸시려면 sys.setrecursionlimit(100000)를 작성하여 깊이 제한을 풀어야합니다. 최고 지점을 구한다.물을 1부터 최고

적록색약BFS 또는 DFS를 활용하는 문제입니다. 이 문제 역시 깊이 제한을 해제해야 DFS로 풀 수 있습니다. graph를 완전 탐색하여 방문하지 않은 곳을 발견하면 DFS 실행.DFS는 4방 탐색을 시작하는데, 같은 문자를 만나면 재귀호출을 하는 방식으로 짠다.DF

알파벳BFS 또는 DFS를 활용하는 문제입니다. 처음엔 DFS에 지나온 알파벳을 담고있는 list를 매개변수로 넣어 in으로 계속 체킹했는데 시간 초과가 났습니다.그래서 알파벳 개수의 크기만큼 list를 하나 만들어 체킹하는 방식으로 바꿔 시간을 줄였는데 또 시간 초과

구간 합 구하기 5N <=1024, M <=100,000의 제한조건이기 때문에 완전탐색을 이용하면M \* N ^ 2의 시간복잡도를 가지므로 당연히 시간 초과가 납니다.그래서 DP를 이용하여 풀어야 하는데, DP는 2차원 리스트를 이용합니다.DPi에는 (0,

개똥벌레종유석과 석순의 DP를 저장하는 리스트를 각각 만들어 해결한 문제입니다.만약 길이가 5인 종유석이 3개고, 길이가 4인 종유석이 2개이면, DP4 = 3+2 입니다. 개똥벌레가 4보다 길이가 긴 종유석도 반드시 통과하기 때문입니다.

숨바꼭질 5이때까지 푼 문제 중 가장 시간이 오래걸린 문제입니다..시간도 다른 문제와 달리 0.25초 안에 해결해야 하기 때문에 일반적인 bfs방식으로 풀면 풀리지 않습니다. 키 포인트는 수빈이가 도달할 수 있는 지점을 배열로 만들어 도달할 수 있는 최소 시간을 갱신하

동전 1DP는 아무리 쉬운 문제라도 문제를 부분 문제로 나눈뒤 점화식을 구하는 과정이 가장 어려운 것 같습니다.점화식은 다음과 같습니다.dpn = dpn + dpn-k (단, n-k >= 0)(n = 이전 동전으로 만들수 있는 경우의 수)(k = 현재 동전의 가치)

이친수처음에 dfs로 풀었으나, 시간 초과로 인해 DP로 풀게 된 문제입니다.n = 3100, 101n = 41000, 1001, 1010n = 510000, 10001, 10010, 10100, 10101n의 경우의 수를 조금씩 나열하다 보면 규칙이 보입니다.n은 n

문제 > 이친수 문제 해설 2차원 DP를 이용하여 푸는 전형적인 문제입니다. 준규는 오른쪽, 아래, 대각선으로 이동할 수 있지만 대각선은 이동할 필요가 없습니다. 왜냐하면, 문제에서 요구하는 것은 최대로 먹을 수 있는 사탕의 개수이기 때문입니다. 그래서 DP를 계산할

평범한 배낭2차원 DP를 활용하는 아주 유명한 문제입니다. 0-1 knapsack 문제 라고도 하며, 분할 가능한 배낭 문제(Fractional Knapsack Problem)와 다르게 그리디 알고리즘으로 풀 수 없습니다.Di = Di - 1 ( 현재 보고있는 무게보

문제DP를 사용하여 가장 긴 부분 수열을 갱신하는 문제입니다.일단 부분 문제로 나누자면 각 인덱스i 마다 0부터 i까지 중 가장 긴 수열의 길이가 들어갑니다. DP를 채우는 방식은 i 이전의 배열을 하나씩 방문하여 seqj가 seqi보다 작다면 dpi와 dpj+1(자기

암호 만들기주어진 알파벳들을 조합해 정렬하는 문제입니다.모음이 최소 하나, 자음이 최소 두개인 것을 인지하고 풀어야합니다.정규 표현식을 이용해 문제를 풀 수도 있어 첨부합니다.

LCSACAYKPCAPCAK두 개의 문자열이 주어지고 가장 긴 공통 부분 수열을 찾는 문제입니다.AC길이 : 0ACA길이 : 1 (A)ACAP 길이 : 1 (A)....ACC길이 : 1 (C)ACCA길이 : 1 (C)ACCAPC길이 : 2 (AC)이런식으로 완전 탐색을

문제 > 주사위 문제 해설 주사위의 개수가 1일 때, 계산하는 것은 각 주사위 숫자를 모두 더한뒤 가장 큰 숫자를 뺍니다. 2일 때, 정육면체는 8칸을 가지고 있습니다. 윗칸은 모두 3면만 보이고, 밑칸은 모두 2면만 보입니다. 저희가 필요한 값은 주사위 1면, 2면, 3면의 최소값이기 때문에 최소값을 구해야 합니다. 1면을 구하는 방법은 그냥 주사위의...

보석 도둑가장 먼저, 어떻게 하면 최대한 많은 가격을 이끌어 낼 수 있을지 생각해야합니다. 가방 하나당 하나의 보석만 훔칠 수 있으므로 2가지 방법을 생각했습니다.1\. 최대한 비싼 보석을 최대한 가벼운 가방에 넣는다.2\. 최대한 가벼운 보석을 최대한 가벼운 가방에

공항처음에 문제가 잘 이해되지 않아 시간이 걸렸는데, 비행기가 주어지면 1~i번 게이트까지는 자유롭게 도킹할 수 있는데, 비행기가 p만큼 들어오면 비행기를 최대한 많이 도킹시키는 것이 목표입니다.비행기가 들어오면 도킹할 수 있는 게이트의 가장 높은 번호로 도킹을 시도합

멀티탭 스케줄링이 문제는 여러 페이징 기법 중 OPT(Optimal Replacement, 최적 교체)를 활용하여 푸는 문제입니다. OPT란 앞으로 일어날 page fault정보를 예측하여 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법입니다.OPT는 앞으로

이분 그래프이분 그래프란 서로 연결된 두 노드가 각각 다른 색으로 색칠되어야 하는 그래프입니다. 이분 그래프는 이 색이 두가지로 제한 되어있습니다.DFS와 BFS의 탐색 방식으로 풀 수 있는데, 탐색을 할 때 마다 현재 색칠되어있는 색깔과 반대되는 색깔인지만 확인하면

벽 부수고 이동하기벽을 단 하나만 부수거나 부수지 않고 이동하여 최단 거리를 구하는 문제입니다.BFS로 푸시려면 벽을 부순 여부와 x,y좌표를 큐에 담아 푸시면됩니다. 일반적인 BFS와 다른 것은 방문여부 체크 리스트를 단순히 boolean 형태로 저장하면 안된다는 것

다리 만들기각 섬을 확장시켜 다른 섬에 닿으면 거리를 출력하는 문제입니다.각 섬을 넘버링한다.각 섬을 확장시킨다.크게 보면 두 가지를 진행하면 됩니다.먼저 섬을 찾은 후 번호를 매깁니다. 저는 bfs를 활용했고, dfs를 활용해도 됩니다. 이때, 각 섬의 가장 자리의

양 구출 작전처음에 문제 이해가 잘 안되서 질문 목록을 찾아본 문제입니다. 양이 들어올때마다 늑대가 먹을 수 있는 것이 아닌, 늑대가 일생에 정해진 만큼 먹으면 더이상 먹지 못하는 구조입니다.DFS로 풀 수 있는 문제이며, 제한 사항이 섬은 최대 123456개 까지 존

문제 > 섬의 개수 문제 해설 이 문제는 BFS와 DFS로 풀 수 있으며 4방탐색이 아닌 8방 탐색을 활용해야 합니다. 풀이과정은 다음과 같습니다. 이중 for문을 이용하여 그래프 전체를 탐색합니다. 1을 발견하면 answer +1. DFS 혹은 BFS 탐색을 진행

치즈이 문제는 치즈와 유사한 문제입니다. 다만 다른점은 변의 노출 개수에 영향을 받는 다는 점입니다. 문제의 요구 사항은 외부에 노출된 치즈를 녹이는 것입니다. 노출된 치즈는 외부에서부터 BFS 탐색을 이용하여 찾아낼 수 있습니다. 즉, 외부인 (0, 0) 부터 bfs

구슬 탈출이 문제는 BFS를 통해 푸는 문제이나, 구현을 하는 과정이 복잡하기 때문에 시뮬레이션으로도 분류를 했습니다.요구하는 사항은 어렵지 않습니다. 공을 사방으로 굴려 10번 안에 빨간공이 골인지점에 도착하면 됩니다. 하지만 파란공이 같이들어오면 안된다는 점이 중요

달이 차오른다, 가자bfs와 비트마스크를 활용하여 푸는 문제입니다. 키를 가지고 이동하는 문제이기 때문에 방문 체크 리스트를 3차원으로 확장하여 풀어야 합니다. 방문 체크 리스트는 boolean, int 둘 중 선택하여 풀 수 있습니다.4방 탐색을 이용하여 움직이는데

가장 긴 바이토닉 부분 수열가장 긴 바이토닉 부분 수열이란 증가하고 있거나 감소하고 있는 부분 수열을 말합니다.모든 지점에서 가장 긴 증가,감소하는 수열의 길이를 구합니다.두 길이를 더해 가장 긴 것을 채택합니다.가장 긴 증가하는 수열은 이 문제에서 구할 수 있습니다.

소형기관차2차원 DP로 푸는 문제입니다. 각 DP에 객차를 넣을지 말지 판단하는 문제라 0-1 knapsack과 유사한 문제라고도 할 수 있겠습니다. DP에는 기관차의 수, 객실번호를 인덱스로 최대 손님수를 저장합니다.ex) DP2 = 105 -> 기관차가 2대, 객실

게임 개발위상 정렬을 이용해 정점들을 모두 검사하여 값을 갱신하는 문제입니다. 왜 위상 정렬을 쓸 수 있냐면 처음 시작점이 어딘지는 모르나, 한 건물을 지어야 다른 건물을 지을 수 있는 구조기 때문에 양방향 그래프가 그려질 수 없고 사이클이 절대로 발생할 수 없기 때문

외판원 순회외판원 순회의 기본적인 문제입니다. 처음에 외판원 순회라는 알고리즘을 이해하지 못해 오래 걸렸던 문제였습니다. 외판원 순회 알고리즘을 사용할 수 있는 환경은 모든 노드가 순회가 되어야 한다는 것인데, 일단 순회만 가능하면 어떤 노드에서 시작하든 상관이 없습니

내리막 길이 문제는 DP 혹은 DFS를 이용하여 풀 수 있습니다. 주의할 점은 이 문제가 가장 빠르게 내려가는 것을 요구하는 것이 아닌, 내려갈 수만 있는 경로라면 모두 채택한다는 점입니다.가장 빠르게 내려만 간다면 오히려 쉽게 구현할 수 있습니다. 사방탐색이 아닌 오

장난감조립이 문제는 문제 특성상 사이클이 생기지 않고 시작 지점과 종료 지점이 명확하기 때문에 위상정렬을 이용해 풀 수 있습니다. 위상 정렬 알고리즘의 단계는 다음과 같습니다.노드를 연결합니다.진입 차수를 저장해 놓습니다.큐 or 스택을 이용해 진입 차수가 0인 노드들

N번째 큰 수메모리를 감안하여 문제를 푸는 것에 익숙치 않아 처음 시도때 실패했습니다. 모든 숫자를 최대 힙에 담아 n번째 나오는 숫자로 답을 구하는 방식이었습니다.1500 \* 1500만큼의 숫자가 힙에 들어가기 때문에 12MB의 메모리안에 들어올 수 없는 방법입니다

강의실 배정이 문제는 그리디 알고리즘을 이용해, 가장 수업 시간이 빠른 것들을 선택하는 문제입니다. N이 <= 200000 이므로 최대 NlogN 안에 들어오는 시간 복잡도를 가져야 시간 초과가 나지 않습니다. 정렬 카테고리에서 찾은 문제지만 고작 input을 s

AC주어진 리스트를 R 혹은 D가 저장되어있는 commands를 따라 뒤집거나 삭제를 하는 문제입니다.요구사항은 어렵지 않으나, 리스트를 뒤집을 때 실제 리스트를 만들어 reverse로 뒤집으면 당연히 시간초과가 납니다. 또, 리스트를 주는 것이 아니라 String 형

문자열 폭발스택을 이용해 문자열을 검사하는 문제입니다. 특히 문자열과 스택을 이용한 문제를 자주 볼 수 있기 때문에 연습하는 것이 좋다고 생각합니다.문자열을 받습니다.한 글자씩 스택에 넣고 넣을때마다 스택의 마지막 부분이 폭탄 문자열과 일치하는지 검사합니다.일치하면 그

고냥이투 포인터를 이용하여 문자열의 최대 길이를 구하는 문제입니다. 골드2 정도의 문제는 아닌 것 같습니다. 투 포인터를 이용해 front와 rear까지의 문자열에 대해 몇 종류의 알파벳이 들어갔는지만 확인하면 됩니다. front와 rear 포인터를 만듭니다(초기 둘

개미굴전형적인 트라이 문제이나, 트라이 알고리즘을 구현하지 않아도 풀 수 있는 문제입니다.(Trie)input이 주어지면 그것을 문자열을 저장하는 트리의 형태로 변경 후 dfs탐색을 이용하여 해결할 수 있습니다.또 다른 풀이는, 주어진 String들을 전부 리스트의 형

IF문 좀 대신 써줘칭호의 개수와 캐릭터의 개수가 둘 다 100,000 이므로, Nlog(M) or Mlog(N)안에 끝내는 코드를 짜야합니다.그래서 칭호를 기준으로 혹은 캐릭터를 기준으로 이분탐색을 진행하면 됩니다.문제에서 칭호는 비내림차순으로 이미 정렬이 되어 있기

타임머신벨만-포드 알고리즘벨만 포드 알고리즘의 가장 기본적인 문제이므로 알고리즘을 알고 있다면 풀 수 있습니다.

웜홀벨만-포드를 이용하여 음수 사이클의 존재 여부를 판단하는 문제입니다.원래의 벨만-포드 알고리즘은 시작하는 노드에서 도달할 수 없는 노드를 inf값을 주어 판단했습니다. 하지만 이 문제에서는 시작 노드가 정해져 있지 않기 때문에 서로 연결되어 있지 않은 그래프에 대해

구간 합 구하기세그먼트 트리의 대표적인 문제입니다. 자세한 설명은 여기

발전소비트 연산을 이용해 현재 어떤 발전기를 켰는지 체크하고, 메모이제이션을 활용해 시간복잡도와 공간복잡도를 줄이며 푸는 문제입니다.처음에 생각난 방식은 다음과 같습니다.이 방식의 문제점은 답이 아닌 다른 반례가 존재한다는 것입니다.다음 그림과 같이 그리디하게 풀게 된

비바라기상어 문제는 제한사항을 꼼꼼히 읽지 않으면 나중에 어마어마한 리스크가 되어 돌아오는 것 같습니다.구현 내용을 나열하자면1\. 구름 이동이 부분은 이동과 동시에 비 내리기를 같이 구현했습니다. 여기서 맵을 벗어나면 핸들링이 필요하기 때문에 그 부분을 조심하고 이동

전깃줄전봇대 두 대에서 모든 전깃줄이 겹치지 않게 최소한의 전깃줄을 걷어내는 문제입니다. 그러므로 전깃줄이 겹치는 경우의 최소한을 찾거나, 전깃줄이 겹치지 않는 최대한의 경우를 찾으면 됩니다.먼저 전깃줄이 겹치는 경우는 a -> b로 가는 전깃줄이 있다고 가정하면a+i

스타트와 링크조합을 이용해 각 팀의 시너지를 계산하는 문제입니다.먼저 사람이 최대 20명이고, 팀을 나누는 방법의 수는 20C10 이므로 184756의 가짓 수가 나오게 됩니다. 하지만 팀을 두개로 나누기 때문에 중복되는 계산이 발생합니다. 그래서 조합의 개수를 반으로

치킨 배달브루트포스를 이용하여 도시의 치킨 거리의 최솟값을 구하는 문제입니다.먼저, 치킨 거리의 최솟값을 구하는 문제이므로 치킨집을 M개로 고정시킵니다. 왜냐하면 치킨집을 M개 고르는 것이 반드시 최솟값을 가지게 되기 때문입니다.다음은 치킨집과 일반집의 좌표를 리스트에

색종이 붙이기10X10 행렬이 주어지고 1x1, 2x2, ... 5x5 색종이를 각각 최대 5장씩 사용하여 행렬을 모두 0으로 만드는 문제입니다. 여기서 색종이를 붙이려면 해당 영역이 모두 1이어야 붙일 수 있습니다.저는 총 3개의 메소드를 활용했습니다.전체 탐색 메소

청소년 상어물고기를 먹는 모든 경우의 수를 체크하고 가장 번호가 많은 경우를 찾는 문제입니다. 아기 상어보다 제한사항이 더 까다롭고 물고기와 상어의 이동이 각각 다르기 때문에 따로 구현해야하는 것은 물론, 사소한 제한사항 하나하나 꼼꼼히 읽어야 합니다.물고기의 이동에

PPAP주어진 문자열을 검사해 "PPAP"가 연속적으로 나오면 "P"로 줄이는 문제입니다. 먼저 PPAP가 있는지부터 판단해야하기 때문에 스택을 이용해 주어진 문자열을 처음부터 끝까지 삽입합니다.삽입하면서 스택의 마지막 부분을 계속 확인하는데, 마지막 부분이 PPAP면

택배보내는 마을, 받는 마을, 택배 수가 정해져 있고 배송할 수 있는 최대 박스의 개수를 구하는 문제입니다.저는 처음에 1번 마을부터 방문하여 가장 빨리 도착하는 순서대로 최대한 담았지만 다음과 같은 반례에 막혀 틀렸습니다.n : 4space : 201 4 202 3

쿼드트리주어진 2차원 리스트를 4분할하고 재귀탐색으로 답을 찾는 문제입니다.주어진 리스트를 검사해서 전부 0 혹은 1일때는 괄호 없이 반환합니다.그게 아니라면 괄호와 함께 11시, 1시, 7시, 5시 방향 순으로 재귀 탐색을 다시 진행하면 끝입니다.

탑스택을 사용하여 가장 가까우며 나보다 높은 탑의 인덱스를 찾는 문제입니다.N <= 500,000 이므로 NlogN이하의 시간복잡도를 가져야 합니다. 그렇기 때문에 마지막에서 처음까지 가장 가까운 탑을 찾는 방법인 브루트포스는 N^2의 시간복잡도를 가져 사용할 수

모노미노도미노 2위와 같은 보드가 있고, 빨간색 필드에 3가지의 도형 중 하나 (1X1, 2X1, 1X2)를 넣어 초록, 파랑칸의 끝까지 밀어넣고 모두 도형으로 채워진 행,열이 존재하면 지우며 점수를 얻는 문제입니다.저는 총 5개의 메소드를 만들어 활용했습니다. 딕셔너

문자열 게임2tc의 개수와 문자열이 주어지고 k만큼 슬라이딩 윈도우를 이용하여 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이이 두가지

스도쿠문제에서 주어진 요구사항대로 스도쿠라는 게임을 구현하면 되는 문제입니다. 주어진 board에서 0인 곳이 비어있는 자리이며 이곳을 스도쿠 공식에 맞게 숫자를 대입해야 합니다.요구되는 로직은 다음과 같습니다.해당 좌표의 행을 검사하는 메소드가 필요합니다.해당 좌표의

두 용액정수 2개를 더해 최대한 0에 가까운 수를 만들어 내는 문제입니다.N <= 100,000 이므로 Nlog(N)이하를 만족하는 알고리즘을 구현해야 합니다.저는 정렬된 배열을 포인터 2개를 사용하여 푸는 방식인 투포인터를 사용해 문제를 해결했습니다.배열을 정렬

마법사 상어와 복제삼성 기출문제인 마법사 상어 시리즈이다.마법사 시리즈 문제는 구현할 내용을 간단히 정리하고, 문제에서 주어지지 않은 엣지 케이스를 가정하는 것이 중요하다. 1\. 복제물고기가 담겨있는 board를 순회하며 Queue에 물고기의 정보들을 담아놓고 5번에

집합의 표현전형적인 Union-Find 문제이다. 단, 주의할 점은 Union-Find로 구현할 때 반드시 경로 압축을 해야만 시간초과에 걸리지 않는다.일반적인 방법으로는 다음과 같이 구현한다.하나의 노드를 기준으로 부모를 따라 계속 탐색하는 방식이다.이 방법은 치명적