코딩테스트

코딩테스트에서 가장 중요한 것은 꾸준함이 아닐까...? 🔥 코딩테스트의 중요성 신입 개발자 채용의 경우 지원 후 코딩테스트로 일정이 시작되는 경우가 대부분이다. 물론 코딩테스트를 보지 않는 경우도 있겠지만, 선택의 폭이 많이 좁아질 것이다. (신입 기준) 또한

문제 보기 > BFS로 찾은 경로는 최단 경로이다. 풀이 그래프의 한 정점(1)에서 다른 정점들의 최단 거리를 구하기 위하여 BFS 사용 가장 먼 정점들의 수를 구하기 위하여 answer, maxPath 변수 사용 정점들의 거리를 계산하기 위하여 edges, paths, visited 를 사용 간선들의 정보인 edges 에 startVertex 가 ...

문제 보기 > n개의 값 중 n개를 뽑는 순열을 백트래킹으로 찾다 보면 모든 경우의 수가 나온다. 풀이 가능한 모든 수들을 찾아내기 위하여 백트래킹 사용 "011" 의 경우 "101", "101" 등 같은 숫자가 나올 수 있기 때문에 checkedNumbers 사용 numbers.length 개의 값 중에서 numbers.length 개의 숫자를 뽑는...

문제 보기 > 트리에서 가능한 모든 경우를 찾기 위해서는 갈 수 있는 모든 노드를 대상으로 DFS 하면 된다. 풀이 이진 트리의 모든 경우의 수를 찾기 위하여 boolean 배열 visited 사용하여 DFS visited를 false로 초기화 하고 0번 노드부터 dfs() 시작 방문 안했으면 true로 바꾸고 양이면 sheepCnt++ 하고 maxS...

누적합은 1차원 -> O(n), 2차원 -> O(n^2)의 시간 복잡도를 가진다.2차원 배열의 연산을 빠르게 수행하기 위하여 누적합 사용

문제 보기 > 미니맥스 알고리즘이란 상대방의 최고의 수가 나에게 가장 최소의 영향을 끼치게 만드는 것 풀이 승자는 최대한 빨리 이기고, 패자는 최대한 오래 버티는 턴 수를 계산하기 위하여 백트래킹 사용 발판이 없어지는 경우 return 현재 턴인 플레이어의 갈 수 있는 경우의 수를 계산하여 재귀 호출 현재는 턴은 지는 경우인데 새로 계산된 턴이 이기는...

문제 보기 > 반복문에서 list를 순회하며 삭제할 때는 삭제 후 인덱스를 1 빼줘야 한다. 풀이 조합을 구하기 위하여 DFS를 사용 코스요리와 해당 코스요리 count를 저장하기 위해 Map 사용 order를 오름차순으로 정렬 후 모든 조합을 구하기 위해 dfs() 시작 조합이 완성되면 코스요리에 포함된 메뉴 수가 2개 이상인 경우만 map에 val...

문제 보기 > 문제에서 배열의 길이가 너무 길다면 이진탐색을 생각해보자. 근데 이게 레벨2라고? 풀이 특정 질문이 포함되거나 포함되지 않을 수 있기 때문에 DFS를 사용하여 map에 모든 경우의 수 넣어주기 그냥 배열을 순차적으로 탐색하여 답을 구하면 시간 초과가

문제 보기 풀이 O(nlog n) 만큼의 정렬(사실 Arrays.sort()는 최악 O(n^2)이긴 함) + O(n) 만큼의 순회로 문제를 해결하기 위해 그리디로 접근 2차원 int 배열 usages에 {startTime, endTime}인 int 배열을 입력 받음 최대한 많은 예약을 하기 위해선 endTime이 빠른 것부터 예약시키면 됨 -> 그리디 ...

문제 보기 > 이분 탐색 + 브루트 포스 조합을 기억하자. 풀이 한 번의 이동에서 옮길 수 있는 물품들의 무게의 최댓값을 효율적으로 구하기 위하여 이분 탐색 사용 해당 무게로 출발지에서 목적지까지 도착할 수 있는지 확인하기 위하여 BFS 사용 목적지와 건널 수 있는 무게를 필드값으로 가지고 있는 Bridge 사용 bridges를 만들고 초기화 시켜줌 ...

문제 보기 풀이 정방행렬을 회전하기 위해 rotateSquareMatrix 구현 lock 의 빈 부분의 수를 count에 저장 0, 90, 180, 270 만큼 차례대로 key를 회전 시킴 lock을 확장한다고 생각하여 중첩 for문을 작성함 중첩 for문 안에 key를 순회하여 일치 여부 확인함 lock의 범위 밖이면 continue key의 ...

문제 보기 풀이 작업의 시작 시간, 종료 시간을 저장하기 위해 Work 클래스 사용 Work를 저장하기 위해 ArrayList works 사용 어떠한 시각 기준으로 1초 동안 한 작업이 수행 중인지 여부를 계산하는 check() 메소드 사용 lines를 순회하며 작업의 시작 시간과 종료 시간을 구하여 works 에 저장 works를 순회하며 work의 ...

행렬을 리스트로 변환하여 풀이하면 접근하기 쉬울 때가 있다. 문제 보기 사용한 것 문제에서 주어지는 행렬, 효율적인 풀이를 위한 ArrayList matrixToList() : 행렬을 리스트로 변환. listToMatrix() : 리스트를 행렬로 변환. 두 메소드의 행렬의 정 중앙부터 시작해서 나선형으로 증가하는 인덱스를 다루기위한 로직은 다음과 같...

문제 보기 사용한 것 rows, columns 크기의 행렬 matrix rotate(): 행렬을 시계방향으로 회전하고 최솟값 반환 Queue 사용하여 구현 풀이 방법 rows, columns 크기의 행렬을 생성하고 1부터 차례대로 넣어 줌 queries.length 크기의 int 배열 answer 생성하고 answer.length 만큼 for문 돌...

문제 보기 사용한 것 최소 비용을 구하기 위한 다익스트라 알고리즘 다익스트라 구현을 위한 PriorityQueue 풀이 방법 fares로 인접 행렬 생성 출발 지점부터 모든 정점 까지 최소 비용을 다익스트라로 구하기 -> together 정점을 for문으로 돌며 해

문제 보기 사용한 것 가능한 모든 경우의 수를 구하기 위한 DFS 풀이 방법 사용 가능한 연산자를 나타내는 opNums 에 따라 dfs() 진행 depth == N이 되면 값이 min 보다 작으면 교체, max 보다 크면 교체 코드

문제 보기 사용한 것 조건을 만족하는 경우만 계산하기 위하여 Stack으로 구현한 백트래킹 사용 그래프의 순환을 판별하기 위한 visited, finished 풀이 방법 팀을 이룬다는 것 -> 순환한다는 것 순환하는 정점의 개수인 numOfCircle을 0으로 생성 for문을 돌며 index 0 부터의 정점을 시작으로 단방향으로 계속하여 이동 방문한 정...

lower bound: k값 이상이 처음 나오는 인덱스 구하기 upper bound: k값 초과가 처음 나오는 인덱스 구하기 문제 보기 사용한 것 시간 복잡도를 통과하기 위한 이분 탐색 이분 탐색 중 lower bound, upper bound 사용 풀이 방법 a, b, c, d 4가지 배열 존재 a, b 배열의 임의의 인덱스를 합쳐서 나올 수 있는 ...

문제 보기 사용한 것 시간 복잡도를 통과하기 위한 이분 탐색 이분 탐색 중 upper bound 사용 풀이 방법 간격을 1부터 마지막 집의 X좌표 - 첫 집의 X좌표 까지 이진 탐색으로 가능한지 탐색 upper bound를 사용하여 불가능한 가장 작은 인덱스 구함 일반적으로 정답은 upper bound 결과 값 - 1 하지만 마지막 인덱스가 가능...

문제 보기 사용한 것 순서가 없고 중복을 허용하지 않는 자료구조 Set 풀이 방법 Result 클래스에 Set으로 win, lose 필드 생성 Map 로 선수 별 결과를 저장 A가 B를 이기면 A win에 B, B win 추가 B lose에 A, A lose

