출발점부터 도착점까지 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제였는데 최소에 꽂혀서 바로 BFS로 접근했던 문제였다. 아직 BFS가 익숙하지 않아서 코드를 작성하는데 시간이 좀 걸렸다.출발점에서부터 이동할 때 만약 이동 가능한 칸이라면 1만큼 더해 해당 칸으로
회의가 끝나는 시간을 1순위로 오름차순 정렬하되, 이 때 동일한 시간에 회의가 끝나는 경우 최대로 사용할 수 있는 회의의 최대 개수를 구하기 위해서는 2순위로 회의가 시작하는 시간을 2순위로 오름차순 정렬해야한다.💡소요시간 : 12m
삼각형의 빗변 상에 위치한 값은 한 칸 위에 있는 값을 그대로 더해주면 된다. 하지만 안쪽에 있는 값은 왼쪽 대각선 위의 숫자와 오른쪽 대각선 위의 숫자와 비교해 값을 넣으면 된다.i = 1층dp\[1]\[0] = dp\[1]\[0] + dp\[0]\[\[0]dp\[1
가장 최선의 방법을 찾아가는 BFS 탐색 문제였다.N = K인 경우가 반례였는데 이 부분은 0을 출력하도록 설정함으로써 해결할 수 있었다.💡소요시간 : 17m
💡문제접근 💡코드 💡소요시간 : 40m
💡문제접근 > * heapq를 사용해서 해결할 수 있었다. 이전 포스팅에 있었던 [[백준] 11279번 최대 힙]과 [[백준] 1927번 최소 힙]에서 다루었던 문제라 수월했다. 약간의 센스가 있으면 더 좋은 문제다. > * 절댓값만을 저장하는 것이 아니라 입력값과
에라토스테네스의 체를 이용하여 쉽게 해결가능한 문제매 테스트케이스마다 에라토스테네스의 체를 돌리는 것은 시간 낭비였다. 또 문제에서 n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력하라고 조건을 주었는데 이를 구하기 위해 나는 투 포인터 개념을 이
두 수 A, B의 최대공약수를 구해서 문자 1에 최대공약수만큼 곱해주면 된다.💡소요시간 : 4m
팰린드롬인지 아닌지를 판별하는 함수와 소수인지 아닌지를 판별하는 함수 두 개를 작성해서 두 개 다 True를 반환하는 N보다 크거나 같은 가장 작은 수를 출력한다.💡소요시간 : 5m
BFS알고리즘을 이용했다. 만약 탐색하고자하는 위치의 값이 1이라면 BFS를 실행한다. 상하좌우 탐색을 통해서 조건을 만족시키면 계속 탐색을 수행해나가면서 단지에 속하는 집의 수를 1씩 더해준다. 만약 큐가 비어있다면 탐색을 중지하고 단지에 속하는 집의 수를 retur
단편적으로 규칙성을 찾아보았지만 눈에 띄는 규칙성이 없었다. 가능한 경우들을 하나하나 나열하면서 정리를 해봤는데 아래의 표와 같은 변화를 확인할 수 있었다. 표를 기반으로 코드를 작성할 수 있었다. DP문제는 규칙성을 빠르고 정확하게 찾아내는 것이 문제의 핵심인 것 같
이전 포스팅에 있었던 \[백준 10844번 쉬운 계단 수] 문제와 유사한 형태의 DP문제였다.이 문제를 해결할 때 역시 마지막 자릿수가 0~9인 경우의 빈도를 dp배열에 저장해서 해결하였다.누적 합 방식으로 값이 저장되는 규칙성을 확인할 수 있다.💡소요시간 : 5m
이전 포스팅에 있었던 \[백준 1463번 1로 만들기]의 응용 문제다. 이 문제에서는 추가로 연산을 사용하는 과정까지 같이 출력해줘야한다. 그래서 연산을 사용하는 횟수의 최솟값, 연산 과정 값을 저장했다. 💡소요시간 : 40m
맞왜틀을 많이 떠올렸던 문제였다. 그런데 문제를 자세히 보니 입력값으로 나온 데이터는 각각의 지원자의 서류심사 성적, 면접 성적의 순위다. 낮을수록 좋다는 것을 뒤늦게 깨달은 것이다. 서류심사 성적을 기준으로 오름차순 정렬한 다음 면접 성적을 기준으로 다른 모든 지원자
다이나믹 프로그래밍 알고리즘 = 규칙성💡소요시간 : 5m
combinations를 이용하고 중복을 제거하기 위해 set을 사용했다.💡소요시간 : 8m
트리에 대한 개념을 유튜브로 보고 이해한 다음 문제를 풀었다.Python으로 트리를 구현하는 방법 : 딕셔너리를 사용위의 코드에서 A는 부모 노드를 의미하고 B는 왼쪽 자식 노드, C는 오른쪽 자식 노드를 의미한다.B를 인덱싱하는 방법 : tree\["A"]\[0] /
최단 거리라는 단어를 보자마자 문제를 BFS 탐색 알고리즘을 이용해서 풀어야겠다고 생각은 했다. 하지만 코드로 옮기는 과정에서 계속 난관을 겪었다.💡소요시간 : 48m
1 ~ 10까지 숫자를 나열할 수 있는 경우의 수를 모두 구해 규칙성을 찾아 코드를 세웠다. 눈에 확 띄는 규칙성이 아니라서 그런지 시간이 좀 오래 걸렸던 문제였다.💡소요시간 : 20m
G층에 도착하기 위해 눌러야 하는 최소 버튼의 수를 구하는 문제다. 최소라는 단어에 바로 반응해서 BFS 탐색 알고리즘으로 접근했다.💡소요시간 : 20m
테스트케이스에서 주어진 수보다 작은 가장 큰 피보나치 수를 단계적으로 빼주면서 0이 될 때까지 계산을 수행한다.문제에서 주어지는 각 테스트 데이터의 최댓값은 1,000,000,000으로 1,000,000,000보다 작으면서 피보나치 수열 중애서 나올 수 있는 최댓값은
단순히 정렬을 하는 문제가 아니었다. 가장 높은 통나무를 중앙에 배치하고 그 다음부터 양 옆으로 통나무를 배치하는 방식으로 수행해간다. 인접한 통나무 간의 높이를 비교해서 난이도를 찾고 가장 마지막으로 맨 앞에 있는 통나무와 맨 뒤에 있는 통나무 간의 높이를 비교해서
DP로 푸는 것보다는 BFS가 낫겠다고 생각해서 계속 도전했는데 WA를 받았다. 확인해보니 어이없게도 방문한 적이 있거나 만약 인덱싱이 N값 이상이 나오면 continue를 실행시켰어야했는데break를 걸어버려 계속 틀렸던 것이다.💡소요시간 : 2h
BFS 탐색 알고리즘을 이용해서 문제를 해결할 수 있었다. 자주 접했던 유형의 문제라 조금은 익숙한 것 같다.💡소요시간 : 28m
BFS 탐색 알고리즘을 이용해서 문제를 해결할 수 있었다.처음 제출한 코드는 2차원 배열에서 최솟값부터 최댓값까지 range로 범위를 지정해서 탐색한 코드였는데 해당 코드가 WA를 받아서 문제를 자세히 읽어봤는데 문제 하단부에 노트라는 부분에 힌트가 있었다.아무 지역도
3 × 3 행렬을 함수 reverse를 작성, for문을 이용해 전 범위를 탐색한 다음 일치하지 않으면 1을 0으로, 0을 1로 바꾸는 연산을 수행한 다음 마지막에 함수 check를 작성, 행렬 A와 행렬 B가 일치한다면 필요한 연산의 횟수의 최솟값을 출력하고 일치하지
지그재그로 스티커를 택하는 것이 무조건 최대가 되진 않는다. 이 부분을 명심하자.입력1 1 1출력1n = 1인 경우 IndexError가 출력되어 통과되지 못한 것이었다. 위의 경우를 해결하기 위해서 for문 안에 1인 경우의 케이스의 결과를 정해주어 코드가 동작될 수
BFS 탐색 알고리즘을 이용해서 해결할 수 있었다. 상하좌우 탐색하여 만약 1이 이어져 있으면 면적을 1만큼 증가시키고 만약 탐색하는 과정에서 1이 나오면 그림이 존재하게 되므로 그림의 개수를 1만큼 증가시켜준다.💡소요시간 : 10m
해당 문제는 직접 좌표의 값을 찾아 계산을 하게 된다면 시간초과(TLE)가 100% 발생하게 된다. 이 문제는 누적 합 개념을 이용해야하는데 2차원 누적 합에 대한 공부가 되어있지않아 접근이 어려웠다. 2차원 배열의 구간 합에 대해서 잘 정리해놓은 포스팅을 참고해서 공
BFS 탐색 알고리즘을 통해 해결할 수 있었다. 양방향 그래프를 그린 다음 거쳐야 하는 단계를 저장한 다음 단계의 총합을 반환하는 방식으로 케빈 베이컨의 수를 구했다.💡소요시간 : 10m
다리의 길이만큼 배열을 만든 다음 만약 다리 위에 있는 트럭의 무게의 합이 다리의 최대 하중보다 많이 나간다면 0을 추가해주고 그렇지 않다면 첫 번째 트럭을 가져온다.실버1 문제치곤 난이도가 좀 있어서 시행착오를 많이 겪었다.💡소요시간 : 18m
물병의 개수를 2진법으로 나타냈을때, 만약 1의 개수가 K보다 작다면 while문을 멈추고 상점에서 사야 하는 물병의 개수의 최솟값을 출력해주면 된다.💡소요시간 : 10m
구하고자 하는 연도를 1로 초기화한 다음 1씩 증가하여 조건을 만족시키는 값이 된다면 연도를 출력하고 아니라면 -1을 출력하는 방식으로 코드를 작성했지만 시간초과(TLE)가 발생했다. 그도 그럴것이 N, M의 최댓값은 40,000까지로 매우 큰 값으로 1씩 증가시키면서
유클리드 호제법을 이용해서 최대공약수를 구한 다음 조건에 맞게 경우를 나누어 코드를 작성했다.💡소요시간 : 4m
인덱스로의 접근을 시도했으나 문자열 S의 길이가 최대 1,000,000까지이고 결국 시간초과(TLE)가 발생하게 된다. 문자열 탐색 알고리즘으로 KMP 알고리즘이 있다고 해서 추가로 공부했다. 구글링을 통해서 시간초과를 해결할 수 있는 방법을 찾아서 풀고 이해했던 문제
N의 값의 범위는 0 ≤ N ≤ 1,000,000,000,000,000,000이다. dp배열의 값을 최대 20!까지 저장할 수 있도록 설정한다. 그 다음 N의 값이 팩토리얼의 값보다 크거나 같으면 N에서 빼주면서 N이 0이 되는지 안되는지 판별한다.💡소요시간 : 5m
문제를 힘겹게 풀었는데 다른 사람들의 방법을 보니 다들 간단하게 금방 푼 것 같아서 풀고도 많이 아쉬웠던 문제였다. 점화식을 세우면서 코드를 작성했는데 아래와 같이 나왔다.$dpi = dpa = max(dpa, card~priceb + dpa-b)$여기서 dpi는 i개
백트래킹의 개념을 몰랐고 재귀에 대해서 익숙하지 않아서 구글링하면서 공부했다.백트래킹과 재귀의 개념을 이해한 다음 다시 풀어봐야겠다.💡소요시간 : 1h
연산 기호의 개수에 맞춰서 최댓값과 최솟값을 구하는 백트래킹 문제였다. 앞서 풀었던 N과 M 시리즈 문제를 다시 풀어보면서 이해하니까 문제가 쉽게 풀렸다.💡소요시간 : 10m
4와 7의 중복순열로 나올 수 있는 경우를 itertools.product를 이용해 찾은 다음 A이상 B이하를 만족하는지 탐색하는 조건문을 실행시킨다.💡소요시간 : 12m
from itertools import permutations를 이용해서 푸는 방법과 백트래킹을 이용한 방법 두 가지로 접근할 수 있을 것 같아 두 가지 방법으로 풀어보았다.💡소요시간 : 10m
누적 합 알고리즘으로 나와 있어서 1차원 배열을 이용한 누적 합을 이용했는데 계속 50점이 나와서 어디가 문제인가했는데 문자열의 길이가 엄청나게 큰 값인 경우 for문으로 탐색하기에는 무리가 있어 시간초과가 발생한 것 같다.결국 전에 풀었던 ascii_lowercase
N개의 카드를 구매하기 위해 지불해야 하는 금액의 최솟값을 구하는 문제다. min을 이용하면 된다.💡소요시간 : 37m
BFS 탐색을 이용해서 문제를 해결했다. 해당 영역에 속하는 부분을 1로 카운팅하고 0으로 카운팅된 값의 개수를 세어주면 되는 비교적 간단한 그래프 문제였다.💡소요시간 : 12m
목표지점 2가 나오는 행렬의 좌표에서 BFS 탐색을 진행하여 만약 0이 나오면 0 그대로 출력을 하고 만약 주변이 다 0으로 둘러싸여 있어서 진출할 수 없어 다른 좌표에 도달하지 못하면 -1을 출력해야한다. 방문여부를 탐색하는 배열과 지도를 나타내는 배열, 그리고 각
나이트가 이동할 수 있는 경우를 계산하여 시작점에서 도착점까지 도달하는데 필요한 거리를 계산하는 문제다. 체스판에서 나이트는 위와 같은 형태의 움직임으로만 이동할 수 있다. 따라서 방향을 나타내는 배열에 8개의 순서쌍을 넣어서 방향을 잡고 체스판의 범위 내에서만 이동가
\`def BFS(a, b): sheep = 0 wolf = 0 queue = deque() queue.append((a, b)) while queue: y, x = queue.popleft() dx = -1, 0,
문제 조건을 잘 정리해보자.같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 많은 경우 늑대의 개체 수는 0, 양의 개체 수는 전부 살아남는다. 그 외의 경우 늑대의 개체 수는 전부 살아남고 양의 개체 수는 0이 된다.💡소요시간 : 17m
각 단어의 사이에 \_을 넣어서 새로운 단어를 만드는데 이 때 만들어진 새로운 단어가 사전 순으로 가장 앞서는 단어를 구하는 문제다. 출력 항목에 보면 사전 순 정렬에 대한 조건이 주어져있는데 조건은 다음과 같다.알파벳 대문자, 소문자, 밑 줄의 순서는 'A' <
이 문제는 다른 문제와 다른 단방향 그래프 문제였다. 문제에서 A가 B를 신뢰하는 관계라고 가정할 때, B를 해킹하면 A를 해킹할 수 있다고 했기 때문에 B에 A를 추가하는 방식으로 코드를 작성해야한다는 것을 알고 코드를 작성했다.💡소요시간 : BFS(31m) + D
오른쪽 위(1사분면), 왼쪽 위(2사분면), 오른쪽 아래(4사분면), 왼쪽 아래(3사분면)💡소요시간 : 38m
재귀 알고리즘으로 해결할 수 있는 대표적인 문제인 하노이의 탑 문제다.쌓아 놓은 원반을 최소 횟수로 옮기는 알고리즘하노이의 탑은 작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키면서 기둥 3개를 이용해서 원반을 옮기는 문제크기가 모두 다른 원반이 첫 번째 기둥
거듭제곱이란?똑같은 수나 문자를 여러 번 곱하는 것을 거듭제곱이라고 한다.거듭제곱을 구하는 방법은 여러 가지가 있다. 각각의 방법을 모두 이해하고 어떤 코드가 가장 효율적인 코드인지를 이해하는 시간을 가지려고 한다.반복문 사용예를 들어, a의 n제곱 값을 구하고 싶을
플로이드 워셜 알고리즘 문제💡소요시간 : 21m
heap을 이용해서 풀 수 있는 문제다.n장의 카드에 쓰여있는 수를 모두 더한 값이 가장 작게 만드는 것이 최종 목표라고 제시되어있다. 그러려면 n장의 카드 중에서 가장 작은 수 2개를 골라 더한 후 heap에 2번을 넣어서 카드 합체를 진행하면 된다.💡소요시간 :
BFS 완전탐색 유형의 문제chess\[r2]\[c2]의 값이 0인 경우 이동할 수 없는 경우이므로 -1을 출력💡소요시간 : 21m
오른쪽과 아래쪽으로만 이동이 가능하고 중간에 방향을 바꿀 수 없다고 했으므로 지도 내에서 오른쪽으로 이동이 가능한 경우, 아래쪽으로 이동이 가능한 경우를 따져서 오른쪽 맨 아래로 이동할 수 있는 경우를 카운팅한다.IndexError에 시달렸던 문제💡소요시간 : 34m
💡문제접근 > * 재귀 알고리즘으로 어떻게 탐색을 해야할지 정말 고민을 많이 했고 쉽사리 해결방법이 떠오르지 않아서 오랜 시간 고민한 문제였다. > * 재귀 함수 코드 : 재귀 함수의 종료 조건 명시 + 자기 자신을 호출하면서 어떤 탐색을 수행할 것인지 💡코드(메
BFS 탐색을 진행하면서 "W" 무리와 "B" 무리를 찾고 리턴한 값에 제곱을 취해 병사들의 위력의 합을 구한다.💡소요시간 : 24m
\[백준 1914번 하노이 탑]문제와 동일한 문제💡소요시간 : 5m
백트래킹을 통해 K개를 구해 나올 수 있는 모든 수들을 더한 최댓값을 구하는 문제였는데 처음에는 문제를 잘못 이해해서 선택한 두 칸이 인접하면 안된다는 것을 한 칸을 고르고 대각선으로만 가야한다고 착각해서 많은 시간을 소모했다.하나의 칸을 골랐을 때 그 칸을 기준으로
배열의 회전을 구현하는 문제로 전의 값을 저장하지 않으면 모서리의 값이 사라지는 문제가 발생해서 이를 염두에 두면서 코드를 짰는데 문제는 간단하지만 푸는데 시간이 많이 걸렸다.💡소요시간 : 56m
딕셔너리를 이용해서 해결할 수 있었다.Key는 후보자의 번호, Value는 리스트 형식으로 추천 수, 들어온 순서로 넣고 사진틀에 게시할 수 있는 경우와 게시할 수 없는 경우에 대한 처리를 잘해주면 된다.💡소요시간 : 27m
가장 위의 중간 정점에서 가장 아래의 중간 정점으로 이동하는 최단 경로를 구하는 문제로 그래프의 방향성을 잘 생각해 코드로 구현하면 해결할 수 있는 비교적 간단한 문제였는데 머릿속으로 경우를 따지는 과정에서 하나를 놓쳐 생각보다 오래 걸렸던 문제였다.💡소요시간 : 3
0~9까지의 방문 배열 만들기(중복 제외) + 부등호를 판별할 수 있는 함수를 만들기💡소요시간 : 41m
💡문제접근 > * 백트래킹을 통해서 접근했다. 재귀함수를 작성하여 접근하는데 합이 n이면서 뽑은 수의 개수가 k개인 모든 경우를 따지지 않고 순서 변수인 cnt를 전역변수로 설정하고 합이 n이면서 순서 변수가 주어진 k와 일치하는지를 확인해서 답을 출력한다. 아니라면
이분탐색을 사용했는데 한 가지를 간과해서 많은 시간이 걸렸던 문제였다.바로 start와 end의 값을 지정하는 부분에서 문제가 발생했던 것이다. 처음에는 start의 값을 리스트의 최소값, end의 값을 배열 전체의 합으로 넣었는데 이렇게 되면 문제가 발생하는데 다음