👆 첫 번째 시도 (시간초과) k값보다 큰 동전값은 삭제하고 동전값을 내림차순으로 정렬, while문을 돌면서 동전값 하나씩 빼 줌 ✌ 두 번째 시도 (성공) k값보다 큰 동전값은 삭제하고 동전값을 내림차순으로 정렬, k를 동전값으로 나눈 몫을 cnt에 더해서 카운팅
👆 첫 번째 시도 (선형탐색) 이진탐색 파트인 건 알지만 왜 이진탐색을 써야 하는지 몰랐음 ㅎ 절단기의 높이를 가장 긴 떡의 길이로 설정하고 1씩 줄여나가면서 잘린 떡의 길이(rest)의 합을 계산 ✌ 두 번째 시도 (이진탐색)
👆 첫 번째 시도 bisect 라이브러리를 사용하면 쉽게 정답을 얻을 수 있다. 📌 bisect 라이브러리 bisect_left(a, x): 배열 a에 원소 x가 들어갈 수 있는 가장 왼쪽 인덱스 반환, bisect_right(a, x): 가장 오른쪽 인덱스 반환
👆 첫 번째 시도 (시간초과) 이중 for문으로 각 원소 i마다 앞 원소들과의 부분합을 구하여 그 중 가장 큰 값을 di에 저장, di 중 가장 큰 값을 출력 ✌ 두 번째 시도 (성공) 각 원소 i마다 그 앞의 부분합을 구할 필요는 없음
👆 첫 번째 시도 (인덱스 에러) dp 테이블 만들어서 d1, d2값을 미리 지정해주는 경우는 입력값 n이 1, 2일 상황도 생각해야 한다. 백준에서 런타임 에러(IndexError) 나면 문제 조건에서 입력값 범위 확인하기! ✌ 두 번째 시도 (성공)
👆 첫 번째 시도 (시간초과) profit : i번째 날에 팔았을 때 얻을 수 있는 최대 수익 (i번째 날의 가격) - (0~i-1번째 날 중 가격이 가장 낮았던 날의 가격)을 profit에 저장하되 해당 값이 음수이면 0을 저장한다.
✌ 첫 번째 시도 (성공) stack에는 여는 괄호만 쌓는다. dictionary는 닫는 괄호를 key로 설정했다.현재 원소가 여는 괄호면 stack에 쌓고, 닫는 괄호면 stack 길이 체크 → 길이가 0이라면 여는 괄호가 없는데 닫는 괄호가 들어온 것이므로
번역이 썩 매끄럽지 않아서 이해를 돕기 위해 그림을 그려보았다. 우선순위 큐에 따르면 빨간 색이 몇 번째로 인쇄되는지 구하면 되는 문제이다. q.append(q.popleft()) 역할을 q.rotate(-1)로 수행할 수 있다. rotate(-1)은 원형 큐가 반시계
터진 풍선의 '번호(인덱스+1)'를 출력하는 문제이므로 pop을 하더라도 초기 인덱스 정보는 끝까지 유지되어야 한다. 이를 위해 enumerate가 사용되었다. enumerate 사용 전과 후의 덱 상태를 비교해보자. 덱에 인덱스와 종이 값이 튜플로 묶여서 하나의 원소
팀 이름으로도 멤버를 찾을 수 있어야 하고, 멤버 이름으로도 팀을 찾을 수 있어야 하므로 key(팀명): value(멤버) 쌍으로 이뤄지는 dictionary를 사용하기 좋은 문제다. blackpink: [jenny, jisu, lisa, rose] redvelvet:
한 줄에 눌려있는 프렛 번호를 저장하기 위해 stack을 사용하고, 줄이 여러개이기 때문에 stack들의 리스트를 만들어 사용한다. line: 해당 줄 stack, fret: 현재 누르려는 프렛 번호. stack 상태의 경우의 수를 살펴 보면 크게 아래 7개의 경우가
처음에 브루트포스로 풀었더니 시간초과가 나서(^_ㅠ) heapq로 푼 코드! 우리의 목적은 모든 거인의 키를 센티보다 작게 만드는 것이므로 키가 가장 큰 거인부터 뿅망치를 때려주다가 센티보다 작은 거인에 도달했을 때 뿅망치질을 멈춰주면 되겠다. 거인들의 키를 오름차순이
10시 30분은 1030, 21시 10분은 2110 이런 식으로 입력이 들어오고, 가장 긴 휴식시간을 찾기 위해서는 시각끼리 뺄셈이 필요하기 때문에 계산하기 쉽게 바꿔주는 게 좋다. 0시 0분을 0으로 잡고 10시 30분 → 10*60+30=630
input 개수를 모를 때 입력 처리 방법과 list, set의 속도 차이를 아느냐가 관건인 문제였다.
Python이 정한 최대 재귀 깊이는 sys.getrecursionlimit()을 이용해 확인할 수 있다. BOJ의 채점 서버에서 이 값은 1,000으로 되어 있다. sys.setrecursionlimit()을 사용하면 Python이 정한 최대 재귀 깊이를 변경 가능!
A가 B를 신뢰할 때, B만 해킹하면 A도 해킹할 수 있다. 따라서 B의 연결 정보에 A를 넣어주는 단방향 그래프로 구현해주면 된다. 우리는 B를 해킹했을 때 몇 개의 컴퓨터를 해킹할 수 있는지 'B의 연결 정보'만 필요하기 때문이다.
좌표가 주어지면 해당 좌표의 상하좌우 좌표로 이동할 수 있는지 각각 체크하기 위해 좌표마다 for문을 4번 돌린다. nx, ny는 이동좌표를 나타낸다. 이동좌표가 (-1, -1)처럼 좌표를 벗어나지 않았고 해당 좌표에 놓인 값이 1이라면 그 곳으로 이동할 수 있으므로
가운데에서부터 채워나가려고 그려보니 이동 패턴이 항상 같았다. 가운데 좌표를 시작점으로 잡고 시작점에서부터 채워나가는 순서에 맞춰 숫자를 저장해주면 된다. 시작점은 보이다시피 항상 ((n-1)//2, (n-1)//2)이다.
(0, 0)부터 (18, 18)까지 모든 좌표에서 방향 갯수만큼 for문을 4번 돌려 → ↓ ↘ ↗ 방향으로 쭉쭉 5칸씩을 체크! (바둑돌이 놓여있는 경우에만=즉 좌표에 저장된 값이 0이 아닌 경우에만) x, y는 현재 좌표, nx, ny는 현재 좌표에서 해당 방향으로
코드에서 볼 수 있듯 (0, 0)부터 좌표를 체크한다. 해당 좌표에 아직 방문하지 않았고 집이 있다면 bfs(0, 0)을 호출한다. (0, 0)으로부터 상하좌우로 이동한 후의 좌표를 체크하기 위해 for문을 4번 돌린다. 이동 후 좌표가 좌표범위를 넘지 않고, 아직 방
(0, 0)부터 좌표 체크를 돌린다. 만약 (0, 0)에 아직 방문하지 않았고 이 좌표에 놓여있는 것이 울타리가 아니라면 bfs(0, 0)을 수행한다. bfs 함수에서는 한 영역의 좌표를 모두 방문하면서 양과 늑대의 수를 리턴한다. 2중 for문에서는 이 리턴값을 받아
heapq에 튜플을 삽입하면 튜플 첫번째 원소를 기준으로 정렬된다. 이 문제는 절댓값을 기준으로 오름차순 정렬을 해줘야 하므로 튜플을 이용했다. (abs(x), x)로 절댓값과 본래 값을 묶어서 heapq에 넣어주고, pop할 때는 heapq.heappop(h)[1]로
기차 각각을 원소 20개를 가진 리스트로 생성, 20개를 전부 0(아무도 안 탄 상태)으로 초기화한다. 명령이 1이면 x번째 좌석의 값만 1로 바꿔준다. (원래 x번째 좌석에 사람이 타고 있든 안 타고 있든 어차피 좌석 값은 1이어야 하므로 착석 여부 판별 필요 X)
A에서 B를 만드는 것보다 반대로 B에서 A를 만들어주는 것이 편하다. 1) B가 홀수인 경우 (1) B가 1로 끝나는 홀수인 경우 : 끝자리 1을 제거한 후 판단 (2) B가 1로 끝나지 않는 홀수인 경우: 끝자리 1을 제거할 수도, 전체를 2로 나눌 수도 없으므로
bisect(a, b)는 b가 a에 들어갈 수 있는 가장 오른쪽 위치를 반환한다. a = [1, 5, 6, 7, 10], b = 6이면 b가 5와 6 사이 또는 6과 7 사이에 들어갈 수 있으나 bisect(a, b)는 가능한 가장 오른쪽의 위치를 반환하기 때문에 6과
input으로 들어오는 나무 이름들을 trees 리스트에 넣어주고, Counter(trees)로 각 이름의 빈도를 세어준다. 다만 출력할 때 빈도순이 아닌 이름 사전순으로 출력해야 하므로 정렬단계를 거쳐야 한다.이렇게 Counter를 바로 sorted 구조로 만들어
케이크는 위와 같이 세가지 경우로 나눠 볼 수 있다. 사실 길이 10은 한 번도 안 자르고 케이크를 얻는다는 점에서 따로 분류했지만 30과 하나의 경우로 묶을 수 있는데, 길이가 10으로 나누어 떨어지는 경우: (길이÷10)-1번 자르고 (길이÷10)개 획득 / 길이가
배추가 심어진 곳에서 bfs를 수행한다. bfs는 인접한 배추를 다 체크하고 1을 반환하도록 설계되어 있어서, cnt += bfs(i, j)는 배추구역 하나를 체크할 때마다 지렁이 한 마리를 더하는 역할을 한다. 배추 좌표 (x, y)가 주어지면 해당 배추와 인접한
'-'가 나오면 그 다음 '-'가 나올 때까지 계속 빼 주었을 때 최솟값을 얻을 수 있다. 예를 들어, 40-10+30-50-60+70이 주어지면 40-(10+30)-(50+60+70)-20-80 이렇게 묶어주는 것! 따라서 '-'를 기준으로 나눠주기 위해 입력을 받고
본래 문자열의 순서를 유지한 채 출력해야 하기 때문에 순서를 기억하기 위해 (문자, 인덱스)쌍이 담긴 리스트 dic을 생성했다. ans: 출력할 문자가 담긴 리스트, add: ans에 한 문자씩 추가해본 리스트, minimum: ans에 한 문자씩 추가해보면서 얻은
익마토가 있는 위치의 근처만 살펴보기 위해서 덱에 tomato를 담았다. (nx, ny)는 익마토의 위치인 (x, y)로부터 상/하/좌/우로 이동한 위치를 나타낸다. 이 이동위치에 덜마토가 있다면 익도록 바꿔준다. 이 덜마토가 익은 날짜는 익마토가 익은 날짜의 다음 날
단어가 wolf 순서대로 이루어져 있는지 → seq 리스트로 체크, 단어의 각 문자가 같은 횟수(n번)로 등장하는지 → dic 리스트로 체크! 이 두 가지를 체크해서 둘 다 만족하면 1을 출력하면 되는 문제다. 이제 코드를 하나하나 뜯어보자. 단어가 4글자 이하면 wo
아이디어는 이렇다. 콜론을 기준으로 문자를 나눠서 리스트 adr에 저장한다. 그리고 adr의 원소 8개를 하나씩 체크하면서 길이가 4보다 작은 원소의 앞을 0으로 채워줘 길이가 4가 되게 만든다. 첫번째 규칙은 이렇게 클리어~! 두번째 규칙 클리어를 위해 생략된 0그룹
lesson은 강의시간을 담을 리스트, room은 강의실 사용이 끝나는 시간을 담을 리스트 → 힙으로 만들어서 빨리 끝나는 것을 먼저 처리할 수 있도록 구현! 가장 빨리 끝나는 강의의 종료시간 room[0]과 현재 강의의 시작시간 lesson[i][0]을 비교
📌 문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 ...
위의 조건 때문에 이 문제는 최단경로 문제에 해당하고, 모든 노드의 최단경로를 계산해야 하므로 플로이드 워셜 알고리즘을 사용했다. i 파티장에서 j 파티장으로 가려고 할 때, k 파티장을 경유해서 가는 경우가 더 빠르다면 경유하는 것으로 최단경로를 갱신해준다. 문제에서
P의 위치를 (x, y) 형태로 pos리스트에 저장한다. 나중에 모든 P의 위치들을 조합해서 (x1, y1), (x2, y2)의 거리를 계산하기 위함! is_correct를 1로 초기화했는데, 거리두기가 지켜지지 않은 경우를 발견하면 0으로 변경할 것이다. P의 위치들
일단 시작점은 0번째 돌이므로 a = 0이 된다. a에서 출발해 b에 도달할 수 있는지 체크할 것이기 때문에 b는 1부터 n-1이 된다. a에서 b로 갈 때의 힘을 계산해서 k보다 작으면 b에 도달할 수 있는 것이다. 따라서 reached[b] = 1로 갱신할 것인데,
칼을 사용하지 않는 경우의 최단시간과 사용하는 경우의 최단시간을 구해서 최솟값을 찾아 출력한다. 단, 최솟값이 T를 초과할 경우 Fail을 출력한다. 코드를 뜯어보자. 한 줄씩 입력받아 graph에 저장하면서 해당 줄에 2(=칼)가 있는지 탐색한다. 2가 있으면
10점부터 0점까지 차례로 화살을 쏠 것이다. 이를 위해 지금 몇점에 화살을 쏠건지를 나타내는 focus와 현재 화살 상황인 arrow를 덱에 넣어준다. 어피치를 이기려면 이 과녁에 어피치보다 1개 더 많이 쏘거나, 이 과녁에는 아예 0발을 쏘고 화살을 아껴서 다른
n=1일때부터 1씩 늘려가며 경우의 수를 구해보면 규칙을 찾을 수 있다. 피보나치와 비슷함! n = 1일 때 1개, n = 2일 때 3개, n = 3일 때 5개, n = 4일 때 11개, n = 5일 때 21개, …
규칙을 찾는 게 관건이었던 문제. n번째를 나타내는 n을 먼저 이진수로 바꾸고, n번째 수를 4는 0으로, 7은 1로 바꿔보면 규칙이 보인다. n의 가장 앞자리를 생략하면 n-1번째 수가 된다. 따라서 n번째 수를 찾으려면 n+1을 이진수로 바꾸고 가장 앞자리를 절삭한
쩰리가 오른쪽, 아래쪽으로만 이동할 수 있기 때문에 방향벡터를 두 개 만들어놓고 BFS를 수행한다. 해당 칸에 적힌 숫자만큼만 이동할 수 있고 그 숫자 미만으로 이동할 수는 없기 때문에 조건이 그렇게 까다로운 문제는 아니었다. 다만 visited[nx][ny] = 1
일단 x, y를 입력받고 y가 사정거리(l)보다 큰 경우에는 절대 맞출 수 없으므로 y <= l로 조건을 걸어준다. 이 동물을 사격할 수 있는가를 동물과 가까운 사대에서만 탐색하기 위해 이분탐색을 이용한다. shoot에 x가 들어가려면 몇번째 인덱스에 들어갈지를 bis
빙산의 위치 x, y를 파라미터로 받아와서 빙산 주변의 바다 갯수를 카운트한다. 단, 여기서 바로 빙산을 녹이면 안 된다. 빙산 하나 탐색할 때 바로 녹이면 연결된 다음 빙산이 얘를 바다로 인식해버릴 수 있기 때문에, 연결된 빙산을 모두 탐색한 후에 빙산을 녹여야 함!
모든 노드의 최단경로를 구해야 하는 문제의 경우 플로이드로 풀면 쉽지만, 이 문제처럼 노드의 수가 500개가 넘어가는 경우에는 플로이드를 사용하면 시간초과가 난다. 따라서 한 노드에서 출발해 다른 모든 노드로의 최단경로를 구하는 다익스트라를 여러 번 수행해서 구해야 한
투 포인터로 해결할 수 있다. while문은 end를 한 칸씩 뒤로 이동시켜주기 위한 반복문이다. 홀수의 갯수cnt가 k개 이하이고 end가 n-1 이하라면 계속 실행된다. end가 n-1이 되면 더이상 end += 1 작업을 할 수 없도록 막기 위해 플래그를 0으로
현재 집합에서 라이언의 수가 k 미만이라면 k가 될 때까지 end를 뒤로 한 칸씩 이동시키면서 탐색을 진행한다. 라이언의 수가 k가 되었을 경우 집합의 크기를 체크한다. 이제까지의 최솟값보다 현재 집합이 가장 작은 크기를 갖는다면 정답을 업데이트한다. 더이상 end를
백트래킹 문제 처음 풀어보는데 어렵다 ^_ㅠ..! back_tracking(cnt)은 재귀함수이므로 base condition을 설정해야 한다. cnt == m일 때, 즉 숫자를 m개 모두 골랐을 때 리스트의 원소를 출력하고 리턴한다. 그 외의 경우 1부터 시작해 n까
dfs가 재귀함수이므로 종료조건을 걸어줘야 한다. 그게 cnt == m일 때인데, 숫자를 m개 모두 선택한 상태라면 더이상 숫자를 선택하면 안되기 때문에 여태 고른 숫자를 출력해주고 리턴한다. cnt != m이라면 아직 숫자를 골라야 한다. 1부터 n까지의 숫자를 요번
이동하는 대상이 고슴도치와 물, 2가지이므로 큐에 고슴도치와 물의 위치를 넣어준다. 고슴도치가 굴에 도착하는 시간을 출력하라는 것이 문제의 요구사항이기 때문에 고슴도치는 큐에 위치와 함께 현재 시간도 넣어주는데, 물인 경우 물의 이동시간은 정답을 출력하는 데에 고려되지
이동하는 대상인 지훈이(J)와 불(F)의 위치를 큐에 넣고 BFS를 진행한다. 그리고 지훈이의 탈출 시간을 출력해야 하므로 큐에는 위치와 함께 시간 정보도 넣어준다. (불의 시간은 고려 대상 X → -1로 넣어줌) 또, 주어진 예제만 봐도 한 타임에 지훈이가 불보다
처음에는 k개보다 덜 먹는 경우의 수도 생각해서 푸느라 무수한 '틀렸습니다'를 마주했는데, 애초에 문제에서 '위 할인 행사에 참여하여'라고 명시했으므로 무조건 k개를 먹어야 한다. 따라서 초밥을 탐색할 때 start 포인터와 end 포인터가 뒤로 한 칸씩 같이 이동한다
투 포인터는 start와 end를 동일 지점에서 출발시키는 문제만 풀어봐서 이번에도 그렇게 짰더니 시간초과가 났다. N이 너무 큰가 봄..^_ㅠ 그래서 용액을 오름차순으로 정렬하고 start와 end를 양쪽 끝에서 출발시켜 점점 좁혀오도록 짰다. ans가 10^9+1인
신맛은 sour에, 쓴맛은 bitter에 입력 순서대로 저장하고, 재료를 몇 개 섞어서 음식을 만들어야 하는지 제한이 주어지지 않았기 때문에 1개부터 n개까지 모든 경우의 수를 다 봐야 한다. → Brute Frorce! 따라서 combinations를 사용해 1개
4와 7로만 이루어진 수(이하 4-7수)는 itertools.product를 이용해 구할 수 있다. 한 자리 수를 얻고 싶으면 repeat을 1로, 두 자리 수를 얻고 싶으면 repeat을 2로 지정한다. (4, 4) 형태를 정수로 바꾸는 건
백트래킹 연습을 위해 itertools를 사용하지 않고 풀어보았다. 차근차근 조건들을 하나씩 추가해보자. (1단계) 백트래킹 기본 틀 잡기 (2단계) isUsed 불린리스트를 이용해 해당 인덱스의 원소를 사용했는지를 체크해서 사용하지 않은 인덱스의 원소만 처리한다.
뿌요가 4개 이상 모여있는 곳을 찾아 뿌요를 터뜨리는데, 터뜨린 자리엔 _를 저장한다. 그리고 터뜨린 자리를 bombList에 (x, y) 형태로 삽입한다. bombList의 길이가 0이면 터뜨린 뿌요가 없다는 것이므로 작업을 멈춘다. 하지만 0이 아니라면 터뜨린
like: 회원들의 치킨 선호도가 담긴 리스트, combinations(range(m), 3): 치킨이 m종류이므로 0, 1, 2, 3, …, m-1번 치킨 중 3개를 고른 조합, tmpSum: 고른 a, b, c번 치킨에 대한 각 회원의 최대 선호도를 더한 값
외부 공기와 접촉한 치즈만을 녹이려면, 값이 0인 부분에 대해서만 BFS를 진행하면 된다. BFS 시작 지점은 어디로 해야 할까? 판의 가장자리에는 치즈가 놓여 있지 않다는 조건이 주어졌으므로 가장자리의 어느 한 지점에서부터 탐색을 진행하면 된다.
DP는 너무 어려워,,,,, 도저히 모르겠어서 구글링함 ㅋ 가치가 같은 동전이 여러 번 주어질 수도 있다는 조건이 주어져서 중복 처리를 위해 coins를 set으로 만들어줬고, coins에 동전 종류들을 담았다. dp[i]는 i원을 만들기 위해 필요한 동전의 최소 개수
before: 패턴에서 * 이전의 문자열, after: 패턴에서 * 이후의 문자열, idx_b: 파일 이름에서 before의 위치, idx_a: 파일 이름에서 after의 위치! 만약 파일 이름에 before과 after이 둘 다 들어간다면 idx_b과 idx_a를
[2, 5]는 서류등수순으로 정렬했기 때문에 서류등수는 당연히 앞선 지원자들보다 낮다. 따라서 면접등수만 앞선 지원자들보다 높으면 탈락을 피한다. 앞선 지원자들의 면접등수 중 가장 높은 등수를 구해서 비교해주면 되는데, 아쉽지만 앞선 지원자는 4등, 이 지원자는 5등!
열별로 합을 누적시킨다. 마지막 줄의 39가 첫 열의 합, 109는 둘째 열의 합, 86은 셋째 열의 합, 59는 넷째 열의 합이 된다. 위 직사각형이 입력받은 모양, 아래 직사각형이 열별로 합을 누적시킨 모양이다. 핑크색으로 칠해둔 것처럼 가장 아랫줄의 합을 구해주면
커서를 가운데 두고 커서의 왼쪽에 위치할 문자를 담는 left, 커서의 오른쪽에 위치할 문자를 담는 right를 따로 관리한다. 시간초과를 피하기 위해 커서를 움직이지 않고 한 턴에 문자 하나를 옮겨줄 것이다. ⑤처럼 첫번째 자리에 append해야 하는 경우와