알고리즘

문제 출처프로그래머스 - 거스름돈처음에는 중복조합으로 문제를 풀어나갔지만 효율성에서 걸리게 되었다. 그래서 동적계획법을 의심을 했지만 DP에는 많이 약해서 점화식이 만들지 못해서 다른 블로그들의 정답을 보고 이해를 한다음 글을 작성한다.사용화폐와 금액대로 만들 수 있는

문제 출처금과 은 운반하기해당 문제를 보자마자 어떤 식으로 풀어야될지 아예 감을 잡지 못했다. 그래서 이곳저곳을 참고했지만 문제를 완벽하게 이해하지 못했다. 어떻게 보자마자 이분탐색이라고 알게 될까.. 비슷한 문제를 열심히 풀어야되겠다.참고사이트https://

문제 출처 : 두 수의 합 백준문제 접근1\. 해당 수열을 정렬하여 작은 수와 큰수를 더하면서 비교하기 위함2\. 왼쪽과 오른쪽으로 시작하는 값들을 더한 값을 위주로 구해야될 값이면 결과++하고 크면 오른쪽을 더 작은 값으로 옮겨주고 작으면 왼쪽을 더 큰 값으로 옮겨주

문제 합승 택시 요금노드별 최소 비용으로 최단거리로 이동해야되므로 최단경로탐색알고리즘을 이용한다. 즉 다익스트라를 사용출발 지점 -> 특정 지점 X -> 도착 지점으로 이동하는 경우와 출발 지점 -> 도착 지점 경우 중 최소 비용을 탐색출발 지점, 도착 지점(A,B)에

문제 혼자서 하는 틱택토 문제 접근방법 현재까지 한 게임의 결과가 규칙에 위반하는지 판단하여 단순히 규칙들을 구현하는 문제이다. 풀이 규칙을 위반하는 경우 후공의 갯수가 선공보다 많은 경우 선공이 후공의 갯수보다 2번 더 많은 경우 ex) 선공 3, 후공 1 선공이

문제 연속된 부분 수열의 합\*\* 비내림차순 : 오름차순으로 정렬이 되어 있는 상태이지만 같은 값이 들어있을 수 있다투포인터 알고리즘을 사용하여 풀었다.1\. 시작과 끝의 지점을 똑같은 인덱스로 표시한다.2\. 합친 값 즉 sum이 목표 값인 k보다 낮으면 끝의 지점

문제 미로탈출(https://school.programmers.co.kr/learn/courses/30/lessons/159993문제 접근1\. bfs로 출발지점에서 레버까지의 최단거리를 구한다2\. 레버까지 가지 못하면 -1 출력3\. 레버에서 출구까지 bf

문제 호텔 대실대실 시작시간 기준으로 오름차순 정렬대실 종료시간 기준으로 우선순위 큐 생성큐가 비어있다면 방하나 추가한 후 큐에 현재 대실 예약정보 저장현재 대실 예약 시작시간이 대실 중인 방의 종료시간보다 큰 경우 방추가x 새로운 예약정보 큐에 저장작은 경우 새로운

문제 - 과제 진행하기우선순위큐를 이용하여 주어진 과제들을 시작시간으로 오름차순으로 정렬멈춘 과제의 자료구조는 스택을 이용(최근 멈춘 과제부터 진행해야되기 때문에)현재 과제와 다음 해야될 과제를 비교1) 현재 과제를 끝내고 시간이 남은 경우 : 남는 시간동안 멈춘 과제

문제 큰수 찾기처음에는 완전 탐색으로 뒤에 있는 모든 숫자들을 탐색하고 비교하면서 할려고 했지만 O(N\*N)으로 시간초과가 나올 거 같아서 고민을 하던 중 가장 가까이 있는 수를 보고 스택을 이용하고자 했습니다. 1\. 맨 뒤의 숫자부터 비교 2\. 스택이 비어

문제 귤고르기정수와 정수의 개수를 저장하는 딕셔너리(hashMap)을 선언정수의 개수(values)를 내림차순으로 정렬현재 sum을 한 귤의 개수가 한 상자에 담으려는 귤의 개수(k)보다 낮은 경우 다음 귤을 추가귤의 개수(k)보다 큰 경우 break 후 결과 출력

문제 시소 짝꿍처음에는 모든 사람들의 무게들을 일일히 비교해가면서 결과를 찾았다. 당연스럽게(?) 시간초과가 났다. 시소에 탔을때 무게를 비교하기 위해서는 먼저 오름차순으로 정렬을 했다. 무게가 덜나가는 사람과 무게가 더나가는 사람이 시소를 탔을 때 시소 짝꿍이 될 수