문제 보기 사용한 것 누적 재생시간이 가장 많이 나오는 곳을 구하기 위한 누적 합 시간을 String int로 변환하는 toIntTime(), toStrTime() 풀이 방법 "HH:MM:SS" (String) -> seconds (int)로 변환하여 풀이 log

문제 보기 사용한 것 연산자 우선순위 순열을 구하기 위한 DFS 풀이 방법 DFS로 연산자 우선순위 순열을 구해 priorities에 저장하고 순열이 완성될 때마다 calcExpression()을 호출하여 해당 연산자 우선순위로 수식을 계산한다. 수식 계산은 현

getOrDefault() : 해시 맵에 있으면 가져오고 없으면 default 반환하는 메소드 문제 보기 사용한 것 연속적으로 진열 된 보석을 구입할 때 모든 보석을 구매하기 위한 최소 구간을 구하기 위해 투 포인터 사용 보석이름, 구간별 보석의 수를 쌍으로 저장하기 위한 해시 맵 풀이 방법 투포인터를 사용하여 현재 r의 개수를 증가 while 문...

문제 보기 사용한 것 최소 비용으로 경주로를 건설하기 위한 BFS 풀이 방법 코너 건설을 구현하기 위해 intn[4] cost (0 : U, 1 : R, 2 : D, 3 : L) 로 선언하고 MAX_VALUE로 초기화한다. (출발점은 0으로) BFS를 돌면서 방향을 전환하는 경우(출발점 제외)는 현재 비용에 600을 더하고, 방향을 이어가는 경우는 ...

순서에 상관 없이 방문 가능 여부만 판단하면 되는 문제도 있다. 문제 보기 사용한 것 그래프를 탐색하기 위한 BFS 선후관계를 저장하기 위한 int 배열 before, after 풀이 방법 BFS를 수행하며 다음 노드에 대해 visited를 2로 설정한다. 다음 노드지만 선후관계가 충족이 되지 않은 경우 visited를 1로 설정한다. 현재 방문 ...

재귀함수를 사용 시 쓸데 없는 호출이 있는지 확인하자. 문제 보기 사용한 것 멤버와 추천인을 저장하기 위한 해시 테이블 풀이 방법 enroll, referral을 순회하며 멤버와 추천인을 저장한다. sellecr, amount를 순회하며 판매자, 판매한 개수 * 100 로 share()을 호출한다. 이익의 90%를 자신이 가진다. 이익의 10%...

다이나믹 프로그래밍으로 풀어야 하는데 DFS로 풀이한 것 같다. 다이나믹 프로그래밍을 더 연습하자. 문제 보기 사용한 것 N을 8번 이하 사용하여 목표 값을 구할 수 있는지 판별하기 위한 DFS 풀이 방법 DFS를 진행하면서 더하거나, 빼거나, 나누거나, 곱한다. 사칙연산을 사용하지 않고 붙여서 사용하는 경우도 생각한다. (5 두번하면 55) N의 사...

문제에서 큰 값이 나올 수 있으면 long 사용 여부를 확인하자. 문제 보기 사용한 것 시간 복잡도를 해결하기 위한 이진탐색 사용. 풀이 방법 입국 심사를 기다리는 사람은 최대 1,000,000,000명, 한 사람당 최대 심사 시간은 1,000,000,000분이다

문제 보기 사용한 것 큰 문제를 작은 문제로부터 해결해나가기 위한 DP 사용. 풀이 방법 삼각형의 가장 윗 부분부터 점차적으로 문제를 해결할 것이다. i = 0 부터 for문을 돌리면서 sum()을 호출한다. sum()은 i 번째 줄과 i + 1 번째 줄을 더하여 나온 배열을 반환한다. 처음에는 왼쪽 아래 대각선으로 두 배열을 더해나간다. 두...

문제 보기 사용한 것 문제를 해결하기 위해 정렬, HashMap 사용 풀이 방법 입력 값을 arr, tmpArr 두 배열로 받는다. tmpArr을 정렬하고 map에 값과 몇 번째 순서인지 넣어준다. arr을 순회하며 map에서 해당 값의 value가 해당 값보다 큰 값의 수이므로 sb에 추가 후 출력한다. 코드

문제 보기 사용한 것 팀을 나누는 모든 조합의 경우를 구하기 위한 DFS 풀이 방법 입력을 받고 DFS를 시작한다. true, false로 팀을 구분짓는다. 팀 구분이 완료되면 각 팀의 파워의 차이를 계산하고 최소 값을 갱신한다. 코드

문제 보기 사용한 것 1, 2, 3의 합으로 나타내는 방법의 수를 구하기 위한 bottom-up 풀이 방법 d의 0 번째 인덱스에 1을 넣고 1, 2, 3의 합으로 나타내는 방법의 수를 구하기 위해 더해 나간다. 코드

문제 보기 사용한 것 계단을 오르는 점수 합을 점차적으로 구하기 위한 bottom-up 풀이 방법 연속으로 3개의 계단을 못 오른다. 따라서 현재 계단에 도착할 수 있는 경우의 수는 3칸 전 -> 1칸 전 -> 현재, 2칸 전 -> 현재 이 2가지 경우이다. 코드

문제 보기 사용한 것 연속된 색상을 선택하지 않고 집을 색칠하는 최소 비용을 구하기 위한 bottom-up 풀이 방법 연속 색상은 선택할 수 없다. 따라서 R, G, B 색상 별로 각각 자신의 색상을 제외한 가격들 중 최소를 구하여 넣어준다. 마지막 집이 R, G, B로 색칠된 결과 중 가장 최소 가격을 출력한다. 코드

문제 보기 사용한 것 한칸 혹은 두칸을 차지하는 타일로 모두 채우는 경우의 수를 구하기 위한 bottom-up 풀이 방법 결국 가로로 한 칸을 차지하거나 두 칸을 차지하는 타일로 채우는 경우의 수를 구하는 문제이다. 따라서 d의 i 번째 값을 구하기 위해 d의 i-1, i-2를 더한다. 문제에 10007로 나눈 나머지를 구하라고 나와있다. 범위 때매 그...

문제 보기 사용한 것 항상 꽃이 피어있는 최소의 꽃 개수를 구하기 위한 그리디 월별로 날짜의 수를 저장한 days 몇월 몇일인지 주어지면 365일 중 몇 번째 날에 해당되는지 반환하는 getDay() 풀이 방법 366의 크기만큼(1일 ~ 365일 계산하기 쉽게) endDays를 만들어 꽃이 피는 날짜를 인덱스로, 꽃이 지는 날짜를 값으로 getDay()...

문제 보기 사용한 것 1을 가장 적은 연산 횟수로 만드는 것을 계산하기 위한 bottom-up 풀이 방법 d의 1 번째 인덱스에 0을 넣고, i = 2 부터 num까지 1을 빼서 구한 것, 2로 나눠서 구한 것, 3으로 나눠서 구한 것 중 가장 적은 횟수를 d의 i 번째 인덱스에 저장한다. d의 num 번째 인덱스의 값을 출력한다. 코드

문제 보기 사용한 것 문자열 파싱 풀이 방법 약간 넌센스 문제인거 같다. 괄호로 표현해서 가장 작은 값을 구하는건 '-'가 한번 나오고 부터 계속해서 빼면 된다. 예를 들어 "1+2-3+4+5-6+7"이 주어진다고 가정해 보자. 1+2-(3+4+5)-(6+7)이 최소이다. 마이너스가 등장하면 다시 마이너스가 등장할 때까지 괄호로 계속 더해준 뒤 ...

문제 보기 사용한 것 최대 결과를 구하기 위한 그리디 풀이 방법 문제를 풀이할 수 있게 입력 받아 배열에 저장하고 정렬해준다. 원활한 풀이를 위해 r과 l을 사용한다. 각각 우측 인덱스, 좌측 인덱스이다. 우선 양수부터 계산하기 위해 r을 사용한다. arr의 r 번째 인덱스과 r - 1 번째 인덱스가 모두 1보다 크다면 곱하여 결과에 더해준다. 가장 큰...

