📌 [BOJ] 백준 9012 괄호 📖 문제 📖 예제 📖 풀이 > 입력을 받을 시 input()과 sys.stdin.readline()의 차이를 인지하게 됐다. input()으로 입력을 받을 경우 두 종류의 괄호 '(' 와 ')' 만을 고려하면 되기에 eli
📌 [BOJ] 백준 10773 제로 📖 문제 📖 예제 📖 풀이
큐 자료 구조의 특성 FIFO(First In First Out) 특성을 고려하면 쉽게 풀리는 문제이다.
핵심은 시간의 합을 최소로 만들기 위해서 사람들이 줄을 서는 순서를 오름차순으로 만드는 것이다.
필요한 동전을 최소한으로 만들기 위해서는 최대한 큰 수의 동전으로 K를 계산해야하기 때문에 동전의 리스트를 내림차순으로 바꿔준다.
입력의 처음 수는 무조건 양수이기 때문에 '-' 를 통해 분할하여 첫 번째 리스트를 제외하고는 모두 더해주면 된다.두 번째 예제와 같이 배열에 '-' 가 없는 경우에는 첫 번째 리스트만이 생성 될 것이다.
본 문제의 점화식은 다음과 같다.
📌 [BOJ] 백준 1149 RGB거리 📖 문제 📖 예제 📖 풀이 > 위의 코드를 시각적으로 표현하면 다음 그림과 같다. 업로드중..
본 문제의 점화식은 아래의 그림과 같다.결과는 dp 행렬 마지막 행의 최대값을 출력하면 된다.
비교 대상인 배열 B를 오름차순으로 정렬한 후, bisect_left() 함수를 사용하여 A의 각 원소가 B에서 몇번째 인덱스로 들어가야하는지를 통해 자기보다 크기가 작은 값들의 수를 알 수 있다.
📌 [BOJ] 10816 숫자 카드 2 📖 문제
오름차순으로 정렬된 N_array가 M_array의 원소를 갖고 있지 않다면 0을, 갖고 있다면 1을 반환하는 bisect_is() 함수를 만들어서 해당 값들을 출력하게 만든다.
DFS/BFS 함수를 이용하여 1번 컴퓨터와 연결되어 있는 컴퓨터의 수를 탐색하여 값을 출력한다.
그래프 내에서 1의 값을 갖는 위치를 찾아 DFS/BFS을 통해 본인을 포함한 1의 값을 갖는 주변 그래프 위치의 갯수를 따로 저장한 후 마지막에 저장된 값의 수와 저장된 값의 오름차순을 출력한다.
입력된 그래프에서 DFS/BFS을 진행한 횟수를 출력한다.
입력에 대해 각각의 조건을 stack 자료구조를 활용하여 출력한다.
입력에 대한 각각의 조건을 큐 자료구조를 활용하여 출력한다.
📌 [BOJ] 백준 2839 설탕 배달 📖 문제 📖 예제 📖 풀이 > 입력값 N이 5의 배수라면 모두 5kg 봉지로 묶어버린다. 그렇지 않다면 3kg 봉지를 하나씩 사용하며 N의 변화된 값이 5의 배수가 되는지 지속적으로 확인한다. 0 또한 5로 나누면 나
A만 재배열이 가능하다는 문제의 조건이 주어졌다.전체 합을 가장 작게 만들기 위해서는 오른차순으로 정렬된 A의 값을 하나씩 가져와 B의 최대값과 곱해준 후 모두 더해주면된다.
본 문제의 점화식은 다음 그림과 같다.
본 문제의 예제에 대한 점화식은 다음 그림과 같다.
공유기 설치 간격을 mid로 설정하여 이진 탐색을 수행한다.공유기 설치 갯수와 입력값 C가 같을 때의 공유기 설치 간격 mid를 result로 출력한다.
배정 예산의 최대값을 mid로 설정한 후 이진 탐색을 수행한다.특정 예산으로 배정 예산의 최대값이 정해지고 그것을 통해 배정한 총 예산이 입력된 정해진 예산보다 작으면 그 때의 mid를 result로 출력한다.
📌 [BOJ] 백준 1260 DFS와 BFS 📖 문제 📖 예제 📖 풀이 > DFS/BFS 함수를 이용하여 각각의 순서를 출력한다. 처음 연결된 노드들을 입력할 때 각 노드의 연결된 노드들은 순서대로 추가되지 않는 것을 주의해야한다. 이를 위해 각 함수의 그
미로 탐색 문제는 BFS를 이용한다.
미로 탐색 문제는 BFS를 이용한다.
고려사항1\. 입력값보다 작은 수들과 그에 대한 갯수만큼의 '+'를 각각의 리스트(stk, answer)에 저장한다.2\. 저장한 수의 마지막 값이 입력값과 같아지면 stk에서 pop()을 이용하여 제거하고, 추가로 answer에 '-'를 저장한다.3\. skt에 마지
split()을 활용해 입력을 분해한 후 첫번째 원소인 a0가 무엇인지에 따라 각 조건의 결과를 출력한다.
업로드중..들 수 있는 총 무게 = (가장 약한 로프가 들 수 있는 무게 x 로프 수)결국 함께 물건을 드는 로프들은 약한 로프에게 맞춰줘야하기 때문에 위의 식이 나온다.따라서 입력을 내림차순으로 정렬한 후 cnt를 1씩 증가시키면서 입력으로 받는 수에 곱한 뒤 그 중
cnt를 1씩 증가시키면서 answer가 N을 넘거나 도달할 때까지 지속적으로 더해준다.마지막에 answer가 N을 넘어가게 되기 때문에 cnt에서 1을 빼준 값을 출력한다.
음수가 있더라도 음수 전에 더한 양수들의 합이 더 클 경우 음수를 포함해 연속적으로 더해주는 것이 연속 합을 최대화한다.따라서 순수 본인의 값과 본인 값에 추가로 전 과정들의 합을 더하는 것 중 어떤 것이 큰지 비교함으로써 위의 상황을 고려한다.
업로드중..수의 나열을 보고 점화식만 찾으면 간단한 문제이다.주의할 점은 dp 배열을 만들 때 0 x (n+1)으로 할 경우이다.dp1, dp2, dp3을 지정해야하기 때문에 위와 같이 배열을 만들 경우 n이 2일 경우 dp3에 대한 index가 없어 오류가 발생한다.
📌 [BOJ] 백준 12015 가장 긴 증가하는 부분 수열 2 📖 문제 📖 예제 📖 문제 > 4번째 푸는거라고 하는데 전혀 기억나지 않았다. . . dp 방식으로 풀면 간단하지만 시간복잡도의 제약이 있기 때문에 이진 탐색으로 분류되는 문제이다. bisect
본 문제는 이진 탐색의 전형적인 코드 모습을 보이지만, 각 행마다 (mid // i) 개수 만큼의 작은 수를 갖는다는 생각을 떠올리기는 어려운 문제이다.
자료 구조 queue를 이용한다.K 번째 전의 수들은 for 문에서 popleft()로 뽑아 append()로 다시 넣어준다.그리고 K 번째 수는 popleft()로 뽑아 출력할 리스트에 넣어준다.
우선 graph에서 값이 1인 위치를 모두 자료 구조 큐에 넣은 뒤 BFS를 통해 그것들의 주위 값인 0들을 한 번의 step을 기준으로 +1씩 올려준다.그럼에도 graph내에 0의 값이 존재한다면 -1을 출력하며 실행을 중지한다.만약 0이 없다면 graph에서 가장
DFS의 경우 재귀함수의 깊이 제한을 설정하는 sys.setrecursionlimit()을 사용하여 깊이를 늘려줘야 error가 발생하지 않는다.
총 주유 비용을 최소화하기 위해서 새로운 정점에 도달할 때 마다 기존 정점의 주유 비용과 비교하고 낮을 경우 가지고 있던 기존 주유 비용을 새로운 정점의 주유 비용으로 초기화시킨 후 다음 간선인 거리와의 곱을 총 주유 비용에 더하는 수행을 반복한다.
본 문제는 다음의 과정을 따른다.
📌 [BOJ] 백준 2467 용액 📖 문제
make_wall: backtracking 방식으로 값이 0인 위치에 벽을 세워 3개의 벽이 세워졌을 때 마다 BFS 함수를 호출한다.BSF: copy를 통해 기존 그래프를 복사해놓은 데이터를 사용한다. 큐 자료구조를 활용해 값이 2인 위치로부터 탐색 가능한 0의 값을
입력으로 받은 M을 활용하여 popleft()로 반환한 값이 해당 queue의 max 값이면서 우리가 찾고 있는 M 번째 수인지 확인하고 그 수에 대한 순위를 출력한다.
일의 자리 수가 1인지 확인하는 방법으로는 해당 값을 10으로 나눴을 때 나머지가 1인지를 보는 것이다. 나머지가 1일 경우 10으로 나눈 몫으로 값을 할당함으로써 1을 제거하는 효과를 보인다.
본 문제는 다음 그림의 점화식을 따른다.
나눠줄 과자의 최대 길이를 mid로 설정하여 이분 탐색을 수행한다.해당 길이에 대해 몇명의 조카들에게 나눠줄 수 있는지 확인하여만약 M보다 더 많은 조카들에게 나눠줄 수 있다면 과자의 최대 길이를 높이고,M보다 더 적은 조카들에게 나눠줄 수 있다면 과자의 최대 길이를
DFS/BFS 중 편한 방법을 통해 답을 출력할 수 있다.우선 일반인이 인지하는 색으로 DFS 함수를 통해 몇개의 구역이 있는지 센다.그리고 방문 기록을 0으로 초기화하고 입력 그래프의 'R'(or 'G')를 'G'(or'R')로 변환하여 통일해준 후 이전에 사용했던
힙 자료 구조의 특성을 활용하면 쉽게 풀리는 문제이다.
heapq 라이브러리는 기본적으로 최소 힙을 지원하기 때문에 최대 힙의 특성을 활용하기 위해서는 값을 넣을 때 해당 값의 마이너스 값으로 우선 순위 값을 추가로 넣어줘 최대 힙의 성질을 띄도록 구현한다.출력 시에는 우선 순위 값을 제거한 두번 째 값만을 출력한다.
30의 배수를 확인하기 위해 다음의 두 과정을 거친다.1\. 입력값에 0이 포함되어있는지 확인한다.2\. 입력값 각 자리수의 합이 3의 배수인지 확인한다.위 두 조건을 만족할 경우 입력값의 자리수들을 내림차순으로 정렬한 후 join을 통해 출력한다.만족하지 않을 경우
4번째 푸는 문제이지만 기억이 잘 나지 않았다. . .상담을 했을 때 보상을 언제 받는 것인지 헷갈려서 두 번째 for문 j에 대한 범위를 range(i+arrayi + 1)로 설정하여 오답이 나왔다.
아이들에게 나눠주는 보석의 수에 대해서 이분 탐색을 수행한다.아이들에게 꼭 같은 수의 보석을 나눠줘야하는 것은 아니기 때문에 특정 색의 보석을 나눠주는 최대 수 mid로 나눴을 때 나머지가 생기면 그것을 아이의 수 1명으로 쳐서 cnt를 늘려준다.
'R'에 대해서는 마지막에 한번 수행해주면 된다.만약 'R'이 짝수번 만큼 나와 두 번 뒤집어야 할 경우 배열은 본래의 모양을 가질 것이다.그렇기 때문에 'R'이 총 홀수번 나온 경우에만 마지막에 reverse 함수를 활용하면 된다.다만 'D'를 처리할 때 R이 나온
가장 긴 수열을 찾는 문제로 다이나믹 프로그래밍의 대표적인 문제 중 하나이다.
나무를 어느 높이에서 자를 것인지에 대해 이분 탐색을 수행하면 된다.나무의 길이가 mid로 설정한 자르는 높이보다 클 경우 길이 - mid를 모든 나무에 대해 더해준 후 그 값을 필요로 하는 길이 M과 비교한다.
기존 토마토 문제에서 높이를 추가로 고려하여 BFS를 수행하면 되는 문제이다.
일차원 배열에 대해서 BFS를 수행한 문제는 처음이다.
heapq 라이브러리를 이용해 힙 자료 구조를 만들고 heapq.heappush 할 경우 절대값으로 우선순위를 넣어주면 되는 문제이다.
📌 [BOJ] 백준 1931 회의실 배정 📖 문제 📖 예제 📖 풀이 > 회의실을 최대로 배정하기 위해서는 끝나는 시간의 오름 차순으로 회의들을 정렬해야한다. 그런 뒤 끝나자마자 바로 회의를 진행하는 경우가 있을 수 있기 때문에 끝나는 시간이 같은 회의들은
📌 [BOJ] 백준 1463 1로 만들기 📖 문제 📖 예제 📖 풀이 > N+1개 만큼의 dp테이블을 만든 후 2부터 for문을 시작한다. 기본적으로 전에 입력한 수에 1을 더하는 과정으로 dp테이블을 갱신한다. 만약 해당 수가 2 혹은 3으로 나누어지는 수
총 M번 투 포인터를 활용하면 되는 문제이다.그러기 위해 비교의 대상이 되는 N_array는 오름 차순으로 정렬할 필요가 있다.
최단 경로를 구하는 문제는 사실 heap 자료 구조를 활용한 다익스트라 알고리즘 공식이 있는 문제이다.
R 이 짝수번 나올 경우 배열은 본래의 순서를 지닌다는 것을 인지하고 다음 두 경우에 대해서 고려해주면 된다.1\. D가 나왔을 경우 지금까지 R이 홀수 번만큼 나왔다면 뒤집을 것을 고려하여 맨 뒤의 요소를 제거해야 한다. 짝수 번일 경우 본래의 순서를 지니기에 가장
heap 자료구조를 이용하면 되는 문제이다.두 개의 수를 뽑아 더해준 후 total에 더해주고 다시 heap에 넣는다.이를 heap 안에 수가 1개가 될 때 까지 반복해주고 마지막에 total을 출력한다.
다이나믹 프로그래밍의 대표적인 문제이다.
이분 탐색을 활용하면 쉽게 풀리는 문제이다.
그래프 내의 최대 값을 찾아내어 그 최대 값의 범위 만큼 DFS/BFS를 수행하여 가장 많은 수행 횟수를 출력한다.
📖 풀이
우선 서류 심사 성적에 대해 오름차순으로 직원을 정렬한 후, 면접 등수를 비교한다.자신보다 앞에 있는 직원보다 면접 등수가 높은 경우 cnt를 1씩 올려주며 cnt 값을 올릴 때 마다 비교 대상인 등수도 갱신해준다.
점수의 최대 값을 구하기 위해서는 목표 지점의 계단을 오르기 위한 다음 두 가지 방법을 고려하면 된다.예를 들어 연속된 계단 1, 2, 3, 4가 있다고 가정하며 타겟 지점은 4층이다.1\. 1층, 2층을 거쳐 4층으로 가는 방법이다. 즉, dpi = dpi-3 + s
이후 게임을 얼마나 할 것인지에 대해 이분탐색을 수행하면 된다.
문제에 정성이 정말 많이 담겨있다. . .딕셔너리 자료구조를 이용해 입력으로 받은 것을 두 가지 경우로 저장한다.출력에 대해서는 입력으로 받은 것이 숫자일 경우 문자를 출력하고, 문자일 경우 이에 해당하는 숫자를 출력하게 한다.
우선 세트와 낱개에서 가장 싼 제품으로 가져와서 다음 3가지 경우를 따져본다.1\. 낱개를 6개 산 가격와 세트 한개를 산 가격을 비교한다.전자의 경우가 더 쌀 경우에는 N개 모두 낱개 가격으로 구매한다.2\. 낱개 6개를 산 가격보타 세트가 산 경우 그리고 N을 6으
DP 문제로 분류되어있는데 많은 사람들이 수학으로 접근했다.
블루레이 하나에 녹화될 동영상의 길이에 대해 이분 탐색을 수행하면 된다.
DFS/BFS를 통해 각 리스트에 인접한 노드를 불러와 해당 노드의 자식 노드로 지정해준다.
스택 자료구조를 이용하면 구현되는 문제이다.
딕셔너리 자료 구조를 활용하여 각 알파벳은 십의 몇승의 자릿수가 주어지는지 확인하다.그런 뒤 가장 큰 자릿수가 주어지는 순서대로 알파벳을 정렬한 후 9부터 차례대로 합을 최대로 만드는 수를 배정 한다.
다음 점화식을 이용하여 해결한다.dpi = dpi-1 + 2\*dpi-2
입력 받은 용액을 정렬한 후 투 포인터 방식을 활용하여 답을 찾아간다.
📌 [BOJ] 백준 7562 나이트의 이동 📖 문제 📖 예제 📖 풀이 > BFS를 활용하여 최단경로를 구하는 문제이며, 기존 문제들과의 차이는 나이트의 이용경로대로 dx와 dy를 설정해주는 것이다.
다음 2가지를 고려해야한다.1\. '('들어온 경우 이를 stk에 추가한다.2\. ')'들어온 경우 다음 2가지를 고려한다.2-1. 직전에 '(' 들어온 경우 stk에서 마지막 '('을 제거한 후 stk 길이 만큼 ans에 더한다.2-2. 직전에 ')'들어온 경우 st
다음 3가지 상황을 고려해야한다.1\. 입력 값이 1인 경우 ans에 그냥 더해준다.2\. 입력 값이 양수인 경우 pos에 모아 sort 후 뒤에서부터 두개씩 뽑아서 곱한 값을 ans에 더해주는 수행을 pos에 1개 요소만 남을 때 까지 한 후 나머지 하나는 그냥 더해
다음 점화식을 이용해 문제를 해결할 수 있다.dpi = max(dpi-1, dpi-2 + arri, dpi-3 + arri-1 + arri)계단 오르기 문제와 다른 점은 마지막 잔을 고르지 않아도 된다는 점이기 때문에 이전의 누적 값을 그대로 가져와도 되는 부분인 dp
모든 입력값에 대해 해당 입력값을 제외한 tmp 리스트를 만들어서 투 포인터 방식으로 합한 값을 입력값과 비교하는 방식으로 수행한다.
BFS를 이용하여 문제를 해결할 수 있다.다른 문제들과 다른 점은 각 노드에 대해 BFS를 모두 적용해가며 연결된 노드들을 탐색한다는 것이다.
지난번 풀었던 요세푸스 문제와 동일하다.자료 구조 queue를 활용하여 풀 수 있다.
기존에 풀었던 한 강의실에서 가능한 최대 강의 수 문제와 같은 문제라고 생각했는데 조금 다르다.본 문제는 우선 순위 queue를 활용하여 전체 강의를 진행하기 위해 몇 개의 강의실이 필요한지를 계산해야한다.
업로드중..사람들의 풀이를 통해 겨우 문제를 이해한 문제이다.점화식을 외움으로써 풀 수 있어진 것 같다.어렵당. . .
이분 탐색 문제 유형에 해당하지만, 집합 자료 구조를 활용하여 해결할 수 있다.
지나온 길의 알파벳을 저장할 집합을 따로 만들어 DFS를 수행하고 cnt를 올려가며 조건을 만족하는 최대값을 ans에 갱신한다.필수적으로 pypy3 파일로 제출해야하며, 채점 시 이유 모를 시간 초과가 지속적으로 발생한다. . .
업로드중..전에 풀었던 문제들과 동일한 형식의 문제로 자료 구조 큐를 활용하면 된다.
그리디 알고리즘의 대표적인 문제이다.
dp에 15746의 나머지를 저장하는 방식으로 수행하지 않으면 메모리 부족 오류로 정답 처리가 되지 않는다.
📌 [BOJ] 백준 3020 개똥벌레 📖 문제 📖 예제 📖 풀이
본 문제는 최소 스패닝 트리를 찾는 문제로 prim/kruskal 알고리즘으로 해결할 수 있다.본 풀이는 kruskal 알고리즘의 코드를 활용한다.
자료구조 스택을 두개 만들어서 'L'과 'D'를 구현하고 마지막에 뒤집은 stk2를 stk1에 이어 붙이고 연속되게 출력한다.
처음 테이프를 붙인 위치로부터 길이 L 이내로 떨어진 위치들의 경우는 카운트 하지 않고, 이외의 위치일 경우 카운트를 한 뒤 테이프의 새로운 위치를 해당 위치로 초기화한다.
dp에 누적합을 미리 구해놓는다.후에 x1, y1, x2, y2 값을 입력으로 받아 다음 점화식을 통해 답을 구한다.ans = dpx2 - dpx2 - dpx1-1 dpx1-1
인출할 때 돈의 액수에 대해 이분 탐색을 수행하면 된다.처음에 인출한 상태에서 시작하기 때문에 처음 cnt는 1로 설정한다.
DFS를 이용하여 문제를 해결한다.DFS 수행 중 목표 지점에 대해 DFS가 수행되었을 경우 cnt 값을 저장해놓고 결과로 출력한다.
BFS/DFS 두 방법을 통해 다음 문제를 해결할 수 있다.
기존 문자열에 += 연산을 활용하여 문자열을 추가한다.
capitalize() 함수를 활용하여 문제를 해결할 수 있다.capitalize() 함수는 가장 앞에 오는 알파벳을 대문자로 바꾸고 뒤에 있는 알파벳들을 소문자로 바꾼다.만약 숫자가 가장 먼저 올 경우 뒤에 있는 알파벳들만 소문자로 바꾼다.
A, B 모두 오름차순으로 정렬한 후 A에서는 가장 작은 수를 B에서는 가장 큰 수를 가져와 곱하고 answer에 더해주는 연산을 반복한다.
자료구조 스택을 이용하여 문제를 해결할 수 있다.
특정 수를 이진수로 바꿔주는 bin() 함수를 활용해 문제를 해결할 수 있다.
이중 for문을 이용해 문제를 해결한다.
특정 수를 이진수로 바꿔주는 함수 bin()을 활용하여 문제를 해결할 수 있다.
다음 점화식을 유도하는 동적 계획법 방식으로 문제를 해결할 수 있다.dpi = dpi-2 + dpi-1
자료 구조 스택을 활용하여 문제를 해결할 수 있다.
다음의 갈색 타일 개수와 노랑색 타일 개수의 관계식을 활용하여 해결할 수 있다.갈색 타일의 개수 = (노란 타일이 가로로 배열된 개수 + 2) × 2 + (노란 타일이 세로로 배열된 개수 + 2) × 2 - 4
📌 [Programmers] 영어 끝말잇기 📖 문제
입력 값 n이 0이 될 때 까지 다음 while문을 돌린다.n이 2로 나눠질 경우 2로 나눠주고, 그렇지 않을 경우 1을 뺀 후 ans을 1 올린다.
구명보트의 개수를 최소화하기 위해서는 가장 무거운 사람과 가장 가벼운 사람을 함께 태워야 한다.poeple을 오름차순으로 정렬한 후 가장 무거운 사람과 가장 가벼운 사람의 무게를 더해 limit보다 작거나 같을 경우 둘 모두를 태워 보낸다.만약 두 사람 무게의 합이 l
두 수의 최대공배수를 구하는 함수 gcd()를 활용하여 다음 문제를 해결할 수 있다.
a와 b가 승리를 통해 대진에서 올라가는 것을 (x+1) // 2로 표현할 수 있음을 배울 수 있었던 문제였다.
다음 점화식의 동적 계획법 알고리즘을 활용하여 문제를 해결할 수 있다.dpi = dpi-2 + dpi-1
각 귤의 사이즈의 개수를 딕셔너리 자료구조를 이용해 할당한다.후에 각 사이즈의 개수를 기준으로 내림 차순으로 정렬한 뒤 k가 0이 될 때까지 각 사이즈의 개수만큼을 불러와 빼준다.각 사이즈를 불러올 때 마다 answer를 1씩 증가시켜주고 k가 0이 되면 answer를
원소 하나씩을 더하는 갯수를 늘려가는 방식으로 문제를 해결할 수 있음을 배웠다.
입력 받은 s를 리스트로 만들어 s의 크기만큼 가장 왼쪽의 요소를 오른쪽으로 붙여가며 완전한 괄호의 집합인지 확인한다.
딕셔너리를 활용해 필요한 물품과 그에 대한 개수를 저장한다.이후 Counter 함수를 활용해 저장한 딕셔너리와 비교하며 일치할 경우 answer를 1씩 증가시키고 마지막에 출력한다.
다음 식을 통해 특정 행렬의 요소 값을 알 수 있다.max(i // n, i % n) + 1
수정이 필요한 문제이다.
📌 [Programmers] 행렬의 곱셈 📖 문제 📖 예제 📖 풀이 > 행렬의 곱셈 식을 이용하여 문제를 해결할 수 있다. answeri += arr1i * arr2j
딕셔너리 자료구조를 활용하여 문제를 해결한다.새로운 옷의 종류일 경우 (입지 않은 경우, 입은 경우) 두 가지를 고려하여 해당 key에 2를 더해주고, 딕셔너리에 이미 저장되어 있을 경우 해당 key에 1을 더해준다.마지막으로 모두 안입은 경우를 제외하고 출력한다.
캐시 사이즈가 0일 경우 캐시의 기능을 활용하지 못하기에 cities의 수 만큼 5를 곱해 출력한다.캐시 사이즈가 자연수일 경우 각 cities가 캐시에 존재하는지의 여부에 따라 5 혹은 1을 더한다.추가로 캐시 사이즈와 현재 캐시내의 데이터 수를 비교하여 가장 처음
입력받은 s의 가장 앞의 '{{' 부분과 '}}' 부분을 제거한 후 '},{'을 기준으로 분할한 뒤 길이를 기준으로 오름차순 정렬을 수행한다.그 후 분할한 것을 하나씩 가져와 ','을 기준으로 분할한 뒤 answer에 없는 값일 경우 추가하고 있는 값일 경우 건너뛴다.
📌 [Programmers] 피로도 📖 문제 📖 예제 📖 풀이
입력 배열인 priorities의 최대값과 가장 앞에 있는 값을 비교하여 같을 경우 answer을 1 올리고, 같지 않을 경우 가장 앞의 값을 맨 뒤로 보낸다.그 과정에서 가장 맨 앞 값을 뺄 때마다 location을 1씩 빼주어 타겟값이 이동해주는 것을 표현해준다.가
📌 [Programmers] [1차] 뉴스 클러스터링 📖 문제 📖 예제 📖 풀이 > str1과 str2를 두 글자씩 끊어서 알파벳에 해당할 경우 A와 B에 각각 저장한다. A와 B의 합집합을 구하고, A와 B의 교집합을 구한 뒤 자카드 유사도를 구한다.
📌 [Programmers] 전화번호 목록 📖 문제 📖 예제 📖 풀이 > 문제가 조금 잘못되지 않았나 생각을 한다. 특정 번호가 다른 번호의 접두사가 되는지를 확인하는 문제라고 생각했는데, 해당 문제의 답은 특정 번호의 일부가 다른 번호의 접두사로 포함되는
📌 [Programmers] 타겟 넘버 📖 문제 📖 예제 📖 풀이 > 입력 배열 numbers에서 값을 하나씩 불러와 기존에 저장되어 있는 배열 leaves의 값들에 +와 -연산을 수행한 뒤 leaves를 새롭게 초기화해준다.
해당 문제를 통해 k진수로 변환하는 방법과 소수를 확인하는 가장 효율적인 방법인 '에라토스테네스의 체'를 배울 수 있었다.1\. 특정 수를 k진수로 변환하기 위해서 특정 수에서 k를 나눈 나머지를 기존 수의 앞으로 붙여주는 수행을 특정 수가 0이 될 때까지 반복해준다.
동적계획법을 활용하여 문제를 해결할 수 있다.
heap 자료구조는 최소힙을 기본으로 구성되어있기 때문에 큰 수를 빼는 것을 고려하여 -1을 곱한 값을 우선순위로 저장할 max_heap도 heap과 함께 준비한다.
DFS를 활용해 다음 문제를 해결할 수 있다.
알파벳을 딕셔너리에 저장하는 방법을 배울 수 있었다.
convert() 함수를 이용해 모든 수를 n진수로 변형한 뒤 튜브가 말해야하는 수만 따로 모아서 출력한다.
📌 [Programmers] 야근 지수 📖 문제 📖 예제 📖 풀이 > heapq.heapify() 활용하여 문제를 해결할 수 있다.
product() 함수를 활용하여 문제를 해결할 수 있다.
BFS를 활용하여 최단거리 문제를 해결할 수 있다.
자료 구조 스택을 활용하여 문제를 해결할 수 있다.
자료 구조 heap을 활용하여 문제를 해결할 수 있다.
target 단어가 words에 없을 경우 0을 리턴한다.target 단어가 words에 있을 경우 BFS를 활용하여 문제를 해결할 수 있다.begin이 target까지 도달하는 최단거리를 구하는 문제이다.
answer을 prices 값의 수 만큼 0으로 초기화시킨 후 특정 인덱스의 값보다 연속적으로 큰 수만큼 cnt를 올려 answer의 인덱스에 초기화 한다.자신의 값보다 큰 수를 발견하더라도 cnt를 1 증가시키고 중단해야한다.
자료구조 딕셔너리와 집합을 활용하여 문제를 해결할 수 있다.
동적 계획법 알고리즘을 활용하여 문제를 해결할 수 있다.
📌 [Programmers] 기능개발 📖 문제 📖 예제 📖 풀이 > progresses의 첫 번째 항이 100을 넘을 때 까지 time을 1씩 증가시킨다. progresses의 첫 번째 항이 100을 넘을 경우 그 항을 제거해주고 cnt를 1 증가시킨다.
Counter() 함수를 활용하여 문제를 해결할 수 있다.
문자열을 활용하여 문제를 해결할 수 있다.
n이 s보다 클 경우 각 요소의 값은 0을 가질 수 밖에 업게 되므로 -1을 출력한다.이외의 경우 s // n 값을 각 요소에 초기화해주고 나머지 값은 요소에 1씩 증가시켜주는 방식으로 할당한다.