문제 - 두 큐 합같게 만들기queue1, queue2의 합계를 각각 구한다음에 queue를 활용하여 pop, insert를 해준다.둘의 합계를 비교해서 합계가 큰 쪽에서 pop을 진행하여 작은 쪽에게 insert를 해준다. 이러한 과정을 합계가 같을 때까지 반복해준다

문제 - 우박수열 정적분문제설명대로 단순히 구현을 하면 되는 문제이다.자연수 k를 1로 만드는 우박수열을 좌표로 저장한다. 이때 1로 만들수 있는 횟수도 같이 저장0~1 ,1~2 의 각 구간별로 미리 넓이를 구한다.ranges의 범위대로 각 구간별 넓이를 더하여 결과에

문제 - 디펜스 게임무적권의 갯수만큼 우선순위 큐에 오름차순으로 정렬하여 저장(무적권을 사용할 때에는 적의 수가 큰 편인 경우에만 사용) 무적권을 사용한 적군 중 제일 작은 수와 현재 적군 수의 비교제일 작은수 < 현재 적군 수 : 현재 적군 수를 우선순위 큐의

문제 - 숫자 변환하기bfs를 이용하여 풀이방법방문처리를 위해 hashset을 이용한다. (set.contains()은 O(1)이므로) queue에 x + n, x 2 , x 3을 넣어주면서 y값이 될때에 횟수를 출력dp를 이용하여 풀이방법x ~ y까지 탐색하면서

문제 - 택배상자문제를 처음 읽었을 때 약간 문제가 이해가 되지않았다.1\. 1 ~ N까지 순서대로 택배상자가 들어온다. 2\. 택배기사가 원하는 order대로 상자를 트럭에 싫어야한다.3\. 만약 들어온 택배상자가 order와 맞지 않는 상자면 보조 컨베이어 벨트에

문제 - 숫자 카드 나누기문제의 설명대로 구현을 하면 된다. A가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 B가 가진 카드는 모든 숫자 중 하나도 나눌 수 없는 가장 큰 양의 정수 a를 구하기 때문에 카드들을 오름차순으로 정렬한 다음 제일 낮은 숫자부터 시작해서