문제 보기 사용한 것 그래프의 한 정점에서 다른 정점까지의 최단 거리를 구하기 위한 다익스트라 간선의 정보를 담기 위한 Edge 풀이 방법 Edge 리스트를 값으로 가지고 있는 리스트인 graph를 선언하고 초기화 해준다. 간선을 입력 받으면서 graph에 저장한다. visited와 dist를 선언하고 dist의 입력 받은 start 인덱스에 0을 입력...

플로이드 문제가 나올 때는 시간 복잡도가 O(V^3)이기 때문에 정점의 수가 100개 이하인 경우가 많다. 문제 보기 사용한 것 그래프의 모든 a, b 쌍에서 a -> b로 이동하기 위한 최소 비용을 구하기 위한 플로이드 풀이 방법 간선을 입력 받아 a -> b의 최소 비용을 저장한다. 모든 정점에 대해 -> i 한 정점에서 -> j 다른 ...

어떠한 일을 수행하는데 순서가 존재하고 순서를 위배하지 않게 나열해야 한다면 위상 정렬을 사용하자. 문제 보기 사용한 것 한 학생이 다른 한 학생의 앞에 서야한다는 정보들이 주어졌을 때 순서에 위배되지 않고 줄을 세우기 위한 위상정렬 풀이 방법 어떤 두 학생이 키를 비교한 결과들을 입력 받고 진입 차수를 기록한다. 가장 앞에 세워야 하는 학생들은 진입...

MST를 구하는 알고리즘에는 크루스칼과 프림 알고리즘이 있다. 크루스칼은 O(E log E), 프림은 우선순위 큐를 사용할 시 O(E log V)의 시간 복잡도를 가진다. 문제 보기 사용한 것 MST를 구하기 위한 프림 알고리즘 프림 알고리즘을 구현하기 위한 우선순위 큐 간선의 정보를 나타내기 위한 Edge, 우선순위 큐를 사용하기 위해 compareT...

크루스칼에서 find()를 수행하며 parent에 넣어주면 더 빠르다. 문제 보기 사용한 것 MST를 구하기 위한 크루스칼 알고리즘 root를 저장하기 위한 parent (이어져 있는지 확인) 풀이 방법 정점의 개수와 간선의 수를 입력 받고, 모든 간선들을 입력 받아 list에 추가한다. Edge의 compareTo를 오버라이딩 하고 낮은 비용 순으로...

문제 보기 사용한 것 서로 공격할 수 있는 경우를 제외하기 위한 백트래킹 풀이 방법 퀸은 같은 row에 존재할 수 없으므로 queens의 index를 row, value를 column으로 백트래킹 조건 : 이전에 배치한 퀸들이 새로 배치할 퀸을 공격할 수 없어야 함 코드

문제 보기 사용한 것 빨간색 구슬이 구멍에 통과하는 이동 횟수를 구하기 위한 BFS 빨간색, 파란색 구슬의 좌표, 이동 횟수를 저장하기 위한 Marble 이동하면 구슬들의 좌표와 이동 횟수 증가하므로 새로운 Marble 인스턴스를 만들어주기 위한 getNew() 풀이 방법 N, M을 입력 받고 현재 맵 상태를 입력 받으며 저장한다. 'R', 'B'인...

문제 보기 사용한 것 가르친 단어들의 조합을 구하기 위한 DFS 가르친 단어들을 순서에 상관없이 저장하기 위한 HashSet add()와 contains()의 속도가 O(1)이라서 사용 풀이 방법 K를 입력 받은 값 - 5로 저장한다. ('a', 'n', 't', 'i', 'c' 는 기본적으로 필요한 글자이기 때문에 제외시킬 것이기 때문이다.) 제외...

문제 보기 사용한 것 주어진 문자열을 int 배열들로 쪼개어 저장하기 위한 문자열 파싱 풀이 방법 문자열을 파싱하여 int 배열을 map에 넣고 idx를 1씩 증가 시킨다. map의 key는 배열의 길이 - 1, value는 배열이다. map의 key 0 ~ idx - 1 만큼 int 배열을 꺼낸다. int 배열을 돌며 set에 없으면 추가시키고...

문제 보기 사용한 것 불량 사용자 후보군 리스트의 경우의 수를 구하기 위한 백트래킹 풀이 방법 불량 아이디 별로 조건에 만족하는 아이디를 HashSet에 넣어준다. 이 때 서로 같은 메모리를 가리키지 않도록 매 단계마다 깊은 복사한다. 모든 불량 아이디가 채워지면 result에 담는다. result.size()를 반환한다. 코드

문제 보기 사용한 것 최대 건널 수 있는 친구들의 수를 구하기 위한 upper bound 풀이 방법 l은 1부터, r은 200,000,001부터 upper bound를 구해준다. 징검다리 돌 하나 값의 최대가 200,000,000이므로 최대 200,000,000의 친구들이 건널 수 있기 때문에 r을 200,000,001로 잡아줌 'num만큼의 친구들...

문제 보기 사용한 것 행렬을 연속해서 곱할 때 최소 연산 횟수를 구하기 위한 Matrix Chain Multiplication 알고리즘 풀이 방법 DP로 문제를 접근한다. N개의 행렬이 존재하면, M[i, j]를 i 번째 행렬 ~ j 번째 행렬까지 곱한 최소 연

문제 보기 사용한 것 2차원 배열의 (1, 1)에서 (m, n)까지 가는 경로의 경우의 수를 구하기 위한 bottom up 풀이 방법 bottom up으로 경로의 수를 저장할 dp를 할당한다. 물에 잠긴 지역은 dp에 -1을 넣어준다. 1열과 1행으로 가는 방법은 항상 하나 밖에 없으므로 1을 넣는다. 이 때 물에 잠긴 지역을 만나면 그 뒤로는 넣어...

문제 보기 사용한 것 방의 개수가 최대 10의 12승이기 때문에 배열 대신 해시테이블로 구현한 union-find 풀이 방법 find()로 현재 방에서 크거나 같은 최대한 가까운 방을 찾는다. 찾은 방을 배정하면 해당 방번호 + 1과 union()한다. 코드

문제 보기 사용한 것 가능한 경로를 구하기 위한 DFS key : 출발지, value : 목적지들 저장하기 위한 HashMap 풀이 방법 map에 출발지, 목적지 정보를 저장한다. 문제 조건에 맞게 dfs를 출발지에 "ICN"부터 넣어 시작한다. map에 출발지로 목적지들을 꺼낸다. 목적지들마다 티켓을 사용하여 해당 목적지를 출발지로 depth를 1 증...

문제 보기 사용한 것 사무실에 존재하는 CCTV를 번호, 좌표, 회전 수로 나타내기 위해 CCTV 사용. CCTV 번호와 회전 수로 가능한 방향들을 구하기 위한 getDirections() 사용. 풀이 방법 사무실 정보를 입력 받아 CCTV인 경우 번호, 좌표로 생성하여 cctvList에 추가한다. DFS를 돌며 모든 CCTV를 회전하는 가능한 경우의 ...

문제 보기 사용한 것 강의의 시작 시간, 끝나는 시간을 담은 Class 더 일찍 시작하는 강의, 더 일찍 끝나는 강의실 부터 다루기 위한 PriorityQueue 풀이 방법 classPQ에 강의의 시작 시간, 끝나는 시간을 입력 받아 Class를 생성하여 넣어준다. 이 때 Class의 우선 순위는 더 일찍 시작하는 강의가 먼저다. roomPQ에 0을...

DP 사용 시 변할 수 있는 값들을 생각해보자. 이 문제의 경우 경과한 시간과 움직인 횟수다. 문제 보기 사용한 것 경과한 시간과 움직인 횟수에 따라 최대로 획득할 수 있는 자두의 수를 구하기 위한 DP int경과한 시간(초) 인 dp 풀이 방법 dp를 intT + 1 크기로 초기화한다. (최대 T초 만큼 지나고, 최대 W 만큼 움직일 수 있음) 1...

문제 보기 사용한 것 익은 토마토 주변의 덜 익은 토마토를 찾기 위한 BFS 토마토의 타입(익음, 덜 익음, 빈 공간), 좌표, 날짜를 저장하기 위한 Tomato 풀이 방법 입력 받으면서 all에 전체 토마토 수, ripe에 익은 토마토 수, box에 입력 값으로

문제 보기 사용한 것 top-down을 사용하여 괄호 집합을 올바른 괄호 집합으로 변환 풀이 방법 문제에서 풀이 방법을 설명하고 있다. 따라서 구현만 해주면 된다. 하나의 괄호 집합은 '('의 수와 ')'의 수가 같아질 때 이다. 올바르지 않은 괄호 집합은 ')'가 '('보다 먼저 나오는 경우이다. 코드

문제 보기 사용한 것 순열을 구하기 위한 DFS 풀이 방법 가장 먼 거리를 점검할 수 있는 친구를 우선적으로 배치하기 위하여 distances를 내림차순으로 정렬한다. for문을 돌며numOfFriends를 1부터 최대까지 순회한다. 현재 numOfFriends 만큼 순열을 구해 order에 저장한다. order를 통하여 벽을 모두 점검할...

문제 보기 사용한 것 도착하는 최단 시간을 구하기 위한 BFS 드론의 좌표, 이동 횟수, 수평 or 수직을 저장하기 위한 Drone 풀이 방법 드론은 2칸을 차지하니 수평, 수직일 때 메인으로할 좌표를 정한다. 필자는 지도상으로 수평일 때 왼쪽 좌표, 수직일 때 위 좌표로 정했다. visited를 intN[2]로 초기화한다. 같은 좌표여도 수평...

문제 보기 사용한 것 문자열을 문자 하나씩 노드로 트리에 저장한다. 풀이 방법 문자 하나를 노드로 트리에 저장하여 풀었지만 시간 효율성을 통과하지 못했다. Trie를 사용하여 다시 한번 풀어봐야겠다. 코드

문제 보기 사용한 것 순열을 구하기 위한 DFS 풀이 방법 줄을 서는 경우의 수를 구한 뒤 조건을 확인한다. 코드

문제 보기 사용한 것 자카드 유사도를 구하기 위한 HashMap 풀이 방법 str1, str2를 소문자로 만들고 두 글자씩 끊어 map1, map2에 1 저장 중복된 문자면 value 1 증가 공백, 숫자, 기호 등이 포함되면 추가 X map3에 교집합 넣어줌 map4에 합집합 넣어줌 map3, map4에 저장된 모든 value를 더하여 답을...

문제 보기 사용한 것 대기실에서 거리두기를 제대로 하고있는지 확인하기 위한 BFS 풀이 방법 대기실마다 BFS해서 거리두기를 제대로 하고있는지 확인 visited를 선언하고 'P'인(응시자) 좌표를 q1에 넣어줌 q1에서 하나씩 꺼내어 q2에 저장하고 q2로 BFS 시작 꺼낸 뒤 visited true로 만약 현재 꺼낸 것이 이동했고, 'P'이면 거...

문제 보기 사용한 것 (0, 0) ~ (N - 1, M - 1) 최단거리를 구하기 위한 BFS 풀이 방법 q의 원소로 {x 좌표, y 좌표, 거리} int 배열를 사용하여 풀이 코드

문제 보기 사용한 것 배열에서 임의의 두 수의 차이가 m보다 클때 가장 작은 경우를 구하기 위한 투포인터 풀이 방법 N이 10만이므로 O(n^2)은 100억으로 효율성을 통과할 수 없다. 따라서 투포인터로 풀이한다. 배열 arr을 오름차순 정렬한다. 0번째 인덱스를 l, 1번째 인덱스를 r로 시작하여 arr[r] - arr[l]을 diff에 저장...

문제 보기 사용한 것 연속된 구간의 합들을 효율적으로 계산하기 위한 구간합 풀이 방법 구간합을 이용하여 O(n)으로 풀이한다. arr의 i 번째 인덱스에 i 번째 인덱스 까지의 합을 저장한다. l을 -1 부터 r을 0 부터 시작하여 while 문을 수행한다.