문제 - 마법의 엘리베이터 (https://school.programmers.co.kr/learn/courses/30/lessons/148653일의 자릿수부터 현재 층의 제일 높은 자릿수까지 확인한다.5보다 큰 경우에는 다음의 자릿수를 올려주고 10 - num

문제 - 혼자 놀기의 달인해당 글을 읽는데 제대로 이해를 못하고 처음에는 순열로 상자안에 들어있는 카드 번호를 만들어서 문제를 풀었다. 이 문제는 처음부터 카드 번호를 순서대로 담긴 배열을 주기 때문에 경로탐색느낌으로 문제를 풀면 된다.우선순위 큐를 내림차순으로 정렬을

문제 - 롤케이크 자르기두개의 set을 쓰면서 왼쪽 오른쪽을 나눠서 모든 토핑의 개수를 세면서 하니 당연하게도 시간초과가 나왔다. 원소의 갯수는 1,000,000 이여서 O(N^2)이면 시간초과가 나오는 것이 당연하다. 그래서 미리 구간별로 토핑의 개수를 저장한 다음에

문제 - 등굣길이동하는 방법은 오른쪽과 아래쪽으로만 움직인다. 그래서 bfs를 이용해서 한다면 O(2^(m\*n))으로 시간초과가 발생한다. 처음 집에 있는 위치에 갈 수 있는 경우의 수는 1이다.집의 아래쪽과 오른쪽으로 갈 수 있는 경우의 수는 각각 1이다. 집의 대

문제 - 줄 서는 방법모든 순열을 구하면서 해당 k번째의 배열을 구하려고했지만 n이 20이하의 자연수로 20!이면 시간초과가 날 것이라고 예상했다.그래서 패턴을 찾다가 어떻게 해야될지 모르겠어서 다른 사람의 풀이를 보고 이해를 해서 코드를 작성했다.위에서 15번째에 있

문제 - 방문 길이이미 지나온 길은 방문 길이에서 제외합니다. 그래서 9번을 움직이지만 8,9번의 움직임은 이미 지나온 길이므로 길이는 7로 출력처음에는 방문한 곳들은 HashSet을 이용하면 위의 그림에 1번 이동과 7번 이동이 같은 것으로 판단하여 중복제거를 하기

문제 - 인사고과완호는 scores0의 점수를 가지고 있다.인센티브를 받지 못하는 대상을 제외시킨다. 근무태도 점수는 내림차순, 동료평가 점수는 오름차순으로 정렬정렬된 맨 처음값을 기준으로 제외대상을 탐색제외대상에 완호가 있는 경우 -1을 출력인센티브를 받는 대상을 근

문제 - 부대복귀처음에는 dfs로 접근을 할려고하니까 재귀호출은 아직 어려워서 stackoverflow가 계속나서 포기를 했다.모든 start지점에서 destination 지점까지 bfs를 돌려 보니 최대가 100_000 \* 100_000이라서 시간초과가 났다.미리

문제 - 양과 늑대루트노드부터 출발하면서 최대한 양을 모은다. 양과 늑대의 수가 같아지거나 늑대의 수 가 많아질 경우에는 양이 잡아먹힌다. 그래서 양의 수가 늑대보다 더 많아야된다.그래서 위의 그림은 0 -> 1-> 8-> 7-> 9-> 4 -> 6-> 5로 방문을 하

A,B의 배열을 모두 오름차순으로 정렬작은 숫자순서대로 비교를 하면서 A의 값이 B의 값보다 작은 경우에만 A의 index를 움직여준다. A의 값이 큰 경우에는 다음에도 A의 값을 사용하기 위해 유지를 해준다. 그 다음에는 다시 B의 값과 비교하면서 2,3번 반복해준다

아파트 1번부터 시작현재 위치가 기지국의 범위 안에 있는 경우에는 기지국 범위 밖으로 이동 (now + w +1 ) 만큼 이동현재 위치가 기지국의 범위 밖에 있는 경우에는 기지국 설치 후 기지국 범위 밖으로 이동

문제 - 스티커 모으기(2)보자마자 이전에 풀어봤던 문제와 비슷해서 DP임을 알았지만.. 어떻게 접근해야될지 이해가 되지 않아서 다른사람이 푼 문제풀이를 보고 이해를 했다.원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.

문제 - 징검다리 건너기징검다리를 건널 때 디딤돌을 밟고 지나간다.디딤돌을 밟을 때에는 디딤돌의 숫자가 줄어든다.디딤돌의 숫자가 0이 되면 해당 디딤돌을 밟지 못한다.k만큼의 디딤돌을 건너 뛰고 걸을 수 있다. 무조건 가장 가까운 디딤돌로만 건너뛸 수 있다.최대 몇명까

문제 - 무인도 여행단순 bfs를 사용하여 각 연결되어 있는 섬들의 값들을 합산하여 배열을 오름차순으로 정렬해주고 결과를 출력하면 된다.

문제 - 모두 0으로 만들기1.모든 점들의 가중치들을 0으로 만들기 위해서는 가중치의 합이 0이여야 가능하기 때문에 가중치의 합이 0이 아닌 경우에는 불가능(-1)출력2.트리이므로 dfs로 0부터 탐색 (어느 노드부터 시작하든 상관없다)3.탐색하면서 리프노드부터 부모노

문제 - Add Two Numbers처음 시도할때에는 링크된 노드에 대한 합산을 String을 통해 숫자를 하나씩 뽑은 다음에 더한 후 해당 값을 이용하여 String으로 변환 후 길이 만큼 ListNode를 만들어서 결과를 출력하려고 했다. 하지만 Long은 64비트

문제 - 826작업자 즉 worker는 자신의 능력을 나타내므로 능력이 difficulty보다 높을 수 없다 즉 workeri < difficultyi 그래서 최대한의 이득을 볼 수 있는 경우의 값을 출력하는 것이다.그리디로 접근을 해야된다.처음에 difficul

문제 - 1482m 개의 부케를 만들어야 된다.부케를 만들기 위해서는 k만큼 이웃된 꽃들이 필요함.꽃이 피는 날은 bloomDay에 저장되어 있다. 예시를 보면 이해하기 편하다.bloomDay가 1,10,3,10,2이며 m = 3, k =1 일 때 1일차 : O, X,

문제 - 15521\. position 배열에 해당 baskets의 위치가 저장되어있다.2\. m개의 볼을 basket에 넣어야된다.3\. basket에 넣으면 해당 볼의 거리만큼 자기장이 생긴다. 이 자기장을 최대로 만들 수 있는 결과를 출력어제와 같이 이진탐색문제이

문제 - 1052고객들이 customer의 배열에 담긴 내용 대로 매 분마다 서점에 들어온다.서점 주인이 심술궃어 주인이 있을 때 고객이 만족하지 못한다. 주인이 있을 때는 grumpy 배열에 저장되어 있다.minutes 동안에만 서점 주인이 성격이 온화해져서 고객들이

문제 - 택배 배달과 수거처음보고 그리디 알고리즘을 사용해야된다는 건 알았다. 그래서 처음 설계를 할 때에 가장 먼거리의 집부터 택배 배달을 시작하고 돌아오면서 최대용량만큼의 빈 상자를 수거한다. 가장 먼거리의 집에 가서 용량이 꽉차면 바로 수거하러 가지만 꽉차지않으면

문제 - 회의실 예약회의실예약은 정렬한 뒤에 시키는대로 구현을 하는 문제이다.근데 내가 작성한 코드는 깔끔하지는 않은 것같다. 이것보다 더 쉽게 작성하는 코드를 좀 참고해야되겠다.

문제 - 2559 문제 접근 누적합, 투포인터, 슬라이딩윈도우를 이용할 수 있다고 하는데 나는 슬라이딩 윈도우가 먼저 생각이 나서 고정적인 슬라이딩 윈도우를 이용했다. k =2가 일 때 처음에 0,1의 인덱스를 더한 값인 경우 최대값으로 설정을 해준다. 그런 다음 2

문제 - 나무 조경인접한 나무끼리 쌍을 묶어서 총 4개의 쌍을 찾아야되는 문제이다. 이때 총 4개의 쌍이 되지 않을 때에는 충족시키지 않아도된다.즉 n=2일때에는 4개의 쌍을 만들 수 없으므로 2개의 쌍만 찾는다.모든 경로를 탐색해야되므로 dfs를 사용한다. 이때에 상

문제 - 3020 문제 풀이 그림과 같을 때 N의 길이를 지날 때 그전에 배열의 값과 현재의 배열의 값을 더해주면 된다. 종유석은 반대로 자라기 때문에 전체의 크기에서 빼주어서 값을 구해준다. 소스코드 참고사이트

문제 - 1655처음에는 값을 넣을 때마다 정렬을 한다음 index를 이용하여 배열의 크기가 홀수개 일때에는 size/2의 값을 출력하고 짝수개일 경우에는 size/2 -1의 값을 출력을 했지만 시간초과가 떴다. 그래서 우선순위큐를 이용하고자 했다. 일단 단순구현으로

문제 - 7579배낭문제와 비슷한 문제로 dp로 해결을 하면 된다.하지만 배낭처럼 dpi를 할 경우 j를 무게로 잡는 즉 메모리를 잡으면 메모리초과가 난다. 100 \* 10_000_000으로 int로는 할 수가 없다.그래서 j를 총 비용으로 설정을 해야된다.dpi :

문제 - 2138매 순간에 최적의 선택을 해야되므로 그리디알고리즘을 사용할 수 있다. 그리디 알고리즘을 사용하면서 매 선택때마다 최적을 선택하지만 종합적으로 볼때에는 최적이라고 보장은 절대 할 수 없다.문제를 보면 i번째의 스위치를 누르면 i-1, i, i+1의 전구가

문제 - 9082처음에는 지뢰가 있는 곳은 주변의 숫자를 없애주는 최신화작업을 한 후 왼쪽,오른쪽 ,나머지 부분에서의

문제 - 15591처음에는 모든 경로의 USADO를 구한다음에 질문에 답을 할려고했지만 N이 최대 5000여서 5000\*5000\*5000개인 경우에는 시간초과가 나오기 때문에 시도하지 않았다.그래서 시키는 대로 BFS를 이용하여 첫 노드에서부터 연결된 노드로 이동시

문제 - 공유기 설치가장 인접한 두 공유기 사이의 거리를 구하기 위해서 이분탐색을 이용했다.1\. 해당 집의 좌표를 오름차순으로 정렬2\. 집의 좌표는 (0 ≤ xi ≤ 1,000,000,000)이므로 최솟값은 0, 최대값은 1,000,000,000으로 설정을 해준다.

문제 - 부분합처음에는 부분합이라는 이름때문에 부분합을 이용해서 풀려고했지만 아직 부분합알고리즘에 대해서 제대로 잘이용할 줄 몰라서 결국 투포인터를 활용해서 풀었다.while(left <= right && right < N)범위설정을 할때 위와 같이 설정을

문제 - 운동처음에는 dfs로 이용해서 사이클을 찾으려고 했지만 두 마을만 거쳐도 사이클을 어떻게 찾아야할지 조건을 찾지 못해서 다른 알고리즘을 생각하게 되었다.1\. 모든 정점에서 모든 정점까지의 최소 거리를 구한다. -> 플로이드와샬 알고리즘을 사용 다익스트라를 사

문제 - 1로 만들기2동적계획법이므로 점화식을 만든다. 1\. 0,1인 경우에는 연산 사용횟수가 0이므로 설정을 해준다. => dp0 = dp1 = 0;2\. 그리고 1을 뺀 경우와 2로 나눈 경우, 3으로 나눈 경우를 각각 따로 생각해서 점화식을 만든다. 각각 따로

문제 - AC처음에는 2,1,3,4,5의 배열을 정수만 추출하여 ArrayList로 넣었다. 그러면서 R인 경우에는 직접 Collections.reverse를 해주면서 뒤집고 D인 경우에는 첫번째 인덱스를 제거하는 식으로 코드를 짰다. 하지만 결과를 보니 16퍼정도에서

문제 - 다리만들기섬 구분 및 번호 매기기 (0 : 바다 1: 섬) 섬의 번호는 2부터 시작bfs를 이용하여 번호 매기기각 섬의 가장자리에서부터 시작해서 다른 섬까지의 최단 거리를 bfs로 구하기

문제 - 문자열 나누기해당 문제는 문자열을 다루는 구현문제로 x글자를 처음에 문자열의 0번째 인덱스로 설정을 해주고 x글자와 같은 횟수와 x가 아닌 다른 글자의 횟수가 같을 경우 문자열을 분리하고 x글자를 현재 문자로 셋팅해주면서 문자열끝까지 보면 된다.

문제 - 배달단일 시작점에서 다른 모든 정점으로의 최단 거리를 찾기 위해서 다익스트라 알고리즘을 사용했다.최소비용을 위해 우선순위큐를 이용해서 시간복잡도를 조금더 줄여보았다.참고 사이트

문제 - 에어컨에어컨을 통해 실내온도를 희망온도에 맞춰 올리거나 내릴 수 있다. 즉 냉방과 난방이 가능하다.flag를 이용하여 냉방으로 하는지 난방으로 하는지 판단그리고 t1,t2의 범위가 -10 ~40 이므로 이를 배열로 나타내기 어려우니 치환을 해주기 위해 +10을

문제 - 할인행사HashMap을 이용하여 10일간의 할인품목들의 갯수를 미리 저장내가 원하는 품목의 갯수와 할인품목들의 갯수가 일치하면 answer+1일치하지않으면 +0을 해준다.Map에 들어가지 않는 품목이 있을 수 있으므로 null체크

문제 - 1504특정 정점에서 다른 정점까지의 최단거리를 구하기 위해선 다익스트라를 사용특정한 두 정점을 지나가야되므로 특정한 두 정점을 기준으로도 다익스트라를 사용1 -> v1 -> v2 -> N, 1 -> v2 -> v1 -> N으로 가는 경로 중에서 최단경로를 구

문제 - 11053최장 증가 부분 수열의 알고리즘을 사용했다. dp를 이용해서 O(N^2)의 시간복잡도를 가지고 있다.1\. 규칙성을 위해서 A0 = 0 으로 설정하여 dp배열과 인덱스를 맞춰줬다.2\. 현재 값의 이전 값에서 가장 작은값 찾기3\. 가장 작은 값의 d

문제 - 수레 움직이기수레는 반드시 상하좌우로 이동해야된다.방문했던 칸으로는 다시 이동하지 못한다.자신의 도착 칸에 도착하면 수레는 고정되어서 다른 수레가 오지못한다.동시에 같은 칸으로 이동하지 못한다.수레는 자리를 바꾸며 이동하지 못한다.위의 5가지 조건을 지키면서

벽 부수고 이동하기4처음에는 부술 벽을 정한 뒤 그 벽을 부수는 방법으로 접근을 했다. 부술 벽이 많게 된다면 시간초과가 뜰거 같지만 일단 시도는 해봤다. 역시나 시간초과가 나왔다.그래서 두번째로 n\*m만큼 system.out.println을 찍어서 이것을 Strin

불!지훈이가 가장자리까지 이동해야되며 그또한 최소거리로 이동해야됩니다. 그래서 bfs를 사용하여 최소거리를 구했습니다.여기서 핵심은 불과 지훈이의 각각 queue를 이용해서 확산되거나 이동할 수 있는 경로를 저장해두었으며 불을 먼저 확산시켰습니다.불을 먼저 확산 시킨