에라토스테네스의 체에서 소수인 i로 거를 때 i x j (j 사용한 것 소수를 효율적으로 판별하기 위한 에라토스테네스의 체 연속된 구간의 합들을 효율적으로 계산하기 위한 구간합 풀이 방법 N을 입력 받는다. 에라토스테네스의 체를 이용하여 N까지의 모든 소수를 L

문제 보기 사용한 것 연속 부분 증가수열의 크기를 구하는 LIS 알고리즘 풀이 방법 LIS로 풀이하되, 그 중에서도 모든 수가 1씩 증가하는 수열이어야한다. 따라서 값을 저장하는 arr 배열과 인덱스를 저장하는 pos 배열을 사용한다. 현재값 + 1의 인덱스가 현재값보다 뒤라면 1씩 증가하는 LIS가 될 수 있음을 이용하여 구현한다. 코드

문제 보기 사용한 것 N개의 색상 중 K개를 뽑는 경우의 수를 구하기 위한 bottom-up 풀이 방법 dpi는 i개의 숫자 중 j개 뽑은 경우의 수를 나타낸다. dpi는 다음의 합과 같다. dpi - 1 : i - 1 개의 숫자 중 j 개 뽑은 것 (전 순서에서 뽑았음) dpi - 2 : i - 2 개의 숫자 중 j - 1 개 뽑은 것 (이번...

문제 보기 사용한 것 시작 지점에서 목표 지점까지 내리막길만 사용하여 도달 가능한 경우의 수를 구하기 위한 top-down 풀이 방법 현재 좌표를 이미 방문한 경우 memo return 현재 좌표를 방문하지 않은 경우 visited true 현재 좌표에서 동, 서, 남, 북으로 도달 가능하고 오르막길이면 해당 경우의 수를 재귀호출하여 모두 ...

문제 보기 사용한 것 타일을 채우는 경우의 수를 구하기 위한 bottom-up 풀이 방법 a 번째 칸의 경우의 수 2칸전의 경우의 수 * 3 (이번꺼 2칸 채우기 -> 3개의 경우 존재) b(4 특수한 모양 2개 씩 존재) 코드

문제 보기 사용한 것 폐업할 매장들을 정하기 위한 DFS 집에서 가장 가까운 매장을 구하기 위한 BFS 풀이 방법 DFS로 폐업할 매장들을 정한다. BFS로 모든 집에서 가장 가까운 매장의 거리들의 합을 totalDistance에 저장하고 answer와 비교하여 더 작으면 교체한다. 코드

문제 보기 사용한 것 한 정점에서 출발 후 다른 정점에 도착하는 최단 비용을 구하기 위한 다익스트라 풀이 방법 특정 정점에서 모든 정점까지의 최소 시간은 다익스트라로 구한다. 모든 정점에서 출발하여 x에 도착하는 시간들을 goTimes에 저장한다. x에서 출발하여 모든 정점에 도착하는 시간들을 comeTime에 저장한다. goTimes[i] + co...

문제 보기 사용한 것 동생을 찾는 최소 시간을 구하기 위한 BFS 풀이 방법 순간이동(2 X x), 한칸 뒤로(x - 1), 한칸 앞으로(x + 1)를 q에 넣으면서 현재 x가 K와 같으면 answer에 time을 넣어주고 break 2배로 이동한 값(0초 소요)이 +1로 이동한 값(1초 소요)보다 항상 먼저 계산되어 q에 들어가므로, 처음으로 ...

문제 보기 사용한 것 (0, 0) -> (N-1, N-1) 까지의 최소 비용을 구하기 위한 다익스트라 풀이 방법 Node 클래스 -> 좌표와 현재까지 잃은 루피 수 q에 (0, 0)과 해당 좌표의 잃는 루피를 저장한다. 상, 하, 좌, 우 를 현재 경로를 거쳐 이동하는 것이 더 최소 비용기면 갱신한다. 코드

문제 보기 사용한 것 어떠한 숫자를 두 수의 덧셈으로 구할 수 있는지 판별할 때 하나의 수를 고정으로 놓고 더할 숫자를 탐색하기 위한 이분 탐색 풀이 방법 이분 탐색을 사용하기 위하여 정렬한다. 어떠한 수를 두 수의 합으로 구할 수 있는지 판별한다. 하나의 수를 배열에서 고른다. 나머지 두 번째 수를 이분 탐색으로 구한다. 코드

문제 보기 사용한 것 같아질때까지 탐색하기 위한 DFS 풀이 방법 DFS를 문자 하나씩 빼주면서 돌린다. 문자를 하나씩 더해주면 시간 초과 빼주면서 계산하면 "A"를 맨뒤에 더한 경우, "B"를 맨뒤에 더하고 뒤집은 경우가 진행됐을 때만 체크하여 탐색할 수 있다. cur과 target의 길이가 같아지면 같은 문자열이면 1을, 다른 문자열이면 ...

문제 보기 사용한 것 최소 횟수를 갱신하기 위한 bottom-up 풀이 방법 bottom-up을 돌면서 현재 숫자를 i라 할때 3으로 나눠지는 경우 i / 3 2로 나눠지는 경우 i / 2 i - 1 세 가지 인덱스에서 + 1한 결과물을 비교하며 dp, process 갱신 코드

문제 보기 사용한 것 0과 1의 출력 횟수를 구하기 위한 bottom-up 풀이 방법 dp를 int형 2차원 배열 n+1, 2 크기로 생성 (dp -> 0의 수 dp -> 1의 수) dp0에 1 저장 (0에서 0출력) dp1에 1 저장 (1에서 1출력) j = 2 부터 n 까지 for문을 돌며 dpj에 j-1 번째 0의 수 + j-2 번째 0의 ...

문제 보기 사용한 것 0과 1의 출력 횟수를 구하기 위한 bottom-up 풀이 방법 입력 받으면서 왼쪽 대각선으로 바로 위의 인덱스와 더해서 갱신하고, 그 다음 오른쪽 대각선으로 바로 위의 인덱스와 더한 것을 왼쪽 대각선으로 더한 값과 비교해서 갱신 코드

문제 보기 사용한 것 타일을 채우는 경우의 수를 구하기 위한 bottom-up 풀이 방법 dp의 0 번째, 1 번째 인덱스에 1 저장 (점화식을 위해 0 번째 인덱스에 1 저장) i = 2 ~ N 에서 dp[i] = dp[i - 1] + 2 * dp[i - 2] 저장 (문제 조건을 위해 10_007로 나눈 나머지로 저장) 코드

문제 보기 사용한 것 이친수의 개수를 구하기 위한 bottom-up 풀이 방법 이친수가 될 수 있는 경우는 다음과 같다. 이번 차례에 0이 오는 경우는 모두 가능 -> dp[i - 1] 이번 차례에 1이 오는 경우는 앞이 0이 아닐 때 가능 -> dp[i - 2] 코드

문제 보기 사용한 것 구간의 최대 합을 구하기 위한 bottom-up 풀이 방법 arr에 숫자 입력 받음 (인덱스 1부터) 인덱스 1부터 구간을 계속 더하거나 새로 시작하거나 둘 중 큰 값 선택 dp 중에 가장 큰 값 선택 코드

문제 보기 사용한 것 증가 구간 중 최대 값을 찾기 위한 bottom-up 풀이 방법 num에 비교한 숫자를 저장하되 num보다 작은 값은 비교 X(이미 비교한 인덱스에 포함되어있음) 코드

문제 보기 사용한 것 점차적으로 증가하는 수열 중 가장 긴 크기를 구하기 위한 bottom-up 풀이 방법 0 ~ (N - 1) 까지 for loop 돌면서 -> i arr[i] 에 입력 값 저장, dp[i]에 1 저장 (i - 1) ~ 0 까지 감소하는 for loop 돌면서 -> j arr[i] > arr[j] 이면 dp[i]를 자신과 dp[j]...

문제 보기 사용한 것 Sticker 클래스 int num, rowLen, colLen 차례대로 스티커 면적, 열 수, 행 수 int matrix 스티커 있으면 1, 모눈 종이면 0 rotate() 90도 회전한 Sticker 인스턴스 반환 Notebook 클래스 int rowLen, colLen boolean is...

문제 보기 사용한 것 점화식을 세워 풀이하기 위한 bottom-up 풀이 방법 i 번째 -> i-2 번째 + i-3번째 코드

문제 보기 사용한 것 점화식을 세워 풀이하기 위한 bottom-up 풀이 방법 i > j 일때 dp[i]는 dp[j]보다 크거나 같음 만약 j에 시작하는 일이 i보다 빨리 끝나거나 같으면 dpi]는 dp[j] + infos[j(info[1])보다 크거나 같음 모든 경우들을 따져서 가장 큰 값을 dp[i]에 저장 코드

문제 보기 사용한 것 점화식을 세워 풀이하기 위한 bottom-up 풀이 방법 뒤에서 부터 계산 i 번째 날의 예약이 기한 안에 (n + 1보다 같거나 작음) 끝낼 수 없으면 dp[i] = dp[i + 1] 끝낼 수 있으면 p[i] + dp[i + t[i]]와 dp[i + 1] 중 큰 값을 dp[i]에 저장 전자는 i 번째 날의 예약을 채택하는 ...

문제 보기 사용한 것 점화식을 세워 풀이하기 위한 bottom-up 풀이 방법 앞이 1인 경우에만 0 가능 -> dpi = dpi - 1 앞이 8인 경우에만 9 가능 -> dpi = dpi - 1 1 ~ 8 의 경우 2를 예를들면 앞이 1이거나 3이면 가능 -> dpi = dpi - 1 + dpi - 1 코드

문제 보기 사용한 것 점화식을 세워 풀이하기 위한 bottom-up 풀이 방법 i보다 작은 수 j에서 arr[j] 코드

문제 보기 사용한 것 점화식을 세워 풀이하기 위한 bottom-up 풀이 방법 dpi : 이번꺼 선택 X dpi - 1 중 가장 큰 값 dpi : 이번꺼 처음으로 선택 dpi - 2 중 가장 큰 값 + arr[i] dpi : 이번꺼 두번째로 선택 dpi - 1 + arr[i] 코드

문제 보기 사용한 것 점화식을 세워 풀이하기 위한 bottom-up 풀이 방법 2차원 int 배열 dp 선언 (1차 : 아이템 수, 2차 : 무게) 새로운 아이템을 고려하면서 dp 갱신 dpi : 새로운 아이템을 넣는 것과 넣지 않는 것 중 큰 값 새로운 아이템의 무게가 w, 가치가 v라면 새로운 아이템을 넣는 경우는 dpi = dpi - 1 +...

문제 보기 사용한 것 5번의 방향을 다르게 하여 최대값을 구하기 위한 백트래킹 풀이 방법 기존 값 copy에 복사 방향에 맞게 이동 후 재귀 5번 이동하면 최대 값과 answer을 비교하여 answer 갱신 answer 출력 코드

문제 보기 사용한 것 네 방향으로 방문하기 위한 dx, dy 방문 여부를 확인하기 위한 visited BFS로 뿌요들을 없앨 수 있는지 확인하기 위한 Queue 뿌요들을 없앨 수 있으면 기록하여 없애기 위한 Stack 풀이 방법 > count 0부터 시작 -> 한 번에 없앨 수 있는 뿌요들 모두 없애기 -> 한 번이라도 없앴다면 1 증가 / 못 없앴...

문제 보기 사용한 것 LCS의 길이를 구하기 위한 bottom-up 풀이 방법 > "ACAYKP", "CAPCAK"로 생각해보자. "ACA", "CAPCA"의 경우 LCS 길이가 3이다. 이는 "AC", "CAPC"의 LCS 길이에서 1을 더한 값과 같다. 따라서 다음과 같은 점화식을 세울 수 있다. "ACA", "CAP"의 경우 LCS 길이가 ...

문제 보기 사용한 것 문자열에서 원하는 문자만 추출하기 위한 문자열 파싱 앞, 뒤에서 모두 원소를 꺼내기 위한 Deque 풀이 방법 명령들의 집합인 문자열 p가 주어지는데 'R'은 뒤집기, 'D'는 삭제이다. 따라서 Deque을 사용한다. !reverse 상태에서 삭제하려면 removeFirst(), reverse 상태에서 삭제하려면 removeLa...

일반적으로 구현한 다익스트라의 시간 복잡도는 O(V^2) 우선순위 큐를 사용해 구현한 다익스트라의 시간 복잡도는 O((V + E)logV) 문제 보기 사용한 것 최소 비용 경로를 탐색하기 위한 다익스트라 풀이 방법 경로를 출력하는 것 제외하면 일반적인 다익스트라 문제와 동일하다. 경로 출력을 위해서 2차원 리스트 path를 사용한다. 다익스트라 진...

문제 보기 사용한 것 점화식을 세워 풀이하기 위한 bottom-up 풀이 방법 n = 1 : {1} n = 2 : {1, 1}, {2} n = 3 : {1, 1, 1}, {2, 1}, {1, 2}, {3} n = 4 : {1, 1, 1, 1}, {2, 1, 1}

문제 보기 사용한 것 문자를 추가시키다 조건이 일치하면 폭발시키기 위한 Stack 풀이 방법 입력 받은 str의 문자를 하나씩 stack에 넣는다. stack의 크기가 key의 크기보다 커지면 터질 수 있는지 탐색한다. 탐색 시에는 역순으로 두 문자열이 일치하는지 확인한다. pop()하면 문자열이 역순으로 출력되기 때문에 reverse()를 사용한다...

문제 보기 사용한 것 새로운 수가 들어갈 자리를 효율적으로 탐색하기 위한 lower-bound 풀이 방법 문제에서 주어진 것은 가장 긴 증가하는 부분 수열의 크기를 구하는 것이다. 따라서 정확한 수열을 구할 필요 없다. 따라서 다음과 같은 방법을 사용한다. 10, 20, 15, 30, 25, 50 10 10, 20 10, 15(교체) ...

문제 보기 사용한 것 경사로의 도움을 받는 지, 경사로의 도움 없이 얼만큼 이동했는지를 나타내는 int support 풀이 방법 >support는 내리막 경사로를 사용할 때 경사로 크기에 따라 커진다. support는 오르막 경사로를 사용할 때 음수 크기가 경사로의 크기만큼 충분해야 한다. support는 한칸씩 건널 때마다 1 감소한다. 풀이의 ...

문제 보기 사용한 것 연속한 수열 중에서 같은 수가 중복되지 않는 수열의 개수를 구하기 위한 투포인터 풀이 방법 기준 인덱스 l에서 r을 증가시키면서 같은 수가 중복되지 않는 수열의 개수를 구한다. 구간 l ~ r에서 연속한 수가 없었다면, 개수는 r - l - 1 이다. 연속한 수가 등장하거나 배열의 크기를 초과했다면 l을 1 증가시킨다. r까지의...

문제 보기 사용한 것 미로 탐색을 위한 BFS 풀이 방법 BFS 수행 시 불을 사람보다 먼저 q에 넣는다. 그렇다면 visited가 false가 되어 해당 칸으로 이동할 수 없다. 코드

문제 보기 사용한 것 우선순위 큐 풀이 방법 우선순위 큐를 최소, 최대 2개 생성한다. Map을 사용하여 두 우선순위 큐의 싱크를 맞춘다. 동기화에는 remove가 사용되며 우선순위 원소 중 처음으로 존재하는 값이 나올 때까지 허수를 삭제한다. iCt와 dCt로

문제 보기 사용한 것 훔칠 수 있는 보석의 최대 가격을 구하기 위한 그리디 가방에 넣을 수 있는 보석 중 가장 큰 가치를 고르기 위한 우선순위 큐 풀이 방법 items에 보석들을 무게 오름차순, 무게가 같으면 가치 내림차순으로 저장한다. bags에 가방의 무게 오름차순으로 저장한다. 훔칠 수 있는 보석들 중 가장 큰 가치의 보석을 빼내기 위한 pq를...

문제 보기 사용한 것 add(), remove()를 O(1)로 수행하기 위한 야매 연결 리스트 풀이 방법 LinkedList를 사용하기에는 포인터 개념이 없으므로 add(), remove()에 O(n)이 걸린다. 따라서 해당 구현체를 사용하면 시간 초과가 걸리므로, 야매 연결 리스트를 사용한다. 데이터를 담을 dat, 이전 주소(인덱스)를 저장할 p...

문제 보기 사용한 것 모든 경우의 수를 탐색하는 브루트포스 풀이 방법 > (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) 문제의 조건은 위와 같다. 따라서 트램폴린을 놓는 경우의 수를 n, m으로 반복문 돌린다면, 최악

문제 보기 사용한 것 contains()를 O(1)로 사용하기 위한 HashSet 풀이 방법 입력 값 -> set 입력 값이 set에 존재하면 1, 안하면 0으로 변환 후 출력 코드

문제 보기 사용한 것 전체를 탐색하기 위한 브루트 포스 풀이 방법 크기가 같아질 때까지 문자를 앞, 뒤로 추가할 수 있다. -> 현재의 차이가 최대이다. 먼저 입력 받은 문자열이 이후 입력 받은 문자열의 길이보다 항상 같거나 작으므로, 이후의 문자열의 크기를 맞춰 차이의 최소를 구해 출력한다. 코드

문제 보기 사용한 것 점화식을 세워 문제를 해결하기 위한 bottom-up 풀이 방법 VIP회원은 좌석이 고정이므로 확인을 위해 set에 넣어준다. 한명뿐이면 경우의 수가 1개이므로 dp의 1번째 인덱스에 1을 넣어주고 점화식을 세우기 위하여 0번째 인덱스에도 1을 넣어준다. for문에서 현재 인덱스나 이전 인덱스가 VIP석이면 섞어 앉을 수 없으...

문제 보기 사용한 것 왼쪽, 오른쪽으로 연속적인 회전을 구현하기 위한 재귀 함수 풀이 방법 톱니바퀴 회전 입력 값마다 operate()로 톱니바퀴를 작동시킨다. 하나가 돌아가면 나머지도 돌아갈 수 있으므로 leftRotate(), rightRotate()를 호출한다. leftRotate()의 경우 index가 벗어나거나 같은 극이여서 회전하지 못하는...

문제 보기 사용한 것 풀이 방법 rotate()는 단순 구현(굴린 방향에 맞게 주사위 재배치) 주사위를 굴릴 수 있는지(벗어나지 않는지)확인 후 dice rotate() 주사위 굴린 후 윗면 출력 만약 굴린 좌표의 map 값이 0이라면 주사위 아랫면 값 복사 0이 아니라면 map 값을 주사위 아랫면에 넣은 후 0으로 설정 코드

문제 보기 사용한 것 특정 정점에서 시작하여 다른 정점까지의 최단 경로를 구하기 위한 다익스트라 다익스트라 구현을 위한 PriorityQueue 풀이 방법 Edge를 v : 도착 정점, w : 간선 가중치로 만들고 Comparable을 간선 가중치 오름차순으로

문제 보기 사용한 것 점화식을 세워 문제를 풀이하기 위한 bottom-up 풀이 방법 dp[i]의 최대 값은 다음 중 최대 값과 같다. arr[i] + dp[0] arr[i - 1] + dp[1] arr[i - 2] + dp[2] 반복.... 따라서 이중 for문을 사용하여 점화식을 세워 dp[]를 n까지 점진적으로 계산하면 된다. ...

문제 보기 사용한 것 빈 영역의 개수, 빈 영역 하나당 크기를 구하기 위한 BFS 풀이 방법 2차원 visited 배열을 만들어 입력 받은 사각형에 포함되는 영역을 true로 만든다. 입력이 끝나면 visited에 대해 2중 for문을 돌며 빈 영역(false)을 발견하면 numOfEmptyAreas을 증가시키고 BFS 돈다. BFS 돌면서 방문한 ...

문제 보기 사용한 것 DFS, BFS와 그래프를 나타내기 위한 인접행렬 풀이 방법 입력 값으로 인접행렬인 adj를 초기화한다. adj와 stack을 사용해 DFS, 결과를 dfsPath에 저장한다. adj와 q를 사용해 BFS, 결과를 bfsPath에 저장한다.

문제 보기 사용한 것 모든 논에 물을 대는 최소 비용을 구하기 위한 크루스칼 풀이 방법 기본적으로 크루스칼 알고리즘을 사용한다. pq 초기화를 위한 2중 for 문에서 i == j의 경우, 우물을 파는 비용을 넣어주기 위해 가상의 노드(0번째 인덱스)와 연결시킨다. 코드

문제 보기 사용한 것 출발 도시에서 도착 도시까지의 버스 비용의 최소를 구하기 위한 다익스트라 풀이 방법 우선순위 큐로 구현한 다익스트라 알고리즘을 사용한다. 시작 정점의 비용을 0으로 초기화하고 pq에 넣어주면서 시작한다. pq에서 꺼낸 정점의 비용과 해당 정점이 가지고 있는 간선의 비용을 더한 값이 간선의 도착 정점의 비용보다 싸다면 교체한다. ...

문제 보기 사용한 것 최대 랜선의 길이를 효율적으로 구하기 위한 이분 탐색 풀이 방법 입력 값으로 초기화, max에 가지고 있는 랜선 중 최대 길이를 저장한다. 이분 탐색을 사용하여 필요한 랜선의 개수보다 많이 자를 수 있는 최대 길이를 구한다. 오버헤드가 발생할 수 있으므로 long 자료형이 필요할 수 있다. 코드

문제 보기 사용한 것 선분의 총 길이를 구하기 위한 그리디 풀이 방법 그리디로 풀이하기 위해 좌표들을 x 좌표 오름차순 먼저, x 좌표가 같으면 y 좌표로 오름차순 정렬한다. 오름차순 정렬된 배열을 돌면서 이전 좌표와 현재 좌표로 그리디 풀이한다. x 좌표로 오름차순 정렬되어 있기 때문에 가능한 경우의 수는 다음과 같다. 현재 선분이 이전 선분에...

문제 보기 사용한 것 배열에서 두 개의 포인터를 사용해 O(N)으로 탐색하기 위한 투포인터 풀이 방법 두 개의 포인터 l, r을 0부터 시작한다. l : 부분 수열 시작 지점 r : 부분 수열 현재 지점 r이 n과 같아지면 최대 길이를 이미 구한 것이니 while 문을 종료한다. 홀수를 제거할 기회가 남은 경우 홀수면 제거할 기회를 사용한...

문제 보기 사용한 것 조건에 맞춰 탐색하기 위한 백트래킹 풀이 방법 백트래킹 하면서 1 ~ N 까지 set 에 들어있지 않은 경우 재귀 호출 후 set에서 빼준다. 코드

문제 보기 사용한 것 숫자의 자릿수를 점차적으로 늘려 풀이하기 위한 DP 풀이 방법 2차원 dp배열을 사용한다. 1차원의 인덱스는 자릿수 2차원의 인덱스는 마지막 자리 숫자 예를 들어 dp3은 "XX1"이 된다. 자릿수를 점점 늘려 for 문을 돌며 2차원 for 문으로 다음 수의 마지막 자리 숫자 k가 가능한 경우를 모두 더해준다. ...

문제 보기 사용한 것 로봇 청소기를 표현하기 위한 Robot 풀이 방법 while 문을 돌며 다음과 같이 풀이한다. 방문하지 않았으면 방문 처리, answer 증가 1 : 모든 방향을 다 돌았으면 (isAllDirClean()) 뒤로 움직일 수 있으면(canBack()) 뒤로 후진 후 ct 초기화, 없으면 while 문 종료 2 :...

문제 보기 사용한 것 우선순위 큐를 사용한 BFS 풀이 방법 현재 위치에서 이어진 빈 방으로 가거나, 뚫어서 갈 수 있다. 이어진 빈 방으로 가는 것은 depth가 증가하지 않는다. 뚫어서 가는 경우는 depth가 증가한다. 따라서 빈 방으로 가는 것을 먼저 선택하기 위해 우선순위 큐를 사용하여 BFS 한다. 코드

문제 보기 사용한 것 모든 부분수열의 합을 구하기 위한 DFS 풀이 방법 DFS로 모든 부분수열의 합을 구한다. 해당 인덱스 숫자를 선택하거나 선택하지 않고 재귀 호출 모든 숫자 완료 -> 합이 s와 같으면 answer 증가 flag를 사용하여 공집합인 경우 answer을 증가시키지 않는다. 코드

문제 보기 사용한 것 이다솜파와 임도연파를 선택하기 위한 DFS 선택한 7명이 인접했는지 확인하기 위한 BFS 풀이 방법 우선 DFS로 이다솜파를 선택한다. 선택 X or 선택 O 분기처리를 사용한다. 이다솜파가 4명 이상 선택됐으면 임도연파를 선택한다. 이다솜파를 선택하지 않았는데 setY()를 호출하면 중복될 수 있으므로 flag를 사...

문제 보기 사용한 것 효율적으로 최대 카드 수를 구하기 위한 upper bound 효율적으로 원하는 카드팩 수를 만들 수 있는지 확인하기 위한 투포인터 풀이 방법 최대 카드 수를 효율적으로 구하기 위해서 upper bound를 사용한다. 선택한 카드 수로 원하는 카드팩 수를 만족할 수 있는지 확인하기 위해 투포인터를 사용한다. 선택하지 않은 카드...

문제 보기 사용한 것 뱀을 나타내기 위한 클래스 Snake 뱀의 머리의 좌표 : pos 뱀의 방향 : dir 뱀의 길이 : len 성장(사과 먹고 길이 증가) : growUp() 방향 전환 : rotate() 이동 : move() 풀이 방법 > 뱀의 머리 좌표를 계속해서 저장하고 뱀이 자신과 부딪혔는지 확인하기 위해 사용한다. ...

문제 보기 사용한 것 정규식으로 풀이하기 위한 Pattern, Matcher 풀이 방법 정규식 패턴을 만든다. -> "(100+1+|01)+" matches()로 일치 여부를 확인한다. 코드

문제 보기 사용한 것 보낼 수 있는 택배의 최대 수를 구하기 위한 그리디 풀이 방법 to 기준으로, to가 같으면 from 기준으로 오름차순 정렬한다. 각 마을당 보낼 수 있는 최대 수를 c로 초기화한다. 오름차순 정렬한 packets를 순회하며 다음 단계를 수행한다. maxNumPerTown과 packet의 to, from을 사용하여 보낼 수 ...

문제 보기 사용한 것 멀티탭에서 뽑을 전기용품을 선택하기 위한 그리디 풀이 방법 멀티탭 구멍의 순서는 중요하지 않으므로 HashSet을 사용한다. 전기용품의 사용순서를 순회하며, 이미 멀티탭에 꽂혀있으면 continue 멀티탭에 꽂을 구멍이 남아있다면 add() 멀티탭에 꽂을 구멍이 없다면 뽑을 전기용품을 그리디로 선택한다. 사용되지...

문제 보기 사용한 것 트리의 root 부터 시작하여 순회하기 위한 DFS 풀이 방법 map에 두 정점 연결 정보를 저장한다. 입력 값의 순서는 "부모 자식"이 아니기 때문에 map에 양방향으로 넣어준다. 트리에 여러 자식이 있을 수 있고, 부모까지 value인 리스트에 들어갈 수 있다. root인 1을 시작으로 DFS 한다. 리스트에 자식...

문제 보기 사용한 것 트리의 root 부터 시작하여 순회하기 위한 DFS 풀이 방법 1번 노드부터 n번 노드까지 for 문을 돌면서 이미 방문한 노드면 continue 방문하지 않은 노드면 ct 증가, DFS DFS는 방문 노드마다 visited를 true 현재 노드의 자식이 이미 visited true 라면 사이클이므로 ret...

문제 보기 사용한 것 작은 카드 뭉치부터 뽑기 위한 우선순위 큐 풀이 방법 우선순위 큐를 사용해서 가장 작은 두 카드 뭉치를 뽑는다. 카드 뭉치의 합을 answer에 더한다. 두 카드 뭉치를 합쳐 pq에 다시 넣는다. pq에 하나가 남을 때까지 반복한다. 코드

문제 보기 사용한 것 최대 컵라면 수를 구하기 위한 그리디 과제를 컵라면 수로 오름차순 하기 위한 우선순위 큐 풀이 방법 Homework를 deadline, num(컵라면 수) 필드로 만든다. 숙제를 모두 입력 받고(homeworks) deadline으로 오름차순 한다. 컵라면 오름차순으로 우선순위 큐 pq를 초기화한다. homeworks를 순회하며...

문제 보기 사용한 것 최대 컵라면 수를 구하기 위한 그리디 과제를 컵라면 수로 오름차순 하기 위한 우선순위 큐 풀이 방법 사용할 계획 날짜 오름차순 먼저, 같으면 남은 기한 오름차순 한다. 같은 사용 날짜 구간으로 묶어서 생각한다. input을 for 문 돌면서

문제 보기 사용한 것 파이프를 컬럼 마지막 인덱스까지 연결시키기 위한 DFS 설치할 파이프 방향을 최선으로 선택하기 위한 그리디 풀이 방법 > 가장 아래 row 부터 시작하여 오른쪽 아래 대각선 오른쪽 오른쪽 위 대각선 순서로 탐색해야 최선의 결과이다. 다음 row 시작시 탐색할 수 있는 조건이 더 많아지기 때문이다. isEmpty에 빈 공간...

문제 보기 사용한 것 길이가 긴 구간을 우선적으로 건너뛰기 위한 그리디 센서 조합의 시작 좌표와 마지막 좌표로 효율적으로 구현하기 위한 투포인터 풀이 방법 > 하나의 집중국이 여러 센서를 가지고 있는 조합이라고 생각하자. 각 조합들의 거리를 최대한 멀게 설정하면 집중국의 수신 가능 영역의 합이 최소화된다. 입력 받은 센서의 좌표를 배열 arr에 저...

문제 보기 사용한 것 배열의 i 번째 인덱스 ~ j 번째 인덱스 까지의 합을 효율적으로 구하기 위한 누적합 O(N)으로 배열의 가능한 구간을 탐색하기 위한 투포인터 풀이 방법 입력 값으로 누적합을 sum에 저장한다. 투포인터와 sum을 사용하여 현재 구간의

문제 보기 사용한 것 직속 관계를 그래프로 나타내고 칭찬 수치를 직속 부하에게 연쇄적으로 부여하기 위한 DFS 풀이 방법 칭찬 수치를 입력 받아서 해당 직원에게 초기화한다. DFS를 수행하며 이전 탐색까지 누적된 칭찬 수치를 현재 직원에게 부여한다. 코드

문제 보기 사용한 것 현재 스티커를 최대의 점수로 떼기 위한 bottom-up 풀이 방법 현재 스티커를 최대의 점수로 뗄 수 있는 후보는 다음과 같다. 컬럼 2만큼 전에서 같은 row의 스티커를 뗀 경우 컬럼 2만큼 전에서 다른 row의 스티커를 뗀 경우 컬럼 1만큼 전에서 다른 row의 스티커를 뗀 경우 따라서 위 3가지 경우의 최대 값...

문제 보기 사용한 것 하루에 지불할 보상금이 더 높고 다른 작업들을 덜 지연시키는 작업을 우선적으로 선택하기 위한 그리디 풀이 방법 작업의 우선순위는 다음과 같다. 하루에 지불할 보상금이 더 높은 것 다른 작업들을 덜 지연시키는 것 따라서 t / s가 더 작은 작업을 우선시한다. 만약 같다면 번호 오름차순으로 정렬한다. 코드

TreeSet은 이진탐색트리 자료구조를 사용하는 컬렉션이다. 문제 보기 사용한 것 검색과 삭제 모두 O(logN)으로 수행하기 위한 이진탐색트리 풀이 방법 TreeSet을 사용하기 위해 Problem의 우선순위를 정의한 compareTo()를 람다식으로 넘긴다. 커맨드에 따라 다음을 수행한다. "recommend" : treeSet에서 first...

문제 보기 사용한 것 조건을 만족하는 최소 숫자를 구하기 위한 백트래킹 풀이 방법 일의 자리수(idx)부터 증가시키면서 백트래킹한다. 다음의 우선순위로 '5'의 개수가 충족되거나 n의 길이까지 백트래킹 현재 자릿수가 5보다 작으면 5로 만들고 재귀 현재 자릿수가 5보다 크면 현재 자릿수에서 반올림, flag true 현재 자릿수가 5면 다...

문제 보기 사용한 것 현재 인덱스에서 특정 모양을 사용할 때 최대 크기를 구하는 findCurMax() 풀이 방법 2중 for 문으로 map을 순회하며 해당 인덱스(i, j)를 기준으로 각 도형(회전, 대칭 포함)을 사용할 때 최댓값을 구한다. 코드

문제 보기 사용한 것 i 번째 인덱스에서 시작하면 i 번째에서 끝나는 경우를 찾기 위한 백트래킹 풀이 방법 2차원 int 배열 map을 선언해서 input으로 다음과 같이 초기화한다. 0 : 가로선 없음 1 : 오른쪽 갈 수 있는 가로선 2 : 왼쪽 갈 수 있는 가로선 백트래킹을 돌며 가능한 모든 경우에 가로선을 놓는다. 매 depth에서...

문제 보기 사용한 것 현재 거리에서 가장 가까운(거리 같으면 위, 왼쪽 우선) 먹을 수 있는 물고기를 찾기 위한 BFS, 우선순위 큐 풀이 방법 현재 위치에서 먹을 수 있는 물고기가 없을 때까지 BFS 다음 좌표를 우선순위 큐를 활용해 위쪽, 왼쪽을 우선으로 탐색 물고기를 특정 개수 먹으면 아기 상어 크기 증가 코드

문제 보기 사용한 것 상어를 나타내는 Shark와 낚시터를 나타내는 Shark 2차원 배열 sharks 풀이 방법 컬럼을 순회하며 낚시꾼 한칸 이동 현재 컬럼에서 가장 가까운 상어 잡기 상어 이동 stack을 사용해서 이동시킴 s를 (R 혹은 C - 1) * 2 만큼 나머지 연산 (자기 자리로 되돌아오는 경우 배제하여 연산 ...

문제 보기 사용한 것 동전 조합의 수를 구하기 위한 bottom-up 풀이 방법 dp[0]을 1로 초기화 현재 동전을 사용한 경우를 계속해서 더해줌 (dp[k] += dp[k - coin]) 코드

문제 보기 사용한 것 행렬에서 가장 큰 1로 이루어진 정사각형을 찾기 위한 bottom-up 풀이 방법 2중 for 문을 돌면서 행렬의 현재 인덱스의 값이 1인 경우 dpi는 다음 중 최소와 같다. dpi - 1 + 1 dpi + 1 dpi - 1 +

문제 보기 사용한 것 히스토그램에서 가장 큰 직사각형을 효율적으로 구하기 위한 Stack 풀이 방법 heights의 마지막 인덱스에 -1을 넣고 stack에 -1을 push()한다. 사용할 전략이 현재 인덱스 높이가 더 작은 경우 stack에 쌓은 값들로 직사각형의 넓이를 구하므로 heights의 마지막 인덱스에 -1을 넣는 것이다. stac...