코딩테스트

중복을 허용하는 다중 집합의 교집합과 합집합을 구하는 게 문제 풀이의 관건이었다. 교집합은 구하기 간단했다. 집합 C를 교집합이라고 하자. 집합 B의 원소가 집합 A에도 있다면 집합 A에 그 원소를 삭제하고 C에 추가하면 된다. 이 경우 중복 원소도 min 개수만큼 카

각 손님이 주문한 요리를 코스 요리 수에 따라 조합하고 전체 주문에서 나타나는 횟수를 딕셔너리에 기록한다. get 함수의 디폴트 설정을 통해 쉽게 구현했다. 코스 요리의 최소 기준이 적어도 두 번은 그 조합이 주문되어야 한다는 것이므로 max_cnt를 통해 걸러주었고

유저 아이디를 키, 닉네임을 값으로 하는 딕셔너리를 사용했다. 유저 아이디는 마지막으로 반영된 닉네임을 값으로 가진다. Enter일 때에는 값을 추가, Change이면 값을 변경한다. 출력 리스트에는 Enter 또는 Leave만 반영되므로 각 상황에 따라 마지막으로 남

주어진 집합을 리스트로 변환한다. 콤마가 집합 내에도 있고 집합을 연결하는 기호이기도 했기 때문에 check라는 Boolean 변수를 두었다. 이후 리스트를 정렬, 포함한 원소 수가 가장 작은 것부터 확인해 정답 answer를 만든다. 즉 for 문을 통해 튜플의 가장

거리두기 확인P 기준 맨하탄 거리 2 이하에서 다른 P가 있을 때 거리두기를 지키지 않은 상황이다. 맨하탄 거리가 1이라면 파티션을 확인할 필요 없이 거리두기를 어긴 상황. 맨하탄 거리가 2일 때 파티션 X를 확인해 조건에 따라 거리두기를 지켰는지를 확인하자.P를 기준

프렌즈 4블록특정 좌표를 중심으로 4블록의 일치 여부를 확인한다. 4블록이 모두 같을 때 각 좌표를 집합에 추가하는데, 삭제가 한 번에 이루어지므로 블록을 모두 확인한 이후에 처리해야 한다. 이후 집합에서 좌표값을 꺼내 각 원소를 공백으로 바꿔준다. 블록 삭제 이후 공

방금 그곡재생 시간을 구하고 그 시간 동안의 멜로디를 구한다. 이때 재생 시간이 더 짧거나 더 긴 경우를 모두 고려해야 한다. 이때 기억하고 있는 멜로디가 포함되어 있으면 재생 시간과 인덱스를 함께 기록한다. 음악이 여러 개일 때 재생 시간, 인덱스 순서대로 정렬해 값

영어 끝말잇기단어를 pre_words에 담으면서 길이/유무/'끝말잇기' 확인을 하고 탈락 여부를 결정한다. 탈락 시 몇 번째 사람이 탈락했는지, 몇 번째 차례에서 탈락했는지 인덱스 i와 사람 수 n을 통해 return한다.탈락 조건을 작성하는 것보다 n과 i를 통해 탈

모음사전주어진 모음을 사용해 중복을 허용하는 순열을 만들고 정렬하는 게 관건. product/combination/permutation 차이를 잘 기억하고 헷갈리지 말자.

캐시캐시 사이즈에 따라 cache 리스트를 만들고 cities의 city 순서대로 cache에 있는지 확인한다. cache hit 시 hit한 city를 가장 끝(cache-1)로, cache miss 시 cache에 곧바로 추가할 수 있다면 append, 그렇지 않다

최솟값 만들기코드보다 어떻게 '최솟값을 구하는 곱셈'을 할지가 관건이었다. 테스트 케이스를 통해 알아냈는데, 처음에 구현한 코드는 시간 초과였다. 보다 수학적으로 생각해볼 것.

스킬트리주어진 스킬을 digit 단위로 확인하면서 스킬트리에 포함된 스킬인지 확인한다. 리스트를 통해 주어진 스킬에서 사용된 스킬트리 인덱스를 순서대로 넣는다. 스킬트리에 포함되어 있지 않다면(즉 skill_idx가 비었다면) 상관없으므로 OK. 스킬트리에 포함된 스킬

최댓값과 최솟값공백 기준 문자열을 리스트로 만들고 최댓값, 최솟값 구하기. 연습 문제라서 LV2에 해당하는 것 같다.

다음 큰 숫자크게 두 단계로 나뉜다. 주어진 n을 이진수로 변환하기. n+1의 이진수를 확인하기. 후자를 구할 때 n에서와 동일한 방법을 선택했다가 시간 초과가 떴는데, 이를 방지하기 위해 n의 이진수 n_bin을 통해 1(=2의 0승)의 자리수를 확인해 n+1 이진수

Jaden Case 문자열 만들기문제는 간단하지만 단어의 길이가 1인 경우를 생각하지 못해 런타임 에러가 나기도 했다. 다양한 조건을 확인하고 문제에 접근하자.

올바른 괄호계산기를 구현할 때에는 디큐로 하겠지만, 괄호밖에 없기 때문에 간단하게 check라는 변수로 '('일 때에는 +1, ')'일 때에는 '-1'을 해주었다. 만일 괄호를 확인하는 도중 음수가 되어버리면 가능한 괄호 닫기가 불가능하므로 곧바로 False를 retu

예상 대진표A가 B보다 작을 때, A와 B가 각각 홀수, 짝수이고 1씩 떨어져 있으면 서로 대진한다는 뜻이다. 다른 조건은 사전에 염두에 두고 있었는데, 홀수, 짝수 조건을 생각지 못해 특정 케이스에서 실패하고 말았다. 코딩 테스트를 할 때 테스트 케이스를 내 나름대로

짝지어 제거하기스택 기능을 활용하지 않았을 때에는 시간 초과로 실패한 케이스가 있어서 당황했다. 문제 설명을 다시 보고 지금 들어 오는 문자가 가장 위에 있는 문자와 동일하다면 pop시켜주는 형식으로 빠르게 구현할 수 있었다. 모든 문자열을 확인한 뒤 리스트가 비었다면

주식가격각 시점의 가격의 상승을 전체 기간에서 판단해야 하므로 for문을 돌려 체크, 떨어지지 않은 기간만을 확인하면 되므로 down이라는 Boolean 변수로 체크...해주었는데 지금 생각해보니 down이 필요하지 않은 상황이다(count = 0을 더해도 괜찮으므로)

기능개발하루가 지날 때마다 현재 진도율에 speeds에 기록된 일일 진도율을 반영해주고, 앞 부분에서 100% 이상 패치가 완료된 지점을 찾기 위해 break를 사용했고, 완료된 부분은 progresses/speeds에서 없애주고 답안에 추가한다.문자열을 조작할 때에는

타겟 넘버각 원소마다 +/-를 모두 적용해본 뒤 그 결과값을 target과 비교해야 하므로 디큐를 활용하면 편리하다. 첫 번째 즉 idx=0 원소에 +/-를 적용해 디큐에 넣고 디큐가 빌 때까지 idx를 하나씩 추가해 주어진 numbers 리스트의 끝에 도달할 때까지

124 나라의 숫자3진법처럼 접근한 뒤 result 값을 reverse해서 return하면 된다. 즉 n을 3으로 나눈 케이스에 따라 분류하고, 다음 n은 3으로 나눈 몫이 된다. 하지만 이때 숫자 4가 들어오는 상황을 다르게 처리해야 한다. 4 다음에 다른 자리로 넘

행렬의 곱셈arr1과 arr2의 곱을 구할 때 편이성을 위해 arr2를 transpose해주었다. transpose한 뒤 arr1의 각 row와 arr2의 각 row를 곱했을 때 arr3의 한 row의 col이 결정되므로 for 문을 활용했다. 특히 zip을 사용하니

피로도현재 피로도 K가 지금 진입하려던 던전이 요구하는 최소 피로도보다 높을 때에만 진입할 수 있으므로, 모든 던전을 입장하는 경우의 수를 permutations를 통해 구해 놓고 break를 통해 제어했다. cur_k를 통해 local 피로도를 카운트했다. 처음에는

점프와 순간 이동0에서 출발하는 게 아니라 도착지에서 거꾸로 간다고 가정하면 문제를 풀기 쉽다. n에 도착하기 위해서는 점프가 아니라 순간 이동을 택해야 하며, 따라서 n 이전에 n//2에 위치해 있어야 한다. 짝수인 경우 곧바로 (뛰로) 순간 이동한다고 가정하자. 홀

n진수 게임m명이 참여하는 중 내 차례에서 말할 수 t개를 구해야 하므로, 미리 t\*m 개의 수까지 구해놓고 내 차례에서 말할 수를 카운트하자. 주어진 진법으로 변환한 문자열에서 몇 번째로 택할지는 for 문만 이용하면 어렵지 않게 구할 수 있다. 문제 풀이의 관건은

이진 변환 반복하기'이진 변환'이라는 게 0을 없애고 남은 길이를 이진법으로 변환하는 두 가지 과정을 모두 포함한다는 것을 주의. bin 함수를 사용해서 편하게 만들 수 있었다. 몰랐다면 이진법 함수를 새로 구현해야 했을텐데... 편리하다.

N개의 최소공배수최소공배수를 쉽게 구하기 위해서는 먼저 최대공약수를 구할 필요가 있다. 파이썬 math 함수 내의 gcd를 통해 최대공약수를 쉽게 구할 수 있다. 최소공배수는 num1, num2의 곱을 두 수의 최대공약수로 나눈 몫이다. 이를 통해 최소공배수를 구하는

피보나치 수재귀가 아닌 다른 방식으로 문제를 풀어야 런타임 에러가 나지 않는다. 리스트를 사용해 n(>=2)에 대해서 이전에 구해놓은 f(n-1)과 f(n-2)를 통해 값을 구한다.

압축시작 인덱스와 끝 인덱스를 통해 검사하고 있는 문자열의 범위(w-c)를 구한다. w~c는 딕셔너리에 존재하지 않으므로 이를 추가하고, w~c-1을 출력한다. 끝에 다다른 경우 현재 w~c-1을 출력하고 break, 답을 return한다.이 문제를 푸는 데 있어서 가

괄호 변환균형(즉 '(' / ')' 개수가 일치하는가) 및 올바른(즉 '(' 이후 ')' 매칭이 성공적인가) 형태의 괄호로 변환해 return하는 문제로, 재귀 함수를 사용하는 게 주요 관건이었다. solution(p)로 문제가 나와있는데, solution 함수 자체를

다리를 지나는 트럭문제 설명이 다소 꼬여 있어서 헤맸지만, 테스트 케이스를 풀면서 bridge_length에 따라서 다리 위에서 머무는 시간(즉 큐에 들어와서 나갈 때까지)이 결정됨을 알 수 있었다. 다리, 즉 큐에 삽입될 수 있는 조건은 다음과 같다. 이를 만족할 때

큰 수 만들기(https://programmers.co.kr/learn/courses/30/lessons/42883가능한 만큼(k개) 가장 큰 숫자 앞까지 자른다. 자를 경우 1개씩 k를 감소시켜준다. 구한 가장 큰 자리 수를 다른 곳에 담아두고, 그 이후부터

순위 검색정보를 사전에 저장하고 조건에 해당하는 사람들의 전체 수를 카운트하는 문제로 딕셔너리를 활용할 때 효율적으로 풀 수 있다. 풀이 시간을 줄이기 위해 이진탐색 함수, 정렬 함수 등 또한 사용했다. 주어진 공간이 넉넉할 때 비교문보다 미리 기록해 두는 과정을 통해

후보키후보키가 될 수 있는 어트리뷰트(칼럼)의 경우의 수를 미리 구한다. 각 경우의 수에 따라 튜플을 확인하며 중복된 튜플이 있을 경우 프라이머리 키 조건을 위배하므로 False, 중복되지 않았을 경우에 후보키가 될 수 있다. 이때 이 후보키의 부분 집합이 이미 후보키

셔틀버스버스가 오는 시간이 주어지고, 대기하고 있는 사람이 있다면 최대 m명만큼 타고 갈 수 있다. 콘은 '가장 늦게' 도착해야 한다. 즉 '막차'에서 마지막 사람으로 타야 한다. 문제를 푸는 과정은 다음과 같다. 버스가 9시부터 출발하고 총 n회 t분 간격으로 주어지

배달그래프 내 존재하는 모든 정점에 대한 특정 정점 간의 최단 거리를 통해 답을 도출해야 한다. 즉 다익스트라 알고리즘을 통해 풀 수 있다. 다익스트라 알고리즘은 양방향, 단방향 모두 사용 가능하며 자기 자신을 제외한 나머지 정점과의 거리를 INF로 설정한 뒤 알고리즘

하노이의 탑전형적인 재귀 문제로 '완료 상황'과 '진행 상황' 조건을 그대로 입력한다. 마법 같은 재귀...라고 생각하지만, 사실 재귀는 아직 내게 어렵다. 하노이의 탑 문제를 정리하면 다음과 같다.FROM, BY, TO라는 세 개의 기둥이 주어진다. N개의 원반이 F

단속카메라자동차가 '나가는' 지점에 카메라를 설치하자. 어떤 자동차가 '들어오는' 시점이 그 카메라의 범위에 들어오지 않는다면 카메라를 그 자동차가 '나가는' 지점에 한 대 더 설치하자.

야근 지수각 원소의 제곱의 합을 야근 지수로 결정하는 까닭에, '최댓값'을 작게 만들어야 한다. 즉 한 번 값을 뺄 때마다 리스트 내 최댓값을 리턴하고, 여기에 1을 뺀 값을 다시 더해주어야 하는데, 일반 max 함수 및 sort를 쓸 경우 시간이 오래 걸린다. 파이썬

2XN 타일링DP를 통해 이전에 계산한 값을 그대로 활용한다. 사실 문제가 DP인지는 직접 직사각형을 몇 개 그려본 뒤 알 수 있었는데, 초기값을 그대로 활용했을 때 피보나치임을 알 수 있었다. DP로 문제를 풀기 위해서는 점화식을 찾은 뒤 크기에 알맞은 리스트를 만든

불량 사용자주어진 유저 아이디 중 제재된 수만큼 경우의 수를 골라보자. 순열을 통해 "어떤 아이디가 제재되었는지" 그 리스트를 만들어낸다. 이 리스트의 원소 하나씩 확인하면서 과연 진정 '제재 아이디'와 매치가 되는지 확인한다. 매치가 되는 경우는 '안 되는 경우'를

가장 긴 팰린드롬팰린드롬 체크는 간단하게 본 문자열과 그 문자열을 뒤집은 문자열이 같은 지 확인하는 방법으로 수행했다. 윈도우 크기 K를 처음부터 옮기면서 팰린드롬 가능성을 체크한다. 윈도우 크기 K는 팰린드롬 전체 길이 len(s)부터 1씩 감소한다. 이렇게 K를 1

네트워크DFS를 통해 '연결되어 있는지' 확인한다. 노드를 하나씩 체크하면서 연결 여부를 visited에 기록한다. visited에 기록되어 있지 않다면 사전에 기록하지 않았던 노드이므로 다시 연결한다. 즉 computers라는 연결 여부를 담은 리스트를 사용해 네트워

신고 결과 받기중복 체크 및 카운트가 관건인 문제. 시간 효율성을 위해 리스트가 아닌 딕셔너리로 구현하였다. 딕셔너리/리스트 컴프리헨션을 통해 간결하게 표현하자. 질문 케이스를 살펴보니 시간 초과 등 문제가 있었는데, 파이썬의 경우 딕셔너리가 대부분 (해쉬 기능을 통해

주차 요금 계산IN/OUT을 확인, 차량별 총 주차 시간을 구한 뒤, 번호가 낮은 순서대로 요금을 구한 뒤 그대로 return한다. 로직은 간단하지만 문자열을 가공하고 옮긴 뒤 조작하는 게 관건. 파이썬 3.0의 딕셔너리가 defaultdict인 까닭에 다른 어려움 없

k진수에서 소수 개수 구하기주어진 수 n을 k진수로 변환한 뒤, 0P0/0P/P0/P와 같은 케이스에 따라 소수의 전체 개수를 구하는 문제이다. 이 케이스는 따로 분류할 필요 없이 k진법으로 변환한 수를 0을 기준으로 split한 각 수가 소수인지 아닌지를 확인하면 된

양궁대회어피치가 쏜 채점표 info를 바탕으로 라이언이 쏠 수 있는 경우 2\*10개의 조합을 모두 구한다. 해당 점수를 라이언이 획득하느냐/하지 못하느냐만 확인하면 되므로 어피치가 해당 점수에 쏜 점수 score보다 1 큰 score+1이면 획득, 아예 획득하지 못할

광고 삽입투-포인터 문제로 특정 '구간'에 해당하는 총합을 유도하는 문제이다. 뒤의 인덱스가 앞의 인덱스를 사용한 배열을 이용한다는 점에서 dp이기도 하다. 문제를 분석하면 다음과 같다.영상 범위 play에 광고 시간 adv를 삽입해야 한다. 사람들이 시청한 logs

징검다리 건너기한 번씩 건널 때마다 바위 내구도가 1씩 감소하고, 연속된 k개의 바위의 내구도가 0일 때 바위를 건널 수 없다. 이때 바위를 건넌 총 사람 수를 구하는 문제이다. x명이 연속으로 건널 때 k개의 연속된 단위에서 연속으로 0 이하가 발생하는지 확인하는 문

추석 트래픽(https://programmers.co.kr/learn/courses/30/lessons/17676?language=python3로그(또는 레코드) 기록을 중심으로 정렬 또는 카운트하는 문제가 자주 나오는 것 같다. 이번 문제 역시 밀리초 단위로

가장 먼 노드특정 노드에서 가장 거리가 먼 노드의 개수를 그래프 상에서 구하는 문제이다. BSF를 통해 쉽게 풀 수 있다. 이때 큐를 리스트가 아니라 파이썬 모듈 디큐를 활용하면 보다 시간 효율적이다. 주어진 vertex는 양방향 그래프의 간선이다. 이를 통해 각 노드

입국심사처음에는 힙을 사용했다. 사람 수만큼 루프를 돌리면서 심사관 목록 중 가장 빨리 끝나는 시간을 return하고 한 번 심사를 마친 뒤에는 초깃값을 offset으로 더해주면서 다시 push해주었다. 하지만 문제에서 요구하는 n의 크기와 times의 범위가 매우 컸

디스크 컨트롤러job을 처리할 때까지 걸린 time 안에 다른 job 요청이 들어온다면, 이 job을 처리하는 평균 처리 시간을 최소로 만들기 위해서는 요청 시간 순서대로가 아니라 소요 시간 순서대로 정렬해야 한다. 즉 정해진 조건으로 리스트(또는 힙) 안의 값들을 재

정수 삼각형전형적인 dp 문제로, 이전에 풀었던 값을 재활용하는 문제다. 이 경우 연결된 부모 노드(즉 상위 레벨에서 대각선으로 왼쪽, 오른쪽으로 이어진 노드) 중 최댓값을 계속해서 업데이트하면서 각 노드 별로 취할 수 있는 최댓값을 구한다.dp 리스트를 만든다. 이

순위그래프 내 순위를 파악하기 위해서는 '부모 노드 그룹'과 '자식 노드 그룹'을 포함해 다른 모든 노드와 연결되어 있어야 한다. 예를 들어 총 n명이 있을 때 자신을 제외한 n-1 명 중 3명만 자신을 이겼고 나머지 n-4명은 자신보다 순위가 낮다. 이때 이 사람의

이중우선순위큐힙을 통해 삽입되는 수를 정렬한다. 빈 큐에서 삭제 명령어는 무효라는 조건을 고려해 힙의 원소 개수를 파악해 삭제 명령어가 유효한 경우를 판단한다.삽입되는 수를 정렬하고 순서에 맞춰 입력되는 최댓값, 최솟값 삭제 명령어를 실행해야 한다. 힙을 통해 효율적으

등굣길각 위치로 이동 가능한 경우의 수의 총합은 (가능하다면) 왼쪽에서 오는 경우의 수 + 위쪽에서 오는 경우의 수의 총합이다. 마지막으로 도착지의 경우의 수를 return한다.주어진 행열 리스트를 만들고 시작점에 1, 웅덩이에 -1을 줘서 표시한다.dp를 통해 왼쪽,

섬 연결하기양방향 그래프의 최소 신장 트리를 구한다. 즉 모든 정점을 연결하는 경로의 총 비용이 최소인 경로를 찾아야 한다. 크루스칼 알고리즘을 사용한다.간선의 비용 순서대로 정렬한다.순서대로 간선을 꺼내면서 총 비용을 계산한다. 이때 간선을 이루는 노드가 기존에 계산

줄 서는 방법n명을 줄 세우는 경우의 수 중 k번째에 해당하는 경우의 수를 구한다.파이썬의 permutation 모듈은 시간 효율성이 떨어지기 때문에 직접 factorial 값을 통해 하나씩 구한다.매 차례마다 line 안에 남아 있는 n 명 중 앞 자리에 설 사람이

거스름돈주어진 동전을 사용해 총합이 n이 될 수 있는 경우를 구해야 한다. 0원부터 n원까지 주어진 동전을 통해 총합을 구할 수 있는 경우의 수를 담을 배열 dp동전은 자신 이상의 금액을 치르는 데 사용할 수 있다.cost-coin을 구하는 데 사용되는 경우가 cost

멀리 뛰기1칸 또는 2칸을 뛸 수 있다. 총 n칸을 뛸 수 있는 경우의 수를 구한다.1칸, 2칸을 아무런 조건 없이 마음대로 선택해 뛸 수 있기 때문에, 1칸 전/2칸 전 사용했던 경우의 수를 그대로 활용할 수 있다. 이를 활용해 dp를 사용한다.조합 수식을 사용할

여행경로모든 노드 방문이 아니라 모든 간선을 사용하는 경로를 탐색해야 한다. 특정 노드에서 출발하는 중복 간선을 허용하는 방향 그래프를 DFS로 풀자.주어진 ticket의 tail → head 정보를 바탕으로 딕셔너리로 만든다. 즉 특정 노드에서 갈 수 있는 인접 노드

최고의 집합s를 n개의 자연수 합으로 표현한다. 가능한 모든 조합 중 곱이 가장 큰 경우의 집합을 구한다. 가장 곱이 큰 경우가 어떤 경우일까? 자연수 8를 2개 자연수의 합으로 표현할 때 {1, 7}, {2, 6}, {3, 5}, {4, 4}가 존재한다. 각 곱은 7

합승 택시 설명노드 별 최단 거리를 구해 특정 구간 c를 경유해 a, b에 도착한 경로별 거리를 구하자. 플로이드 워셜 알고리즘을 통해 각 노드에서 (자신을 포함한) 모든 노드로 향하는 최단 거리를 구한다.자기 자신을 0으로, 인접하지 않은(즉 이어진 간선이 없는) 노

N-QueenN X N 위의 좌표 (행, 열)에 퀸이 N개 놓일 수 있다. 이때 퀸이 서로 공격하면 안 되는 경우의 수를 N에 따라 구해야 한다. 즉, 서로 같은 행, 열, 대각선에 퀸이 존재하면 안 된다.row 행에 넣을 퀸의 위치를 정하자. (0 <= row

보석 쇼핑정해진 목록 안에 모든 종류의 보석이 들어가야 한다. 이때 가장 짧은 목록을 구하자.보석 종류를 카운트하면서 시작점과 끝점을 주어진 목록 상에서 이동해가며 확인하는 투 포인터 문제다.끝점을 이동해가면서 모든 종류의 보석을 포함했는지 시작점을 이동해가며 최단 거

문자열 압축i 길이의 문자열을 구한 뒤, 반복 가능한 최대 횟수를 카운트해 이중 최솟값을 return하는 문제다. 문자열을 조작하는 방법을 익히는 데 연습이 되는 문제로 for 문이 끝난 뒤 s_pre에 남아 있는 카운트까지 확인해주는 게 문제를 푸는 소소한 포인트.압

DFS와 BFS양방향 그래프가 주어진다. 시작 노드에서 시작해 DFS, BFS를 통해 탐색한 경로를 출력한다.양방향 그래프이기 때문에 각 노드 별로 인접한 노드를 담는다.스택과 큐를 통해 각각 DFS와 BFS를 표현한다.인접 노드 중 정점 번호가 낮은 순서대로 탐색하기

바이러스DFS/BFS를 사용해 1번 노드와 연결된 모든 노드의 개수를 구한다.시작 노드 (1번 노드)와 양방향 그래프가 주어진다.각 노드 별로 인접한 노드 리스트를 구한다.시작 노드 1번부터 방문할 수 있는 노드 개수를 카운트한다.

1. 문제 설명 >단지번호 붙이기 2. 문제 분석 > 리스트로 입력된 그래프에서 클러스터의 개수와 클러스터 내 노드의 개수를 구한다. 이때 클러스터란 이동 가능한 노드 집합이다. 이동 가능한 노드의 좌표를 모든 좌표에서 찾아 시작 노드로 정한다. 시작 노드에서 이동

유기농 배추그래프 내 클러스터의 개수를 탐색 알고리즘으로 카운트한다.이동 가능한 노드가 1, 그렇지 않으면 0으로 표시된 그래프가 존재한다.클러스터, 즉 이동 가능한 노드 집합의 개수를 카운트한다.모든 좌표에서 시작, 1로 표시된 이동 가능한 노드를 시작 노드로 정하자

미로 탐색시작 좌표 (1, 1)에서 도착지 (n, m)까지 이동할 때 경로의 길이를 구한다.탐색 알고리즘을 사용할 때 노드의 위치와 함께 여태까지 탐색한 노드의 개수도 함께 담는다. 시작 노드와 도착 노드를 경로에서 함께 카운트한다는 데 주의.

토마토탐색 가능한 노드가 1로, 그렇지 않은 노드가 -1로 주어진다. 주어진 위치에서 상하좌우로 이동할 때 모든 노드를 탐색할 수 있는지 확인하고, 가능하다면 걸리는 시간을 구한다.BFS 또는 DFS를 통해 현재 그래프의 주어지 노드에서 -1을 제외한 나머지 노드에 다

숨바꼭질n번 노드에서 k번 노드까지 이동 가능한 방법이 세 가지 있을 때 가장 짧은 시간을 구한다.모든 노드를 미리 만들어 놓는다. 0으로 만들어 아직 방문하지 않았음을 표시하자.시작 노드 n번을 큐에 넣고 BFS를 실행한다. 현재 노드 번호에 +1, -1, \*2를

벽 부수고 이동하기시작 노드에서 도착 노드까지 이동하는 최단 경로를 구한다. 경로 탐색 중 최대 한 번까지 이동할 수 없는 노드로 이동할 수 있다.문제를 푸는 관건은 지금까지 이동한 경로에서 벽을 부순 적이 있는지를 확인하는 방법이다. visited 변수를 3차원으로

N-QueenDFS를 통해 지금까지 놓은 퀸과 다른 행을, for 문 내에서 열과 대각선이 다른 퀸 위치를 체스 판에 넣는다. 행을 하나씩 추가하면서 행이 n이라면 (즉 0행부터 n-1행까지 모두 탐색 성공했다면) 퀸을 놓을 수 있다는 뜻이다.DFS를 재귀 형식으로 구

동전 0주어진 리스트 내 값으로 구할 수 있는, 즉 그리디 알고리즘의 해를 구한다.주어진 값 k가 0이 될 때까지 하나씩 뺄셈을 하는 방식으로 구했지만, 이 경우 시간 초과가 나왔기 때문에 divmod를 통해 빨리 해결할 수 있었다.

회의실 배정끝나는 시간을 빠른 순서대로 주어진 회의를 정렬해, 지금 끝나는 시점에서 선택 가능한 회의를 하나씩 골라간다. 가장 많은 회의를 고르기 위해서는 끝나는 시간이 빠른 순서대로 회의를 정렬한다. 끝나는 시간이 같다면, 시작하는 시간이 빠른 순서대로 고르자.순서대

스택스택 기능을 구현하는 문제input()이 아니라 sys.stdin.readline()을 사용해야 시간 초과가 나지 않는다.

제로0이면 pop, 아니면 push. 마지막으로 스택에 존재하는 모든 수의 합을 출력한다.

괄호(와 ) 개수를 카운트하면서 스택에 넣는다. )는 (와 개수가 같아야 하며, (가 스택에 이미 들어 있을 때에만 올바른 괄호로 사용 가능하다.(가 있을 때만 )를 사용할 수 있다. 이때 스택에서 (을 팝하면서 개수를 맞춰준다.(와 )의 총 개수가 같아야 하는데, )

큐 2큐의 기능을 구현한다. input()보다는 sys.stdin.readline().strip()으로, 일반 리스트보다는 디큐로 구현할 때 시간 초과가 나지 않는다.시간 초과를 해결하는 데 시간을 더 쓴 문제

카드 2큐를 사용해 주어진 작업을 반복하는 문제. 리스트보다 디큐를 사용하자.

요세푸스 문제 0n명 중 k번째 사람을 순서대로 팝한다. 이때 k번째 사람을 구하기 위해 그 앞의 사람들을 맨 뒤로 넣는다. 리스트가 아니라 디큐로 구현할 때 시간 효율을 높일 수 있다.

덱디큐 기능을 구현한다. 사실상 파이썬 모듈에서 deque를 지원하니, 매우 간단하게 구현할 수 있다. 시간 문제상 sys.stdin.readline().strip()을 활용하자.

회전하는 큐파이썬의 디큐는 deque.appendleft와 deque.append를 통해 왼쪽, 오른쪽 모두 삽입 가능하다. 이를 활용해 원형 큐를 만들자.원하는 번호의 수가 현재 큐 안에 몇 번째 인덱스인지 확인하고, 주어진 두 가지 연산(즉 0번을 -1번으로, -1

ACfliped를 확인하면서 왼쪽, 오른쪽에서 주어진 값을 팝한다. 원소가 없을 때 팝한다면 에러다.런타임 에러를 해결하는 데 시간이 더 걸렸다. 원인은 빈 배열을 받아들인 뒤 nums.split(',')를 하고 디큐로 만들기 때문. nums가 빈지 (또는 n이 0인지

최단경로다익스트라 알고리즘을 통해 특정 노드에서 다른 모든 노드까지의 최단 경로를 구한다. 우선순위 큐(힙 구현)를 통해 시간 복잡도를 줄일 수 있다.연결 노드 및 비용을 통해 그래프를 구현한다.초기 상태에서 시작 노드를 제외한 나머지 노드는 갈 수 없다고 취급하자.

특정한 최단 경로특정 노드 v를 경유하려면 start -> v -> end 경로를 각각 나누어 start -> v 최단 경로, v -> end로 나눌 수 있다(중복 간선을 사용 가능하기 때문). 방문할 노드가 두 개이므로 순서에 따라 두 가지 경로를 구해 최단 경로를

수 찾기이분 탐색으로 해당 리스트 안에 특정 원소가 포함되어 있는지 확인한다. 이때 리스트는 정렬되어 있어야 한다.이분 탐색의 기본 조건(start<end, mid 등)을 확인하는 문제heap을 통해 주어진 리스트를 정렬했는데, 파이썬 기본 모듈 sort를 사용해

숫자 카드 2해당 수가 몇 개 있는지 기록한다. 해당 수가 기록한 수 중 존재한다면 개수를, 없다면 0을 리턴한다.이분 탐색보다는 딕셔너리($O(1)$)를 사용하는 게 시간 효율적이다.

랜선 자르기특정 길이로 각 랜선을 나눈 몫의 총합이 n 이상이라면 이 길이는 유효하다. 유효한 길이 중 가장 큰 값을 반환한다.이분 탐색을 할 때 어떤 기준(여기에서는 mid로 해당 원소를 나눈 몫의 총합이 n보다 커야 함)을 만족시키는 값을 모두 얻어낼 수 있다.

나무 자르기랜선 자르기와 마찬가지로 mid를 통해 원하는 기준이 충족된다면 기록해둔다.

공유기 설치집 위치가 담긴 배열이 주어진다. 특정 간격으로 공유기를 설치할 때, 설치 가능한 공유기 간격 중 가장 큰 값을 구한다.공유기를 설치하는 간격이 비교하는 집들 사이의 거리 이하일 때 공유기를 설치할 수 있다. 이때 공유기 '한 대'를 설치했기 때문에 비교하는

ATM정렬 후 누적해가면서 현재 사람이 기다리면서 누적된 시간을 합하자.

잃어버린 괄호최솟값을 만들려면 -나온 뒤의 수는 모두 빼준다고 생각하면 된다. 단, -가 나오기 전까지는 더해주어야 한다.

주유소현재 사용 가능한 주유소 중 가장 싼 기름으로 각 도시까지 갈 수 있다. costs\[i]를 통해 i번까지 중 가장 값싼 기름값 local_cost를 구하고, 이를 통해 이번 차례에 도착할 stations\[i]까지 사용할 비용을 알 수 있다.

최대 힙파이썬의 heapq 모듈을 통해 최대 힙을 구현하려면 -1을 곱해 음수 min-q를 사용하자.input()이 아니라 sys.stdin.readline()을 써야 시간 초과가 나지 않는다.

최소 힙파이썬 heapq 모듈은 기본적으로 min-heap이다.

절댓값 힙절댓값을 기준으로 min-heap을 만들자. 원본 수 역시 가지고 있어야 하기 때문에 \[abs(num), num]을 힙에 넣자.

가운데를 말해요힙 두 개를 사용해 중간값을 구한다. 이때 힙은 최소 힙과 최대 힙으로 \[최대 힙] -> 중간 값 <- \[최소 힙]으로 저장된다. 따라서 최대 힙의 top이 중간값을 저장하고 있다.

숨바꼭질BFS를 통해 리프 노드까지의 깊이를 구하자. 깊이가 가장 긴 루프 노드를 반환한다.

숨바꼭질 3BFS를 통해 최단 경로를 구한다. 이때 다음 노드를 구하는 오프셋의 우선순위에 주의할 것.

숨바꼭질 4BFS로 최단 거리를 구하는데, 움직인 경로를 백트래킹한다.처음에는 BFS로 전달할 때 path를 아예 만들어 전달하면서 기록했는데, 시간 초과로 인해 path라는 리스트를 통해 path\[next_node] = cur_node를 기록했다. 즉 현재 노드 번

노드 사이의 거리플로이드-워셜 알고리즘을 통해 모든 노드에서 다른 노드로 가는 최단 거리를 구한다.

보물섬탐색 가능한 노드에서 BFS를 통해 리프 노드를 찾자. 모든 좌표에서 리프 노드까지의 거리를 카운트한 뒤, 힙을 통해 최댓값을 리턴하자.

상범 빌딩이차원 배열이 아니라 삼차원 배열로 오프셋을 구할 때 z축까지 고려하는 게 특징.시작 노드와 도착 노드를 각각 이미 탐색한 노드, 탐색 가능한 노드로 변경해주면 보다 편하게 BFS를 사용할 수 있다.

호석이 두 마리 치킨BFS를 통해 특정 조합으로 루트 노드 두 개를 설정했을 때 각 노드의 깊이를 구하는 문제다. 깊이를 구했다면, 각 조합에 따른 단순 정렬 및 반환이 끝이다.루트 노드를 두 개 큐에 삽입하더라도 BFS를 통해 동일한 리듬으로 (즉 루트 노드 1과 루

소년 점프시작 노드에서 모든 노드에 대한 깊이를 카운트한 정보를 기록하자. 모든 에이전트가 탐색 가능한 노드라면, 기록된 깊이가 가장 작은 깊이를 고른다.BFS 형태를 통해 손쉽게 구할 수 있는 문제로, 어떤 사정을 요구하는지(예를 들어 빌런이 해당 노드에서 멈춰있을

1. 문제 설명 >인구 이동 2. 문제 분석 > 탐색 알고리즘을 통해 그래프 모든 노드에 대해서 탐색 가능한 범위를 파악한다. 클러스터의 조유와 그 안에 소속한 노드 좌푯값을 기록하고, 노드 값을 평균에 따라 바꿔준다. 클러스터 개수가 전체 노드 개수보다 줄어들지 않

텔레포트플로이드-워셜 알고리즘을 통해 특정 노드를 경로로 사용해 각 노드에서 다른 모든 노드에 대한 최단 거리를 구한다.플로이드-워셜을 푸는 알고리즘보다도 input() 등 입출력 함수 사용으로 인해 시간 초과가 난 문제다. sys.stdin.readline() 등으로

주식그리디 알고리즘. 로콜 최댓값을 어떻게 구하는지가 관건인 문제. 처음에는 인덱스를 앞에서 체크하면서 로컬 최댓값을 max(prices\[idx:])로 구했는데, 아니나 다를까 시간 초과. max 연산을 할 필요 없이 뒤에서부터 기록할 때 효율적으로 풀 수 있었다.

카드 합체 놀이현재 상태의 최솟값을 항상 꺼내려면 우선순위 큐를 택하자.

블로그2그리디 알고리즘이다. 지금 이 시점에서 가장 적게 번갈아 사용할 수 있는 색깔을 택한다. 다시 말해, 인덱스를 따라가면서 색깔이 같다면 한 번 더 칠할 필요가 없다. 바뀐다면 이 색을 칠하는 횟수를 한 번 더 추가한다.

물병n은 1리터 짜리 물병 n개다. 같은 양일 때 합쳐 빈 병을 만들 수 있으므로, 2의 거듭제곱의 합으로 n을 가장 적은 수의 물병을 써서 표현할 수 있다. k보다 현재 물병 수가 많다면 물이 가장 적게 든 물병 두 개를 꺼내서 상점에서 물병을 사들여 빈 병을 만들자

보석 도둑우선순위 큐를 통해 현재 가방에 담을 수 있는 보석을 가격이 큰 순서대로 정렬하자. 이때 min-heap과 max-heap을 사용 목적에 따라 모두 사용할 수 있어야 한다.가방과 보석을 무게가 작은 순서대로 정렬한다. min-heap을 활용하자.담을 수 있는

1로 만들기 2n을 주어진 방법을 사용해서 1로 만드는 문제다. BFS를 통해 노드 1~n개를 만들고, 탐색 방법을 역으로 이용해 가장 먼저 탐색하는 순간까지 카운트한다. 탐색하면서 백트래킹할 수 있도록 현재 노드와 다음 노드 값을 저장한다.

1로 만들기 2n을 주어진 방법을 사용해서 1로 만드는 문제다. BFS를 통해 노드 1~n개를 만들고, 탐색 방법을 역으로 이용해 가장 먼저 탐색하는 순간까지 카운트한다. 탐색하면서 백트래킹할 수 있도록 현재 노드와 다음 노드 값을 저장한다.

카드 구매하기 2i개의 카드를 구매하는 비용은 j개의 카드를 사용할 때, (i-j개의 카드를 사용 비용 + j개의 카드를 사용 비용) 중 선택할 수 있다.DP는 직관적 설명이 이해하기 쉽다.

카드 구매하기카드 구매하기 2 문제와 풀이 방법이 같다.

퇴사 2i번 날 진행한 상담 종료일이 퇴사날보다 전이라면 이 상담을 한 경우와 하지 않은 경우 중 최댓값을 마지막 상담 종료일로 업데이트한다. 상담을 한 경우의 이득은 지금까지 dp에 기록한 값 중 가장 큰 값에 i번 상담을 한 이득을 더한 값이다.인덱스를 거꾸로 돌려

치킨 배달n개 중 m개를 순서에 상관없이 고른다면 조합 combinations를 사용할 수 있다. 모든 치킨 집 중 m개의 치킨 집을 택하고, 각 집의 최단 치킨 거리의 합을 모두 카운트하자. 가능한 조합에서 만들어진 치킨 거리 중 가장 작은 값을 리턴한다.

리모컨브루트 포스 문제로 모든 경우를 체크하면서 가능한 답을 모은 뒤, 최솟값을 출력하자.n의 범위가 500000이지만, 최댓값보다 큰 값을 튼 뒤 -할 수도 있으므로 그 범위를 크게 잡자.if m : buttons = list(input().split())else:

암호 만들기브루트 포스로 가능한 조합의 암호 조합을 모두 만든 뒤, 조건(모음 및 자음 개수)에 맞는다면 출력한다.처음에는 순열(permutations)로 하나씩 케이스를 만들었는데, 이후 조합으로도 충분히 케이스를 커버할 수 있음을 깨달았다.

월드컵국가 간 경기에서 가능한 승패, 무무, 패승 중 하나씩을 택해 마지막 라운드까지 진행한다. 이때 승리, 무승부, 패배 카운트에 따라 한 조합만 가능할 수도 있지만 모든 조합이 가능할 수도 있기 때문에 재귀적으로 접근해야 한다.백트래킹을 사용하는 문제로 어떤 지점에

콘센트최대 힙과 최소 힙을 활용해 시간이 가장 많이 걸리는 기기부터 콘센트 크기가 허용하는 만큼 충전하자. 각 콘센트 자리에는 그 자리에서 기기별 충전시간이 누적 카운트된다. 다 충전한 기기를 뽑을 때에는 그 자리에서 사용한 시간이 가장 작은 자리를 사용하자.주어진 크

정보 상인 호석여러 개의 우선순위 큐를 그때마다 만들어 접근하는 문제. 딕셔너리와 힙을 활용하자.

최소 회의실 개수힙을 통해 가장 회의가 빨리 끝나는 시간을 확인해, 시작 시간이 빠른 회의 순서대로 더 기다릴 수 있다면(즉 이 회의의 시작 시간이 진행 중인 회의 종료 시간보다 느리다면) 회의실을 추가할 필요가 없다. 만일 더 빠르다면(즉 진행 중인 회의를 기다릴 수

순회강연우선순위 큐를 통해 고비용 순서대로 강연을 뽑아, 가장 늦게 강연할 수 있는 날부터 카운트하면서 해당 날짜 별 얻을 수 있는 이득을 기록한다.현 시점에서 힙에 존재하는 가장 이득이 큰 강연을 노트(nodes)에 기록한 이득과 비교하는 과정은 그리디와 유사하다는

이중 우선순위 큐삽입될 수를 담을 최대 힙과 최소 힙을 각각 구현한다. 최댓값을 삭제할 때에는 최대 힙에서, 최솟값을 삭제할 때에는 최소 힙에서 삭제한다. 이때 다른 힙에서 이미 삭제된 값이라면 힙에 수를 삽입할 때 체크한 명령어 별로 유니크한 인덱스 변수를 통해 유효

단어 뒤집기 2문자열 조작 문제로, 인덱스를 통해 하나씩 이동해가면서 단어를 만들어 저장한다.생각해보니 for문으로 풀 수 있었다.

팰린드롬 만들기팰린드롬은 문자열 중간을 기준으로 같은 문자가 반복되는 특수한 케이스다. 홀수, 짝수 여부에 따라 팰린드롬을 확인하자.

안정적인 문자열스택을 통해 {의 개수와 }의 개수를 맞춰가면서 카운트하자. 앞에 {에 담겨져 있다면 }가 들어올 때 안정적인 문자열이 되지만, 그렇지 않다면 바꿔주어야 한다.

단어 맞추기순열을 구하는 방법이다. 사전식 배열 모듈은 파이썬에 없기 때문에 따로 구현해야 한다.

백조의 호수BFS를 위한 큐 네 개를 활용해 이번 차례 탐색한 정보, 다음 차례 탐색할 좌표를 파악할 수 있다. 기본적인 BFS는 쉬웠지만, 메모리 관리 및 시간 관리가 어려웠던 문제다. 어차피 탐색할 노드라면 사전에 미리 visted로 체크할 수 있고, 그 정보를 n

최소 비용 구하기다익스트라 알고리즘을 통해 주어진 노드에서 다른 모든 노드에 대한 최소 비용을 구한다. 우선순위 큐를 통해 효율적으로 풀 수 있으며, 이때 그래프 구현은 딕셔너리가 편하다.

최소 스패닝 트리크루스칼 알고리즘을 통해 최소 신장 트리를 구할 수 있다. 이때 Union-Find를 통해 각 노드의 루트 노드를 구할 수 있다.Find 함수를 재귀 또는 반복문으로 풀었을 때에는 시간 초과가 났는데, 메모라이제이션을 통해 효율적으로 풀 수 있었다.

비밀번호 찾기간단한 해시. 파이썬에서는 딕셔너리 모듈을 활용하자. 최신 패스워드만 사용하면 되므로 dict.get() 등 디폴트 값을 체크하지 않아도 된다.

빈도 정렬딕셔너리를 통해 빈도와 처음 등장한 인덱스를 카운트하고, 이후 딕셔너리 값을 key= lambda x 등을 통해 정렬할 수 있다.

좋다투 포인터를 통해 좋은 수를 제외한 나머지를 정렬한 상태로 생성, start 와 end를 하나씩 가감해가면서 합계를 비교하자.

대칭 차집합집합의 A.intersection(B)를 통해 교집합을 구할 수 있다.

친구 네트워크Union-Find를 통해 노드 별 포함 관계를 표시할 수 있다. 크루스칼 알고리즘에서 사용한 바를 그대로 활용.Find 함수를 사용할 때 메모라이제이션을 통해 재귀 시간을 단축할 수 있다.

전화번호 목록접두사를 비교해 다른 전화번호 목록에 있다면 일관적이지 않은 전화번호가 된다. 중첩 루프를 탈출하기 위해 가장 좋은 방법은 함수를 통해 곧바로 return한다. 반복문을 사용했을 때에는 매번 if로 비교해주어서 시간 초과가 났지만, 함수를 선언하니 중첩 함

사냥꾼처음에는 총 별로 사냥 가능한 사냥감을 카운트하면서 hunted를 체크, 이미 사냥했다면 다른 총에서 체크할 필요 없이 확인했다. 그런데 시간 초과가 나서 이분 탐색을 통해 각 사냥감 별로 사냥한 가능한 x좌표의 최적 총을 찾았다.이분 탐색은 여전히 해결법이 곧바

1EOF를 받을 때까지 테스트 케이스를 입력받을 때에는 try except를 사용하자.

숨바꼭질 5동생의 좌표가 시간이 지나면서 움직이기 때문에 위치가 계속 변한다. 또한 수빈이가 움직이는 +1 -1 연산으로 visited 하나 만으로는 중복 여부를 확인할 수 없다. 홀수, 짝수 여부에 맞춰 두 개의 visited를 사용해야 한다.홀수 짝수 여부를 따로

미확인 도착지양방향 그래프가 주어진다. 시작 노드 s에서 여러 목적지들 goals이 주어질 때, 해당 goal까지 가는 경로에 간선 g-h를 사용했는지 확인하고, g-h가 사용되지 않았다면 예상 가능 목적지에서 제외한다.s-goal에 g-h 또는 h-g 간선이 사용되었

게임DFS를 통해 탐색 가능한 최댓값을 카운트한다. 이때 visited를 통해 방문 여부를 기록하고, dp를 통해 (방문 가능한 경우 방문할 때) 그 노드에 대한 최댓값을 기록해 효율적으로 접근할 수 있다.dp를 쓰지 않으면 시간 초과가 난다. 재귀 사용 접근은 개인적

알고리즘 수업 - 깊이 우선 탐색 1재귀 또는 스택을 통해 DFS를 구현한다.재귀 구현은 에러가 떠서 스택을 통해 구현했다. 스택을 통해 구현할 때 오름차순으로 연결 노드를 스택에 넣는데, 이때 넣는 순서를 주의하자.

알고리즘 수업 - 깊이 우선 탐색 2이전과 스택에 연결 노드를 넣는 순서만 다르다. (내림차순 또는 오름차순)

1. 문제 설명 >알고리즘 수업 - 깊이 우선 탐색 3 2. 문제 분석 > 스택을 통해 DFS를 구현하며, 루트 노드를 0으로 시작해 다음 방문할 노드에 깊이+1을 통해 카운트해준다. 처음 방문한 노드의 깊이만 체크할 수 있다는 점을 유의하자. 3. 나의 풀이

깊이 우선 탐색 3번과 동일한 문제로 스택에 내림차순으로 연결 노드를 방문하는 데 주의.

알고리즘 수업 - 깊이 우선 탐색 5DFS를 통해 각 방문 노드의 깊이와 방문 순서를 카운트한다.

알고리즘 수업 - 깊이 우선 탐색 6이전 문제와 동일. 내림차순 정렬에 주의.

한국이 그리울 땐 서버에 접속하지패턴 매칭을 하는 문제. 전치와 후치를 비교할 때 전치 확인 후 중복 제거를 위해 비교할 문자열 s에서 전치를 제거할 필요가 있다. abc\*cda에서 abcda는 매칭이 안 되는 문자열이기 때문이다.

추월해쉬가 쉽도록 딕셔너리를 활용하자. 딕셔너리를 통해 차가 들어간 순서를 이름으로 기억한 뒤, 나온 순서에 따라 들어온 순서를 함께 비교할 수 있다.

서로 다른 부분 문자열의 개수인덱스를 조정해 커서로 문자열의 부분 문자열을 체크하면서 중복 체크를 위해 집합을 활용한다.

문자열 집합집합을 통해 문자열이 있는지 없는지 확인한다. 파이썬의 집합 set은 $O(1)$이라는 사실을 기억하자.딕셔너리를 통해 각 문자별로 집합을 따로 분류해서 시간을 단축할 수도 있는데, 유의미한 차이는 아니었다.

IOIOI처음에는 있는 그대로 패턴 p를 만들고 그 길이만큼 비교했는데, 아니나 다를까 시간 초과가 났다. 패턴이 공통적으로 반복되어 있으니, 부분적으로 나눠서 패턴을 카운트하고, 그 개수만큼 패턴이 나오면 그때 비로소 패턴 p가 들어 있다고 적자. 이럴 경우 비교되는

생태학EOF까지 입력받는 걸 신경쓰는 게 더 어려운 문제.

신입 사원그리디 알고리즘 문제로 다른 사람들과 비교했을 때 특정 사람 보다 한 종류의 순위만 높아도 합격된다. 서류 심사 순위로 정렬한 뒤, 다른 한 사람과 비교해가면서 면접 심사 순위의 순위를 로컬 최솟값으로 정하면서 카운트하자.

보물두 수의 곱을 최소로 만들기 위해서는 두 수 간의 차가 최대가 되어야 한다. 반대로 곱이 최대가 되려면 차가 최소여야 한다.

햄버거 분배가장 멀리서 먹을 수 있는 햄버거부터 먹는다는 원칙으로 풀 수 있다.

카드 문자열string.ascii~를 사용해 손쉽게 알파벳 리스트를 호출할 수 있다.

1, 2, 3 더하기 4점화식을 구해 dp를 푼다. dp(n, 1) = dp(n-1, 1)dp(n, 2) = dp(n-2, 1) + dp(n-2, 2)dp(n, 3) = dp(n-3, 1) + dp(n-3, 2) + dp(n-3, 3)dp(n) = dp(n, 1) +

안전 영역탐색 알고리즘을 통해 탐색 가능한 범위를 모든 노드에서 찾는다. 방문한 노드를 -1(또는 True)로 마킹하면서 중복 탐사하지 않도록 방지한다.비가 오지 않는 순간부터 안전 영역의 최대 높이까지 비가 올 케이스를 모두 고려해야 한다. 문제 이해도가 떨어져 처음

쇠막대기스택을 통해 스택 안에 있는 쇠막대의 개수를 카운트했다. 레이저를 ( 바로 다음에 )가 올 때 플래그 비트를 통해 파악했다.본 문제에서 실제 스택만이 아니라 스택을 가장한 카운트만으로도 문제를 풀 수 있다. 가령 (가 들어왔다면 +1을 하는 식으로 스택 내부의

트리리프 노드의 개수를 카운트하는 문제다. DFS 또는 BFS를 사용하자. 다음 노드를 방문할 수 없는 조건일 때 리프 노드임을 알 수 있다. 주어진 트리에서 루트 노드가 여러 개인 경우, 루트 노드가 잘린 경우 모두를 포함해야 한다는 점을 주의하자.

로프로컬 최댓값을 구하는 그리디 알고리즘.

30그리디 알고리즘 태그를 보고 들어갔는데 정수 성질에 관해 생각하고 푸는 문제였다.\* unzip을 통해 손쉽게 반복문을 사용하지 않아도 풀어서 쓸 수 있다. (sep은 덤)

수들의 합서로 다른 자연수를 n개 더해서 s를 만들 때, 가장 큰 n을 구하는 문제다. 수학적 원리르 통해 손쉽게 풀 수 있다.서로 다른 수를 가장 많이 사용해 특정 수를 만드는 방법은 1+2+3+...+n이다. 이 식은 간단하게 $n(n+1)/2$인데, 이 합을 $s

1, 2, 3 더하기그리디 알고리즘 점화식을 구하자.점화식을 구할 때 초기 조건으로 주어지는 케이스를 모두 풀어보고 어떻게 점화식이 도출될지 생각하자.

2xN 타일링dp\[n] = dp\[n-1] + dp\[n-2] if n > 2

연결 요소의 개수모든 노드를 확인할 때 방문이 안 되어 있다면 그 노드를 시작 노드를 하고 큐에 넣자. 다음 노드를 확인하면서 방문 가능한 모든 노드를 방문하자. 이렇게 큐에 한 번 넣어서 방문 가능한 노드는 연결된 클러스터다.

연구소빈 칸에 벽을 세 개 세울 수 있다. 이때 itertools.combinations를 사용해 벽을 세울 수 있는 조합을 쉽게 구할 수 있다. 모든 케이스에 대해서 로컬 그래프를 만들고, 바이러스가 퍼져나가는 탐색 알고리즘(여기에서는 BFS로 구현)을 실행한다. 0

적록색약그래프를 조건에 따라 두 개로 나눈다. 원본과 R=G를 동일하게 만든 그래프를 원본을 통해 하나 더 만들면 된다. 그리고 모든 노드를 돌면서 방문하지 않은 노드일 때 그 노드를 기준 색깔로 삼고 경계를 카운트하면 된다.연결 상태, 일종의 클러스터 개수를 물어보는

균형잡힌 세상스택을 통해 최근에 들어간 괄호가 이번에 닫는 괄호의 종류와 매칭이 가능한지 체크하면서 균형이 깨졌는지 체크한다. 모든 문자열을 확인한 뒤 스택에 남아 있는 괄호가 없다면 균형 잡힌 문자열이다.

듣보잡set을 통해 풀었는데, 딕셔너리를 통해 접근해도 되는 문제다.

접미사 배열힙큐는 너무 편리하다.

뒤집기처음 시작하는 수를 기준점으로 삼고, 기준점과 다른 지점을 만나면 뒤집어야 한다. 이때 뒤집기 시작한 후 연속해서 뒤집을 때에는 카운트하지 않아야 하므로 flipped라는 플래그 비트를 사용했다.

프린터 큐큐 내에 존재하는 문서의 우선순위 정보를 파악하기 위해 먼저 Counter 모듈을 통해 개수를 구했고, 우선순위 로컬 최댓값 개수를 카운트하면서 0이 될 때 다음 우선순위를 가리키도록 지정했다. 케이스 문서 인덱스를 맨 앞의 경우와 나누어 뒤로 가거나 앞으로

나는야 포켓몬 마스터 이다솜딕셔너리에 저장된 키와 값을 반대로 만드려면 딕셔너리 컴프리헨션을 사용하자. dict_inv = {val:key for key, val in dict_original.items()} dictionary.items()는 키 값을 튜플 형태로 반

오큰수스택을 통해 내 기준점에서 오른쪽에 있는 수들이 무엇인지 확인한다.

패션왕 신해빈딕셔너리를 통해 빠르게 타입 별 값의 개수를 구하고, 조합을 통해 가능한 옷을 입을 수 있는 경우를 빠르게 카운트하자.

섬의 개수대각선까지 이동 방향에 포함해야 한다.

토마토z축까지 넣어서 이동 방향을 설정한다.

알파벳로직 자체는 어떤 탐색 알고리즘을 사용해서든 풀 수 있다. 하지만 파이썬은 시간, 메모리 초과 관련해서 주의할 사항이 많은 문제다.원래 큐나 스택을 디큐로 푸는데, 여기에서는 set으로 풀어야 시간초과가 나지 않았다. 또한 pypy에서는 메모리 초과가 나는 코드가

Z재귀적 풀이로 조건에 맞는 상황만 재귀 함수를 호출하는 게 시간 초과가 나지 않는 방법.

케빈 베이컨의 6단계 법칙플로이드-워셜 알고리즘을 통해 k번째 노드를 경유지로 사용, i에서 j로 갈 수 있는 거리가 더 짧아진다면 이를 교체한다. 이를 통해 모든 노드에서 다른 모든 노드에 대한 최단 경로를 구할 수 있다.

테트로미노케이스 바이 케이스로 총 19개가 나온다. 하나씩 코드를 적기는 너무 소모적이라 그나마 공통적이라 판단되는 블록의 공통 개수를 카운트, 하나씩 블록을 추가해가면서 로컬 최댓값을 구했다. 물론 이때 인덱싱 관련 문제로 인해 다소 헤맸다.

DSLR현재 노드에서 변형 가능한 식이 주어지고, 범위 안에 있고 방문한 적이 없을 때 방문해가면서 최소한의 방문 횟수를 카운트하는 문제. 이 문제는 특히 이 조건식을 어떻게 사용했는지를 기록해야 하기 때문에 큐에 따로 path를 함께 전달하거나 백트래킹을 사용해야 한

스택 수열커서 인덱스를 두고 스택 안에 target이 존재하는지 여부를 통해 pop할 것인지 push할 것인지 확인

집합의 표현union-find를 통해 합집합인지 아닌지 확인할 수 있다. 특히 find 함수에서 메모라이제이션을 통해 재귀 호출을 줄일 수 있다.

탑(> https://www.acmicpc.net/problem/2493)스택을 통해 자신보다 높은 탑이 왼쪽에 있는지 확인해간다. 스택 확인이 끝난 뒤에는 자신이 오른쪽 탑들 기준에서는 새로운 스택의 top이 된다는 데 주의.

카드 정렬하기우선순위 큐를 통해 최솟값 두 개를 pop한다.

구간 합 구하기세그먼트 트리는 구간 합을 빠르게 구할 수 있는 자료구조로, 트리 형태로 부모 노드가 자신의 자식 노드의 총 합을 저장하기 때문에 $O(nlogn)$만에 원하는 값을 얻어낼 수 있다.초반에는 dp로 풀었는데, 아니나 다를까 시간 초과. 세그먼트 트리라는

중량제한크루스칼 알고리즘을 통해 높은 가중치부터 연결시켜나가면서 원하는 도시가 연결되었는지 매번 간선이 추가될 때마다 확인하자. 새로운 간선이 추가될 때 현재 total을 최소 중량으로 업데이트한다. 이때 들어오는 중량이 현재 값보다 작다고 보장하기 위해 heap 같은

단어 수학십진수 자리 수는, 그 자리 수가 n이라고 할 때 $digit\*10^{n-1}$이므로 들어오는 수를 통해 해당 수가 전체에서 얼마나 카운트되는지 파악할 수 있다. 딕셔너리를 통해 빠르게 저장하자.

캠핑휴가날에 맞춰서 캠핑을 시작한다고 가정해서, 진행되는 구간을 최대한도로 확보하자. 남은 기간 동안 진행 가능한 일이 남아 있다면 실행하자.

A → BA -> B에서가 아니라 B -> A로 단축하는 가장 빠른 방법을 카운트한다. 변환 식이 모두 적용이 안 된다면 결국 변환 불가능하다는 뜻이므로 루프문을 빠르게 종료해야 한다.

기타줄6개 패키지로 살 때 최솟갑을 구하고, 나머지는 패키지로 구매할 때가 더 싼지, 낱개로 살 때 더 싼지 비교한다. 이때 패키지는 자동으로 6개들이라는 점을 기억하자.

수 묶기두 개씩 묶었을 때 가장 이득이 되는 경우는 양수는 큰 수대로 정렬, 음수는 작은 수대로 정렬해서 앞에서 두 개씩 묶는 것이다. 이때 양수는 주의할 점이 1은 묶는 것보다 더하는 게 이득이라는 점이다. 물론 -1과 같은 경우는 덧셈이 곧 뺄셈이기 때문에 신경쓸

베스트셀러딕셔너리로 카운트한 뒤 값으로 정렬한다. 이때 정렬 기준을 key=lambda x:(-x\[0], x\[1])로 세팅하는데, x\[0]은 클 수록, x\[1]은 작을 수록 우선순위를 높게 준다는 뜻.

문서 검색커서를 통해 검색하려는 문자가 존재하는지 확인하자. 존재한다면, 중복 체크가 안 되므로 인덱스 범위를 검색하는 문자 길이만큼 옮겨버린다.생각해보니 검색이 실패한다면 첫 글자가 나올 때까지 넘기는 게 더 빠를 것 같다.

이친수dp를 풀 때 초깃값이 어떻게 활용되는지 파악하기 위해 수를 늘려가면서 점화식을 얻어내자.

퇴사퇴사 2와 동일 문제.

1. 문제 설명 >문자열 폭발 2. 문제 분석 > 스택을 통해 현재 접근 가능한 가장 뒤의 문자에 들어오는 문자를 입력했을 때 폭발 문자가 되면 폭발 문자를 없앤다. 처음에는 파이썬 문자열 모듈의 find 메소드를 사용했는데 시간 초과가 나왔다. 이후 문자열을 바꾸

1. 문제 설명 >문자열 2. 문제 분석 > A 길이만큼 B를 슬라이싱해 비교를 피할 수 없는 순간의 비굣값을 카운트, 최솟값을 출력한다. 3. 나의 풀이

1. 문제 설명 >영역 구하기 2. 문제 분석 > 모든 범위에서 탐색 알고리즘을 실행해 노드 개수를 카운트, 기록한다. 3. 나의 풀이

경로 찾기플로이드-워셜 알고리즘(시간 복잡도 $O(n^3)$을 통해 i번째 노드에서 j번째 노드로 가는 최단 경로를 구할 수 있다. 이 문제에서는 경로가 있다면 1, 없다면 0으로 표시하는데, 거리가 무한대면 경로가 없는 것으로 본다.

나이트의 이동BFS로 최소 이동 거리를 구하는 전형적인 문제. 오프셋이 다양했다.

트리의 부모 찾기BFS를 돌면서 다음 노드를 방문할 수 있다면 (즉 여태까지 방문한 적 없는 노드라면) 다음 노드가 현재 노드의 자식 노드다.

플로이드간선 비용 중 최솟값만 받아들여야 한다.

여행 가자플로이드-워셜 알고리즘으로 각 노드 별 다른 모든 노드에 대한 최단 경로를 탐색하고, 여행 계획으로 들어오는 인접 노드 간 최단 경로가 무한(즉 경로 없는 노드들)인지 체크한다.

강의실 배정우선순위 큐를 통해 연장 가능한 강의실과 새로 할당해야 하는 강의 기준을 나눈다.

N번째 큰 수우선순위 큐를 통해 n번째 큰 수를 구한다. 메모리 초과를 하지 않으려면 힙 사이즈를 유지해야 한다.

거짓말탐색 알고리즘을 확인할 때 방문 여부를 두 번 확인하는 문제.

스타트와 링크조합을 통해 두 가지를 나눈다. 이때 combinations으로 만들어지는 조합의 양끝은 서로 배타적인 집합인데, 이를 이용해 쉽게 차를 구했다.

3의 배수기본적인 문자열 조작 문제

두 용액이분 탐색을 통해 left와 end 인덱스 값을 더했을 때 어느 부분이 0에 가까운지 체크한다. 연산을 하면서 0에 가장 가까운 (즉 절댓값을 사용) 기록이 있다면 인덱스를 기록해둔다.

카드딕셔너리 .get 메소드는 디폴트 값을 사용하기 떄문에 편리하다.

스타트링크BFS를 통해 목적 노드까지 가는 횟수를 카운트

내리막 길DFS를 백트래킹하는 문제로, 시간 초과로 인해 DP를 적용해야 한다

트리의 지름트리의 지름(이때 깊이가 아닌 비용의 최댓값)은 트리 내 특정 노드에서 최장 거리에 존재하는 노드를 구하고, 그 노드에서 다시 한 번 최장거리를 구해 글로벌 최장 거리를 구해야 한다.루트 노드를 구한다 하더라도 지름이 깊이가 아니라 거쳐온 비용의 합계에 따라

트리의 지름다른 트리의 지름 문제와 같은 문제.

욕심쟁이 판다DP와 DFS를 함꼐 사용해야 시간 내 풀 수 있는 문제다. DP에 현재 노드에서 이동 가능한 개수를 담아, 기록한 값이 있다면 DFS를 돌리지 않고 그대로 사용하는 데 초점을 둔다.

퍼즐BFS를 통해 특정 상태에 도달했는지 확인한다. 이때 방문 여부는 그 과정의 상태 그래프를 담고 있어야 하기 때문에 집합 또는 딕셔너리를 사용하자.

텀 프로젝트사이클이 생기는 순간, 사이클의 길이를 카운트하는 문제다. 이때 사이클에 연결된 노드를 자를 수 있는 코드가 필요한데, 노드들을 담아내는 리스트를 통해 어디까지 사이클이 잘리는지 파악할 수 있다. DFS, Union-Find 등 사이클 파악 여부 알고리즘을

PPAP스택을 통해 뒷부분 4자리를 PPAP와 매칭하면서 pop하자.

이진 검색 트리전위, 중위, 후위는 재귀를 통해 푸는 게 보다 직관적이다. (서브 트리라고 가정해서) 그 트리의 루트, 왼쪽 서브트리, 오른쪽 서브트리가 있을 때 출력 기준이 루트 노드라고 하자. 재귀를 주는 순서는 각 탐색 방향이다. (즉 중위라면 왼쪽, 루트 출력,

공항Union-Find 함수 중 부모 노드를 찾는 Find 노드를 활용하는 문제였다. 처음에는 순서대로 for 문 루프를 통해 break가 일어나는 순간까지 카운트했는데 시간 초과가 났다.

문제집위상 정렬을 통해 푸는 문제. 정렬 기준이 (정해진 기준이 없다면) 번호가 작은 게 우선 순위가 크므로 min-heap 사용한다.

줄 세우기위상 정렬 문제로, 정해진 정렬 우선순위가 없기 때문에 일반적인 큐로 구현했다.

최종 순위위상 정렬을 통해 순위가 변경되었을 때의 정렬된 노드를 출력하는 문제다. 연결 그래프를 통해 head와 tail을 표시하고, in_degree를 통해 head의 입장에서 연결된 tail의 개수가 0일 때에만 큐에 삽입하는 건 일반적인 위상 정렬과 동일한데, 순

네트워크 연결최소 신장 트리를 구한다. 크루스칼 알고리즘을 통해 구현했다.

도시 분할 계획최소 신장 트리를 구한 뒤 마을을 두 마을로 분리하려고 한다. 간선의 최솟값을 얻으려면 최소 신장 트리를 구성하는 간선 중 최댓값을 없애야 한다. 간선 비용을 더할 때 리스트를 통해 더하고, 마지막에 더해지는 값을 제외하자. 우선순위 큐를 통해 들어오는

전력난최소 신장 트리를 구해 기존 간선 비용 총합에서 최소 신장 트리를 구성하는 간선 비용의 합을 뺀다.

행성 터널크루스칼 알고리즘을 통해 최소 신장 트리를 구했다. 이때 힙에 넣는 간선의 수가 매우 많아질 수도 있는데, 최소 비용이 되는 터널만 넣으면 되므로 각 축을 기준으로 정렬하여 최소한의 개수의 간선만 만들도록 한다.

해킹다익스트라를 통해 시작 노드에서 건너갈 수 있는 노드가 있다면 그 노드에 대한 최단 거리를 구한다. 이때 영향을 미치지 못하는 노드와의 거리는 처음에 설정한 INF로 세팅되어 있다는 데 주의.

녹색 옷 입은 애가 젤다지?다익스트라를 통해 시작 노드에서 목적 노드까지 가는 최단 거리를 구한다.

파티특정 노드 i -> 도착 노드 x, 도착 노드 x -> 특정 노드 i까지 가는 경로의 합이 최댓값인 노드 i를 구해야 한다. 양방향 간선이 아니기 때문에 각 i마다 x에 대한 최단 거리를 구하기 위해 다익스트라 알고리즘을 사용해야 한다.

거의 최단 경로다익스트라 알고리즘을 사용해 최단 경로를 얻어내고, BFS를 통해 최단 경로에 사용된 간선을 제거할 수 있다. 이후 다익스트라 알고리즘을 사용하면서 (이때 이전의 간선은 사용할 수 없다) 거의 최단 경로를 얻는다.최단 경로를 구하기 위해 다익스트라 알고리

도로포장다익스트라 알고리즘과 DP를 함께 사용해 푼다. 이때 DP의 관건은 큐에 현재까지 포장한 개수를 넘겨주는 데 있다.

작업위상 정렬과 DP를 통해 푸는 문제다. 위상 정렬을 통해 이전 작업을 마칠 때마다 다음 head에 그 시간을 더해간다. 그런데 다른 tail에서 마치는 시간이 더 클 수도 있기 때문에 dp를 통해 더 큰 값을 고르자.

음악 프로그램위상 정렬 조건 중 정렬이 불가능한 경우는 in-degree를 하나씩 제거해갈 때, 다음에 queue에 삽입되는 노드가 존재하지 않는 상태다. 즉 while문이 조기 종료되기 때문에, 정렬된 노드의 수가 정렬하려는 기존의 수보다 작다.

게임 개발백준 2056 작업과 정확히 동일한 문제. DP를 응용해서 head에 걸리는 시간을 누적하면서 최댓값을 기록해둔다.

임계경로위상 정렬에 DP를 적용해 해당 노드에 대한 최장 거리를 구할 수 있다. 이를 응용해 최장 거리에 사용되는 간선을 BFS를 통해 거꾸로 역추적하자.거의 최단 경로라는 문제에서 비슷한 기법으로 풀었는데, 그때에는 다익스트라를 통해 최단 거리를 구한 뒤, 거꾸로 B

ACM CraftDP를 적용한 전형적인 위상 정렬 문제

선수과목위상 정렬에서 큐에 들어가는 순서를 기록한다.

행성 연결크루스칼 알고리즘을 통해 최소 스패닝 트리를 구한다. pq에 값이 남아 있더라도 연결한 간선의 개수가 n-1, 즉 주어진 정점에서 1을 뺀 수와 같다면 조기 종료.

나만 안되는 연애우선순위 큐에 넣는 간선을 조건화해서 넣어야 풀리는 문제다.

전기가 부족해union을 할 때 서로 다른 루트 노드가 모두 발전소라면 연결해서는 안 된다.

도로검문비활성화할 수 있는 간선은 최대 1개로, 최단 경로를 구성하는 간선을 비활성화해야 거리를 바꿀 수 있다. 다익스트라와 BFS를 통해 최단 경로를 구성하는 간선을 카운트할 수 있고, 하나씩 비활성화 -> 활성화하면서 한 번씩 다익스트라를 돌려 각 간선을 비활성화했

최소비용 구하기 2다익스트라 알고리즘과 BFS를 통해 최단 거리를 구성하는 간선을 찾을 수 있다. 이를 통해 출발 노드에서 도착 노드까지 이어지는 경로를 역추적한다.

K번째 최단경로 찾기다익스트라를 통해 해당 노드에 대한 최단 경로를 계속해서 업데이트한다. 총 k번째 경로를 찾아야 하므로, distances의 이차원 배열을 통해 거리를 갱신해가면서 확인.

네트워크 복구다익스트라 알고리즘을 통해 시작 노드에서 각 노드까지 최단 경로를 구하는 데 사용하는 모든 간선의 집합을 구하자.

택배k번째 노드를 일종의 경로로 사용하는 순간 path를 업데이트한다. 플로이드-워셜 알고리즘을 사용했다.

플로이드 2플로이드-워셜 알고리즘을 통해 각 노드에서 다른 모든 노드에 대한 최단 거리를 구하면서, k번 노드를 경유해서 업데이트할 때 path\[i]\[j]에 새롭게 업데이트된 k번 노드를 사용한 경유지로 다시 쓴다.

https://www.acmicpc.net/problem/14950클러스터에 연결된 간선만을 heap에 넣으면서 그때마다 다음 간선을 선택한다.

학교 탐방하기크루스칼 알고리즘을 통해 MST를 구했다. 이때 MST에 먼저 연결되는 간선의 종류를 따로 우선순위 큐에 저장한 뒤, MST를 구해가면서 이 종류의 간선을 쓸 수 있는 최댓값을 구하자.

키 순서플로이드-워셜 알고리즘을 통해 i와 j번 노드 간의 거리를 구할 수 있다. 이때 i번에서 j번까지, 그리고 j번에서 i번까지 거리가 무한대라면 우열을 매길 수 없다.

플로이드-워셜 알고리즘의 nodes\[i]\[j]는 곧 i번 노드에서 j번 노드로 향하는 최단 거리다. 이때 사이클은 i번에서 시작해 i번으로 도착하는 간선들의 집합인데, nodes\[i]\[j]+nodes\[j]\[i]는 i번에서 출발, j번까지 갔다가 i번 노드로

저울백준 2458 키 순서와 유사한 문제로 값이 무한(즉 닿을 수 없을 때)임을 통해 비교가 가능한지 확인할 수 있다.

역사nodes\[i]\[j], nodes\[j]\[i] 가 각각 INF(도달 불가)인지 확인함을 통해 순서 비교

궁금한 민호플로이드-워셜 알고리즘은 k번 노드를 일종의 경유지로 사용, i번 노드에서 j번 노드까지 가는 경로를 단축시키는 알고리즘이다. 이때 이를 거꾸로 k번째 노드를 사용한 것을 비활성화할 수도 있다. 서로 다른 i, j, k번 노드를 사용할 때 nodes\[i]\

레이저 통신방향과 거울 개수를 큐의 원소를 통해 계속 확인하면서, 거울을 통해 방향을 틀 수 있다면 이를 반영한다. 같은 개수의 거울을 사용할 때까지는 같은 곳을 여러 번 방문 가능하다는 점이 관건.

서강 그라운드플로이드-워셜 알고리즘을 통해 최단 경로를 얻고, 이를 활용해 i번 노드에서 다른 j번 노드까지의 최단 경로가 수색 범위 안에 있는지 체크한다.

다리 만들기 2크루스칼 알고리즘으로 MST를 구하는 문제. 간선의 길이를 구하는 게 더 귀찮은 문제.

택배 배송다익스트라.

동전 1다이나믹 프로그래밍을 통해 계산 가능한 동전의 경우의 수를 합하자. n원 짜리 동전 하나로 n원을 계산하는 경우의 수는 1이다.

합분해다이나믹 프로그래밍

백양로 브레이크일방향과 양방향의 의미를 노드 값을 통해 표현하고 플로이드-워셜 알고리즘을 통해 연결할 때 곧 양방향으로 연결해야 하는 노드의 총합이 구해지도록 하자.

KCM Travel다익스트라를 통해 현재 들어오는 해당 노드로 가는 최소 시간을 비용을 맞추면서 dp로 체크한다.

비밀 모임플로이드-워셜 알고리즘을 통해 각 노드에서 다른 모든 노드로 가는 최단 거리를 찾는다. 이동할 노드 행 열 값을 모두 더해서 최소가 되는 인덱스를 왼쪽에서부터 고르자.

타임머신벨만-포드 알고리즘은 특정 노드로부터의 다른 모든 노드에 대한 최단 거리를 구하는 방법이다. 다익스트라 알고리즘보다 시간 복잡도는 좋지 않지만 음수 가중치를 구할 수 있으므로 범용성이 있다. 음수 사이클이 존재할 때 문제를 풀 수 없기 때문에 정점 개수만큼의 반

민준이와 마산 그리고 건우다익스트라 알고리즘을 통해 1번 노드에서 다른 모든 노드에 대한 최단 거리를 구한다. 도착지에서 거꾸로 출발지까지 BFS를 실시하면서 사용한 경로 중 원하는 건우가 위치한 노드가 있는지 확인하자.

등산다익스트라 알고리즘 ▷ 도착 노드 기준 다익스트라 알고리즘을 돌려서 로컬 최댓값을 뽑는다.

백도어다익스트라에서 업데이트하는 노드 코스트에 조건을 하나 더 추가한다.

일요일 아침의 데이트다익스트라를 통해 쓰레기를 지나는 최소 경리의 거리를 카운트한다. 다익스트라 알고리즘보다는 다음 노드가 빈 칸 .일 때 인접 노드에 쓰레기가 있는 거리 역시 카운트해야 하고, 정확한 개수가 아니라 있는지 없는지 여부만을 확인해야 하는 등 문제 해석이

Strahler 순서위상정렬을 통해 in_degree가 0이 되는 순서를 파악한 후 문제에서 요구하는 사항(tail 노드의 strahler 값이 몇 개 존재하느냐에 따라 다음 strahler 값을 설정)을 충족시켰다.

영우는 사기꾼?위상 정렬의 in_degree를 활용한다. 해당 노드가 '존재'한다면 곧 삽입 가능한지 확인(in_degree가 0인지)하고, '삭제'한다면 그 노드가 필요한(즉 tail인) 다른 노드의 in_degree를 1씩 증가시킨다.

웜홀음의 가중치가 존재할 때 특정 노드에서 다른 모든 노드에 대한 최단 경로를 벨만-포드 알고리즘을 통해 얻을 수 있다. 이때 음의 사이클이 존재하는지 확인하자.

골목길벨만-포드 알고리즘을 통해 시작 노드에서 도착 노드까지 최단 경로가 아닌 최장 경로를 구한다. 도중 사이클이 존재한다 할지라도 도착 노드까지 가는 데 사이클이 생기지 않는다면 (즉 노드의 개수가 n이고 n번째 반복에서 거리 값이 업데이트될 때 업데이트되는 거리 노

세부크루스칼 알고리즘과 BFS를 통해 풀었다. MST 중 시작점 s에서 도착점 e까지 이어지는 간선을 따라 최솟값을 구하다가, e에 연결되는 지점에서 간선이 가지고 있는 최솟값 가운데 최댓값을 뽑는다.

물대기크루스칼 알고리즘을 통해 최소 신장 트리를 구한다. 이때 i->j 간선 비용과 i->i 간선 비용을 비교해야 하는데, i->i 간선 비용을 0->i 간선으로 처리한다.

도시 건설크루스칼 알고리즘을 통해 MST가 만들어지는 확인한다.

안정적인 네트워크1번 노드를 제외한 MST를 만든다. 문제 해석이 관건.

겹치는 건 싫어투 포인터 문제로 left, right 커서를 조절하면서 가능한 로컬 최댓값을 기록해둔다.투 포인터 문제 실력을 늘리자.

수들의 합투 포인터를 통해 범위 합을 기록한다. m과 비교하면서 m이 되는 순간 cnt를 1씩 증가시키면서 총 몇 개의 가능한 경우의 수가 생기는지 확인

배열 합치기pypy로 제출하니 시간 보정을 받았는지 내장 모듈로도 시간 안에 통과.

두 수의 합정렬 -> 이분 탐색으로 두 포인터를 통해 합계를 x와 비교한다. x보다 크다면 right 커서를 줄이고 x보다 작다면 left 커서를 늘려야 한다.

수열투 포인터로 부분합을 확인

주몽이분 탐색을 통해 풀이.

먹을 것인가 먹힐 것인가투 포인터를 통해 대소 관계를 비교해 인덱스 범위를 구한다.

부분합투 포인터를 통해 조건을 충족한 길이의 최솟값을 얻는다.

용액투 포인터를 통해 양쪽에서 범위 내 가장 큰 수, 가장 작은 수의 합을 기록해두면서 가장 0과 가까운 인덱스를 찾는다.

수 고르기투 포인터를 통해 두 개의 수(중복 가능) 차이를 기록해 m보다 크다면 local_diff 중 최솟값을 기록한다.

세 용액용액 문제와 동일한 매커니즘. 용액 하나를 고정해두고 for 문을 통해 mid, right를 구해 0과 가장 가까운 조합을 answer 리스트에 기록한다.

다이어트제곱수의 성질을 이용해 푸는 문제.

용액 합성하기용액 문제와 정확히 동일한 문제.

로봇 프로젝트테스트 케이스까지 관리해야 한다.

줄어드는 수DFS를 통해 백트래킹한다. 왼쪽 수가 오른쪽 수보다 커야 하고, 수 number가 비어있다면 값을 그대로 주거나 출력할 수 있다. 중복 수는 집합으로 체크하자.

차이를 최대로DFS를 백트래킹을 사용해 푼다. DFS를 통해 전달하는 파라미터는 모든 경우의 순열.

N과 M (5)백트래킹을 통해 푸는 순열 문제. 순열의 개수가 정확히 m일 때에만 출력.

모든 순열전형적인 순열 백트래킹

N과 M (8)중복 순열 문제.

외판원 순회 2DFS 및 백트래킹을 통해 출발 노드에서 출발, 도착 노드가 같다면 그때까지 방문한 도시 개수를 카운트해 최솟값을 갱신한다. 이때 로컬 최솟값과 다음에 방문한 노드 비용을 비교해야 시간 초과를 피할 수 있다. 파이썬으로 풀 때에는 이 부분으로 인해 계속

국왕의 방문다익스트라 알고리즘을 사용한다. 사용 중인 간선을 파악해 업데이트 가능한 시간을 갱신하는 게 주요 문제 풀이 관건.

합리적인 이동경로다익스트라를 통해 T 기준 최단 거리를 구한다. 이를 통해 특정 노드에서 T를 가는 경로보다 다른 경로(즉 특정 노드와 연결된 다른 노드 사용한 경로) 거리가 더 짧다면 이를 합리적인 이동경로라고 한다. DP를 통해 시작 노드 1번의 합리적인 이동경로를

숫자 카드이분 탐색으로 풀었는데 시간 초과가 나서 집합으로 검사했다. ...키워드에 이분 탐색이 있던 이유가...?

예산이분 탐색.

게임이분 탐색을 통해 문제를 풀려고 노력했다. 값이 바뀌지 않는다면 -1, 그렇지 않는다면 mid 값을 기록한 ans를 출력하자.

기타 레슨정렬하지 않고 이분 탐색을 사용해야 한다.

알고스팟간선 체크가 아니라 행렬 자체를 입력받아 구현한 다익스트라 알고리즘.

장난감 조립위상 정렬과 DP를 혼합한 문제. 기본 부품과 중간 부품의 의미를 파악하는 게 관건.

부분수열의 합백트래킹을 통해 부분 수열을 택한 부분 합을 구하자.

숫자 야구완전 탐색 문제로 모든 경우의 수마다 조건을 확인해주자.

소 운전한다이차원 그래프로는 시간 초과로 인해 풀 수 없었다. 몇 시간을 보내다 결국 검색 후 일차원 배열 안에 모두 넣어 푸는 방법을 볼 수 있었다. 본 문제에서 V, k 값의 최대 범위가 주어지기 때문에 가능한 방법이다.

저울그리디 알고리즘 문제는 언제나 어렵다...

사탕 게임브루트 포스 구현으로 행, 열을 각각 바꿔주며 그 시점의 최대 개수 ans를 리턴한다.

DNA카운터를 통해 풀면 편리.

생일정렬 lambda 활용하기

창영이와 퇴근다익스트라를 통해 최대 경사의 최솟값을 비용으로 한 최단 거리의 거리 집합을 구한다. 다음 노드로 가는 비용이 현재 비용 또는 경사 중 최댓값임을 주의.

복제 로봇MST 문제를 크루스칼 알고리즘으로 풀려면 간선이 필요한데, 본 문제를 푸는 키워드는 어떻게 간선을 구하는가?이다. 행렬을 통해 제시된 특정 노드 간의 간선을 구하기 위해 양 노드 간 연결 가능한 최단 거리를 BFS를 사용해 구하자.

Watering the FieldsMST 문제로 간선 비용이 특정 수치보다 높을 때에만 우선순위 큐에 넣고 크루스칼 알고리즘을 사용하면 되는 문제. 시간/메모리 관련은 (적어도 파이썬에서는) 간선의 개수가 정점의 개수 n보다 1 적은 n-1일 때 바로 탈출하면 된다.

불우이웃돕기MST를 통해 최소 연결 비용을 구하고, 그래프를 이루는 총 비용에서 뺀다.

Arctic Network크루스칼 알고리즘으로 MST를 구하는 문제로, 채널 개수 S에 따라 MST 별로 구하는 간선의 개수가 달라지기 때문에 문제 해석에 유의.

미로 만들기다익스트라 알고리즘.

등산다익스트라 알고리즘을 통해 집에서 목표까지의 최단 거리를 구하자. 학교에서 목표까지의 최단 거리 또한 구할 수 있다. 특정 목표를 경유지로 사용할 수 있다면 (즉 다익스트라로 얻어낸 거리값이 무한대가 아닐 때) 성취감과 거리값의 차 중 최댓값을 구할 수 있다.다익스

집 구하기여러 개의 다익스트라를 돌리기보다 더미 노드를 통해 다익스트라를 돌리는 횟수를 획기적으로 줄일 수 있다는 인사이트를 갖고 가자.

별자리 만들기MST를 얻기 위한 간선 비용을 유클리드 거리를 통해 구할 수 있다.

도로문제 이해가 가장 어려웠다. 우선순위는 간선이 존재할 때 간선을 이루는 노드 번호 i, j에서 i<j인 케이스를 간선으로 넣는다. 연결되어 있다는 말은 곧 (MST에 사용된 간선) + (MST를 이룬 n-1개의 간선에 m-(n-1)개만큼의 간선을 우선순위에 따

MST 게임크루스칼 알고리즘을 반복해서 특정 구간의 MST를 구한다.

행렬그리디 알고리즘. 처음 순간에 맞지 않으면 3X3 매트릭스를 변환.

수리공 항승그리디 알고리즘으로 앞에서부터 정렬, 테이프 범위를 기록해서 카운트

크게 만들기스택을 통해 현재 가장 위에(즉 뒷자리) 있는 숫자보다 들어오는 숫자가 크면, (변경 가능한 시점에서) 바꾸는 게 더 큰 수를 만들 수 있는 방법이다.

인간 대포시간을 기준으로 다익스트라 알고리즘을 사용한다. 각 노드 간의 시간을 구하는 게 문제를 푸는 관건으로, 시작점에서는 걷기만 사용된다는 데 주의하자.

인터넷 설치최단 거리를 다익스트라 알고리즘으로 구하는 게 관건이 아니다. 특정 값을 최소 지불 비용 cost_budget으로 삼았을 때 도착지 n까지 이동하는 데 사용한 간선 비용 중 cost_budget 이상인 간선의 개수가 무료로 이용 가능한 간선의 개수 k 이하여

악덕 영주 혜유크루스칼을 통해 MST와 MST에 사용한 간선을 기록할 수 있다. MST에 사용한 간선으로 그래프를 만들어, 다익스트라 알고리즘을 통해 특정 노드에서 다른 노드로 가는 경로의 길이 중 가장 긴 값을 구할 수 있다.

방탈출비상탈출구를 0번으로 둔 뒤 연결한다면 MST를 구하는 문제로 변한다.

세금다익스트라를 통해 간선을 사용한 횟수를 카운트할 수 있다. 이차원 배열 distances를 통해 이를 기록하자. 간선에 추가 비용을 추가하면, 이동 거리가 크더라도 간선 이용 횟수가 적다면 총 이동 거리가 짧아질 수 있기 때문에 모든 경로를 간직하고 있어야 한다.

개코전쟁다익스트라를 통해 특정 노드까지 가는 경로를 구할 수 있다. 이때 경로를 구성하는 특정 간선만 비활성화한 채로 다익스트라 알고리즘을 사용할 수 있다.

정기검진'다리'를 시작점으로 집과 병원을 이어줄 수 있다. 어느 다리에서 출발했을 때 최소 거리가 걸리는지 모르기 때문에 (그리고 집과 병원의 위치에 따라서 달라질 수 있기 때문에) 모든 다리를 시작점으로 사용해 다익스트라 알고리즘을 사용할 수 있다. (집+병원+다리)

지하철다익스트라 알고리즘을 통해 확인하는 파라미터가 두 개(환승 횟수/이동 비용)로 환승 개수가 우선순위가 높다. 우선순위 큐를 통해 환승 횟수가 낮다면 이동 비용이 크더라도 먼저 뽑는다. 이때 기록하는 distances는 이차원 배열로 선언해 환승 횟수까지 모두 기록

1. 문제 설명 >Road Reconsturction 2. 문제 분석 > 2차원 배열로 그래프를 입력받고, 상하좌우 연결된 간선이라 생각하자. 다익스트라 알고리즘을 통해 입력된 값이 최소가 되는 루트를 찾을 수 있다. 도착지에 도착 가능할 때 그 최소 거리를 출력한다

고속철도 설계하기기존 연결된 간선을 통해 union-find 실행, 추가될 간선을 통해서 모든 노드가 연결되었는지 파악할 수 있다. 정확한 의미의 MST는 아니지만, 크루스칼 알고리즘을 응용해 풀 수 있다.

도로MST에 포함된 간선을 확인한다.

유럽여행간선 비용을 재계산해야 원하는 의미의 MST를 구할 수 있다. 노드를 사용하는 비용 + 왕복 비용까지 모두 카운트해야 하기 때문이다.

조별과제 멈춰!크루스칼 알고리즘을 통해 MST를 구성하는 간선 정보 및 비용을 추출할 수 있다. 이를 통해 BSF로 특정 노드에서 출발해 다른 노드로 가는 경로 중 간선의 최댓값을 dp에 기록하자.

오르막 수점화식을 구해서 푸는 dp 문제다. n번째 카운트는 곧 n+1 번째 9의 총 카운트다.

타일 채우기점화식을 찾아야 하는 dp 문제. dp\[0] = 1로 설정하는 조건을 찾는 게 관건.

뱀시뮬레이션 문제로 처음 위치에서 출발해 특정 조건에 다다를 때까지 반복하는 문제다.미로 행렬 그래프를 구현해 쉽게 접근할 수 있다. 이때 방향, 다음 좌표 등을 구하는 함수를 구하면 편리하다. 시뮬레이션 문제에 익숙해지자.

핑크 플로이드플로이드-워셜 행렬을 통통해 인접 리스트를 재구성하는 문제로, 크루스칼 알고리즘을 응용한다. MST를 구성하는 최소 길이 간선은 특정 두 컴포넌트를 잇는 간선으로 사용되며, union-find를 통해 컴포넌트가 같은지 확인할 수 있다.

헤븐스 키친최대 신장 트리를 통해 최대 시청률을 구한다. union-find를 통해 트리를 구성하는 간선으로 인접 리스트를 만들 수 있다. 만든 인접 리스트 내 노드 간 리프/루트 관계를 알 수 있다.승자/패자가 루트/리프 노드 관계로 표현할 수 있음을 알아내는 게 이

과제우선순위 큐를 통해 현 시점에서 가장 큰 점수를 가진 과제를 뽑을 수 있다. 이때 과제를 할 수 있다면 가장 늦게 하고, 그렇지 못하다면 하지 않는다.

도서관그리디 알고리즘으로 양/음 경우를 나누어 카운트한다. 이때 m 권을 가지고 갈 수 있는데, 최대 거리를 기준으로 모든 책을 가지고 이동할 경우의 거리를 기록하자. 이중 가장 긴 경우를 마지막으로 뺴놓고, 왕복이므로 2배.

센서수신 가능한 영역이 최솟값이어야 그 합이 최소가 된다. 수신 가능한 영역은 곧 각 센서 위치의 차의 합으로 계산할 수 있다. 수신의 개수는 n-k개로, 집중국 k개만큼 커버할 수 있기 때문에 전체 n개 중 k개를 뺀 수만큼만 계산한다.

A와 B문자열 개수의 차만큼 주어진 조건대로 A 또는 B를 체크.

주사위겉면에 드러나는 최솟값을 구하는 문제로, 전개도 상 마주보는 두 수가 존재하므로 이 중 최솟값을 3개 고른다. 주사위의 특정 면이 3개, 2개, 1개씩 드러나는 횟수를 구할 수 있으므로 이를 카운트하는 그리디 알고리즘.

배해당 시점에 무게 제한 이하 무게가 들어오면 옮길 수 있다. 모두 옮길 때까지 반복.

행복 유치원키 순서대로 정렬한 뒤, 가장 키 차이가 적게 나는 경우를 n-k번만큼 뽑는 그리디 알고리즘

택배처음에는 출발 기준 오름차순으로 정렬했지만, 풀리지 않는 경우가 있었다. 1번 노드에서 시작하기 때문에 1번과 가장 가까운 위치에 도착한 시점에서, "택배 출발지부터 도착 전까지 얼마나 많은 짐을 싣고 다니는가"가 주요 확인 포인트가 된다. 배열을 통해 각 구간 별

간선 이어가기 2일반적인 다익스트라

늑대 사냥꾼나무와의 거리가 인접 행렬로 표현된 거리가 된다. 이를 사용해 BFS를 사용해 시작점에서 도착점까지 가는 경로를 파악할 수 있다. 경로 중 나무와의 최솟값을 answer에 갱신하자.

무엇을 아느냐가 아니라 누구를 아느냐가 문제다다익스트라를 통해 업데이트 시마다 노트에 경로를 기록하자.

면접보는 승범이네도시에서 면접장까지 걸리는 최단 거리를 다익스트라 알고리즘을 통해 구한 뒤, 최댓값 및 도시 번호를 구한다.도시에서 면접장까지의 거리가 아니라 면접장에서 도시까지 걸리는 거리를 구해야 한 번에 구할 수 있다. 단방향 그래프이므로 그래프 구현시 거꾸로 구

소가 길을 건너간 이유 7다익스트라 알고리즘으로 움직인 횟수를 카운트하면서 풀을 먹을 때를 고를 수 있다. 처음에는 움직인 카운트가 3의 배수가 되면 노드 값을 추가하고, 나머지는 t를 더해주었다. 이 경우 업데이트가 똑바로 되지 않아(3의 배수가 되기 전 t를 더한

소수마을현재 노드와 다음 노드 간의 거리가 소수일 때에만 갱신에 사용할 수 있다. 다익스트라 알고리즘과 소수 판별 알고리즘을 혼합해 사용한다.

Bad Cowtractors최대 스패닝 트리를 구하는 문제

Jungle Roads일반적인 크루스칼 알고리즘 문제. 노드 번호가 정수가 아니라 캐릭터이기 때문에 딕셔너리를 통해 매핑한다.

There is No Alternative원본 MST를 형성하는 간선 집합과 MST 비용을 구한 뒤, 각 간선을 원본 그래프에서 제외한 뒤 다시 한번 MST를 구해보자. 만일 MST 값이 달라진다면 그 간선은 '대체 불가능한' 간선이다.파이썬에서는 시간 단축을 위해 원

DFS와 BFSDFS와 BFS를 각각 재귀와 큐를 통해 구현했다.파이썬이 아니라 스위프트로 처음 알고리즘을 풀어본다. 이미 알고 있는 내용이라지만 입출력 및 배열 선언 등 구현 과정에서 많은 부분에 숙달할 필요가 있다.

미로 탐색BFS를 통해 시작점에서 도착점까지 최솟값 비용을 구할 수 있다. 스위프트에서는 파이썬의 zip을 어떻게 표현할까?

1. 문제 설명 >단지번호 붙이기 2. 문제 분석 > 전체 범위에서 이동 가능한 노드가 있다면 BFS (또는 DFS) 실행, 탐색 가능한 노드를 탐색한 노드로 만들면서 개수 체크. 3. 나의 풀이

바이러스일반적인 탐색 알고리즘을 통해 풀 수 있다. 이때 원본 컴퓨터의 개수를 제외해야 하는 데 주의.

토마토탐색 알고리즘으로 행렬 그래프를 탐색하면서 마킹하면서 최대 비용을 기록한다. 탐색을 마친 뒤 행렬 그래프 중 0이 남아 있다면 탐색 불가능한 지역이 남아 있다는 뜻이다.스위프트는 큐가 없기 때문에 BFS를 사용할 때 구현해주어야 한다. 팝 구현을 배열의 remov

연구소조합 및 큐를 사용한 BFS가 필요한 문제다.스위프트 내 내장 모듈에 조합/큐가 존재하지 않기 때문에 조합의 경우 for 문을 반복, 중복 체크해 구현했다. 하지만 이 경우 3개만 고르기 때문에 구현이 간단했고, 고르는 게 많아질 때에는 별도로 함수를 구현해야 한

지진이분 탐색을 통해 MST에서 사용할 이득 수식의 x (mid)를 결정한다. 정렬/우선순위 큐를 통해 이득을 최대화할 수 있다. 이득을 표현하는 수식을 찾고, 이를 MST를 찾을 때 정렬하는 키로 삼아야 하는, 두 가지 개념을 혼합한 문제.

1. 문제 설명 >레드 블루 스패닝 트리 2. 문제 분석 > 간선 비용이 모두 동일할 때 특정 종류의 간선을 사용해서 MST를 만들 수 있는지 확인하는 문제다. 우선순위 큐를 두 개 만들어 각 종류별로 우선순위를 다르게 한 redpq, bluepq를 따로 만들어 파란

최단경로평범한 다익스트라 알고리즘 문제로 최단 경로를 구한다. 하지만 스위프트는 힙 등 우선순위 큐를 제공하지 않기 때문에 직접 힙 구조체를 만들어 사용해야 하는데, 이 과정이 문제를 푸는 대부분을 차지한다. 우선순위 큐를 사용하지 않는 방법으로는 시간초과가 나기 때문

지각하면 안 돼비용/시간을 모두 비교 기준으로 삼고 다익스트라 알고리즘을 사용해야 한다. distances를 이차원 배열로 파악하고 일차적으로는 비용, 이차적으로는 시간에 따른 이득이 있을 때 값을 갱신한다. 제한 시간 및 제한 비용에 따라 필터링하기 때문에 이차원 배

동전 0일반적인 그리디 알고리즘.

1. 문제 설명 >회의실 배정 2. 문제 분석 > 정렬 이후 그리디 알고리즘을 통해 할당 가능한 회의실을 체크하고, 현재 진행 중인 회의가 끝나는 시간과 바로 다음 들어오는 회의 시작 시작을 비교하자. 파이썬의 람다 함수 정렬 방법을 몰라 문제 제출 88% 쯤에서

최소 스패닝 트리크루스칼 알고리즘을 통해 최소 스패닝 트리 비용을 구한다.스위프트에서 구현한 크루스칼 알고리즘에서 비용 순서대로 간선을 정렬해 하나씩 확인하는데, 내장 모듈에 힙이 없기 때문에(파이썬에서는 힙을 사용했다) 배열에 간선 저장 후 정렬한 결과를 반복문을 통

네트워크 연결정확히 이전 MST 문제와 같은 문제

행성 터널MST 문제로 전형적인 크루스칼 알고리즘 문제. 간선 비용이 주어지는 게 아니라 좌표를 통해 구해야 하는 게 독특하다. 그런데 모든 노드 별 거리를 매칭하면 메모리 초과가 나기 때문에, 정렬을 통해 가장 가까운 노드끼리의 거리를 차례대로 입력하자. 이때 노드

다리 만들기 2BFS를 사용한 컴포넌트 분리 + BFS를 이용한 노드 별 최단 거리를 통한 간선 만들기 + 크루스칼 알고리즘을 통한 MST의 청 세 가지 기법을 결합해 푸는 문제.파이썬으로 이전에 풀었던 문제로, 크루스칼 알고리즘에 넣어줄 데이터 전처리 과정이 관건인

단어 수학딕셔너리를 활용해 자릿값까지 고려, 특정 알파벳이 총 몇 개 언급되는지 카운트한다. 내림차순 정렬 뒤 9부터 수를 주어 값을 계산.파이썬의 dict.get(key, default)가 스위프트에서는 dict\[key, default:certain value]로

문자열 폭발스택을 통해 마지막 부분의 문자가 폭발하는 문자열일 때 팝하는 아이디어를 떠올리는 게 문자. 사실 아이디어보다는 적절한 구현 방식으로 시간 초과가 나지 않는 게 두 번째 관건이었다.처음 제출한 코드에서는 시간 초과가 났는데, 짐작컨대 배열의 joined()

Eight puzzle정답지에서 이동 가능한 모든 모습을 이동 횟수와 함께 기록, 들어오는 입력값의 해당 카운트를 출력한다. 만일 기록되어 있지 않다면 불가능한 조합.

Eight puzzle파이썬으로 풀었을 때와 동일하게 풀었다. BFS를 통해 정답에서부터 가능한 모든 경우의 수 및 이동 횟수를 딕셔너리에 기록했고, 주어진 입력값이 없을 때에는 불가능함을 알 수 있었다. 스위프트에서는 큐가 자료구조 모듈로 제공되지 않기 때문에 일반

레드 블루 스패닝 트리크루스칼 알고리즘은 한 번 사용할 때 정렬을 한 번만 사용해도 되기 때문에 우선순위 큐를 굳이 사용하지 않아도 시간 초과가 나지 않는다는 점이 스위프트에서 편하다.

보물섬BFS를 브루트 포스로 돌려 특정 육지에서 출발, 도착 가능한 가장 긴 육지까지의 거리를 리턴하고 최댓값을 기록했다.이 부분을 해결하는 과정이 가장 관건이었다. map을 문자열 이차원 배열로 활용해 접근하려고 했는데(스위프트에서 문자열 조회는 문자열 인덱스로 접근

연료 채우기현재 기름으로 갈 수 있는 주유소를 모두 확인해서 가장 기름이 많은 주유소부터 하나씩 채워가자. 도착지까지 주유하면서 갈 수 있는지 확인할 수 있다.그리디 알고리즘 문제로 힙을 두 종류 사용하는 문제였다. 탐색 알고리즘보다 개인적으로 그리디 알고리즘이 더 어

말이 되고픈 원숭이방문 체크를 말처럼 이동 가능한 횟수까지 기록할 수 있도록 하는 게 포인트.

인구 이동BFS를 통해 인접 행렬에서 연결된 국가 간의 연합이 가능한지 컴포넌트를 구성할 수 있다. 컴포넌트를 딕셔너리에 기록하고, 인구 이동(노드별 값의 총합 평균으로 주기)이 가능할 때까지 반복한다.

얼음 미로이동 가능할 때까지 연결된 이동 방향으로 계속해서 빙판 비용을 더한다. 이동 가능하다면, 그리고 다음 장벽이 구멍이 아니라면 그곳으로 점프(다익스트라 갱신, 힙에 넣는다). 출구까지 가는 최단 거리를 다익스트라로 찾아 리턴하자.

전화번호 목록정렬 및 프리픽스 비교를 통해 겹치는지 체크. 스위프트 문자열에 이런 기능이 있다는 걸 알았다.

플로이드각 노드에서 다른 모든 노드에 대한 최단 거리를 찾고 싶다면 플로이드-워셜 알고리즘을 사용하자. 시간 복잡도가 큐브라는 데 주의.

도서관스위프트에서 divmod 같은 모듈이 있으면 좋을 것 같다.

호석사우르스이동 횟수를 카운트해서 3으로 나눈 나머지의 수에 따른 이동 방법을 제한한다. 따라서 나머지에 따른 차원을 distnaces에 추가해두면 편리하다.

발전소 설치이미 연결되어 있음을 표시하기 위해 존재하는 간선에 가중치를 0으로 두자.

레이저 통신BFS를 통해 좌푯값과 진행 방향, 거울 카운트를 기록하면서 visited라는 방문 체크 + 최소 거울 카운트 기록 매개변수를 통해 도착지에 갈 때까지 최소 거울 카운트를 유지하자.

줄 세우기전형적인 위상 정렬이다. tail과 head를 분리한 뒤, 차수(몇 개의 노드가 스스로를 가리키고 있는가?)가 0인 노드부터 먼저 큐에 넣자.

골목 대장 호석 - 효율성 2다익스트라 알고리즘에서 거리 업데이트 시 간선을 비용할 때 제한 비용 limit를 설정해두는 문제다. limit는 그래프를 구성하는 간선의 최솟값부터 최댓값 중 하나로 이분탐색의 키(왼쪽, 오른쪽)으로 사용한다. limit를 통해 도착지로

1. 문제 설명 >수 묶기 2. 문제 분석 > 정렬 후 두 개씩 수를 곱할 수 있을 때, 가장 값이 큰 결과를 얻기 위해서는 (양/음 모두) 수의 차이가 가장 작은 두 수를 곱한 값을 더하는 것이다. 이때 예외는 양수 1을 곱했을 때에는 값이 같기 때문에 1은 덧셈으

A Great Way다익스트라 알고리즘을 통해 distances를 구한 뒤 이를 통해 경로를 추적할 수 있다. 입력으로 받아들이는 그래프가 방향 그래프임에 주의.

제국다익스트라 알고리즘을 통해 최단 경로(곧 최단 시간)을 구하는 문제로, 3차원 배열을 통해 가능한 똇목의 경우를 고려했다.

연예인은 힘들어특정 노드에서 시작점/도착점까지 걸리는 거리를 합했을 때 최솟값이 나오는 노드를 살펴봐야 하기 때문에, 다익스트라 알고리즘을 최소로 돌리려면 각각 시작점/도착점을 시작으로 해서 최단 거리 리스트를 구한 뒤 조건에 따라 노드를 구하자.

공항이전에 파이썬으로 find 함수를 응용해 풀었던 문제다. find를 풀기 전에 visited 체크로 풀어보기도 했는데, 스위프트에서도 아니나 다를까 70% 정도에서 시간초과가 났다.

주간 미팅다익스트라 알고리즘을 적게 돌리는 방법은 공통되는 지점을 시작점으로 사용하는 법. (본 문제에서는 장소마다가 아니라 도착점을 시작점으로 사용해 총 두 번만 돌리면 된다)

징검다리 달리기 2좌표를 통해 간선을 시간 초과가 나지 않도록 넣는 게 가장 큰 이슈인 문제. 간선만 넣었다면 다익스트라를 통해 꺼내자.

쉬운 최단거리다익스트라처럼 푼 BFS 문제.

야쿠르트 아줌마 야쿠르트 주세요다익스트라를 통해 문제에서 이동한 거리를 누적해서 구하고, 이 누적값보다 현재 내가 있는 정점 buy_start로부터의 최단 거리 my_distance 값이 이하일 때 야쿠르트를 살 수 있다.

아름다운 문자열원본 문자의 순서대로 타겟 문자를 반복, 타겟 문자의 순서대로 커지는 조건으로 개수를 카운트할 수 있다. 타겟 문자가 들어 있는 개수는 마지막 타겟 문자 인덱스의 개수다.

저울누적 합의 성질을 생각해보는 문제. 분류는 그리디/정렬이었는데, 그리디 알고리즘을 푸는 방향보다는 수의 성질을 예시를 통해 접근하면서 귀납적으로 풀었던 문제였다. 이전에 파이썬으로 풀었던 경험이 있었기도 하고.

두 단계 최단 경로 1노드1에서 출발, 노드2를 경유해 노드3에 도착하는 최단 경로는 노드1 기준 다익스트라 알고리즘으로 구한 최단 거리 중 노드2까지의 거리 + 노드2 기준 다익스트라 알고리즘으로 구한 최단 거리 중 노드3까지의 거리이다. 분할해서 생각하자.

오픈채팅방문자열 입력을 배열/딕셔너리에 기록하면서 유저 아이디에 해당하는 닉네임이 마지막으로 반영된 값을 유지하는 게 관건. 리턴하는 문자열에는 Change가 반영이 되지 않는다는 데 주의.

아이템 제작다익스트라 알고리즘의 원리를 이용, 특정 노드로 갈 수 있는 비용이 업데이트되면 그 노드를 사용(경유)하는 다른 모든 노드에서도 업데이트되도록 한다. 이때 다익스트라 알고리즘 이전에서 거리 비용을 만들었는데, 여기에서는 문제 상황에서 곧바로 비용이 주어지므로

1. 문제 설명 >택배 2. 문제 분석 > 그리디 알고리즘 문제. 파이썬으로 풀었던 문제를 복습할 겸 스위프트로 풀어보았다. 현재 시점에서 사용 가능한 로컬 최댓값을 계산하는 게 관건인 문제. 헷갈리기 쉬우니 주의. 3. 나의 풀이

1. 문제 설명 >소수 경로 2. 문제 분석 > 에라토스테네스의 체를 통해 네 자리의 소수를 모두 구해놓자. 입력 소수를 각 자리를 변경해 BFS를 시도하면서 목적 소수가 될 때 횟수를 카운트한 값을 그대로 리턴할 수 있다. 이때 자릿값을 바꿔주는 것은 정수가 아니라

MST 게임크루스칼 알고리즘을 통해 MST를 구했다. parents 변수를 한 번 반복할 때마다 초기화시켜주면서 카운트. 코스트를 인덱스로 사용하는 것 역시 문제를 풀기 위한 기본 조건이다.

유럽여행MST를 구할 때 우선순위 큐에 들어가는 비용을 '왕복' 간선 및 두 노드의 입국 비용을 합해 구성하는 것을 떠올리는 게 가장 큰 관건인 문제다. 이를 통해 간선을 구성한다면 이후는 일반적인 MST를 구하는 문제.

문자열 압축문자열을 배열로 변환해서 풀면 (적어도 스위프트에서는) 접근하기 보다 편리해진다. 인덱스에 접근하기 전 카운트를 통해 조건을 제어하자.

기능개발현재 진도율에 따라 배포 가능 여부를 판단할 수 있다. 앞에서부터 접근, 배포 가능한 최대 지점까지를 카운트한 뒤 남아 있는 기능 정보를 업데이트하자.

두 단계 최단 경로 2특정 노드를 경유하는 최단 경로는 도착지와 목적지에서 각각 돌린 다익스트라 알고리즘으로 구한 최단 경로 배열에서 그 노드를 사용하는 거리 두 개의 합이다.

물대기MST를 풀 때 그래프를 연결하는 가상의 노드를 만드는 게 문제를 풀 때 매우 편리한 경우가 있다.

변신로봇주어진 입력값을 바탕으로 간선 비용을 만들어내는 게 주요 관건.

떡 돌리기처음에는 한 번에 떡을 한 개만 들고 간다는 조건이 아니라 여러 개의 떡을 들고갈 수 있을 줄 알았기 때문에 note라는 배열에 특정 노드에 대한 경로를 기록해서 왕복 가능한 거리까지 카운트, 그 거리 안에서 추가로 이동 가능한 노드까지의 거리를 계산했다. 하

우주신과의 교감간선 비용을 좌푯값을 통해 직접 계산하는 문제. 입력된 순서를 그대로 노드 번호로 사용하자. 이미 연결된 간선은 비용이 0으로 간주, 우선순위 큐에 넣으면 자동으로 맨 앞에서 출력된다.

Fix WiringMST는 주어진 모든 간선 비용 페어 중 노드 개수 - 1개만큼을 최솟값을 구해 더하면 된다. 이렇게 정렬된 비용 리스트를 통해 특정 노드 페어에서 최소 스패닝 트리를 구했을 때 그 값이 최대한 경우 역시 구할 수 있다(바로 옆에 있을 때에만 연결시킬

욕심쟁이 판다DP + DFS(재귀) 통해 특정 노드에서 출발했을 때 이동 가능하다면 dp를 통해 전역으로 이동 카운트 기록

이분 그래프DFS를 통해 이분 그래프를 점검할 수 있다. 재귀적으로 접근했기 때문에 파이썬의 재귀 제한을 풀었고, pypy가 아니라 python3로 제출했다. 전역 변수 플래그를 통해 곧바로 이분 그래프가 아닐 경우를 체크하는 게 핵심.모든 그래프(연결이 보장되지 않은

빙산BFS를 통해 들어오는 위치에서 (현 시점의) 인접 물 개수를 카운트, 감산해주면서 연결된 모든 빙하를 녹이는 과정을 반복한다. 이때 중요한 것은 visited를 사용해 연결되어 있지 않은 빙하가 발견될 때 이를 곧바로 체크하는 점이다.메인에서 flag를 확인하니

줄 세우기그리디는 처음에 접근법에 대한 감을 잘 못 잡으면 풀기 어렵다.

이분 그래프이분 그래프 문제를 파이썬으로 푼 뒤 스위프트로 옮겨 보았다.

지진MST를 통해 주어진 기준에 따라 가장 높은 이득을 얻어내는 값을 구한다. 이때 모든 경우를 탐색하는 게 아니라 이분 탐색을 통해 탐색 경우를 줄일 수 있다.주어진 간선 복구 비용 및 시간이 주어진다. 시간 당 이득을 gain이라고 하면 간선을 (간선 복구 비용)

부분 문자열KMP 문제로 "들어 있는지"를 판단하는 문제. LPS와 KMP solver를 통해 O(N+M) 안에 찾을 수 있다. 원본, 타깃 문자열 길이만큼이기 때문에 무리 없다.

찾기KMP를 통해 패턴의 인덱스 위치를 기록하자.

나는 친구가 적다원본 문자열을 가공한 새로운 문자열(숫자가 없는 버전)을 만들 때 처음에는 for문으로 letter.isdigit() 혹은 letter.isalpha()로 확인했는데, 시간 초과가 났다. 이후 리스트 컴프리헨션 방식으로 변경 이후 KMP 알고리즘을 사용

게임다음 이동 장소가 위험한/죽음의 영역 중 어디에 있는지를 일일이 for 문을 통해 확인할 수 있다. 죽음의 영역이라면 갈 수 없고, 위험한 영역일 때에는 비용이 1 추가 된다. 다익스트라 알고리즘을 통해 '다음 영역'으로 갈 수 있는 최단 거리를 구하자. "현재 어

엔터프라이즈호 탈출다익스트라를 통해 시작 위치("E")에서 다른 모든 노드에 대한 최단 거리를 구할 수 있다. 최단 거리 배열에서 가장자리 위치의 최솟값이 곧 탈출할 수 있는 가장 짧은 거리다. 처음에는 모든 가장자리 값을 비교한 뒤 최속값을 리턴했는데, 파이썬 언어에

부분 문자열KMP를 통해 부분 문자열 존재 여부를 확인할 때 곧바로 리턴했다.

찾기KMP를 통해 부분 문자열을 찾았을 때 해당 원본 문자열 인덱스에서 타겟 문자열의 길이를 뺀 값을 통해 일치하는 패턴이 시작하는 위치를 기록할 수 있다.

공통 부분 문자열이차원 배열을 통해 공통 문자열이 같다면 이전에 나온 값보다 +1을 해주자. 전체 배열에 기록된 값 중 최댓값이 공통 부분 문자열 중 최장 문자열의 길이다.

LCS 3공통 부분 문자열에서 사용했던 기법을 통해 비교한다. 이번에 비교할 문자열은 총 세 개이므로 삼차원 배열을 만들어 DP에 기록, 최댓값을 업데이트했다.

LCS 2LCS의 길이를 구할 때 문자열 자체도 배열에 기록할 수 있다.

괄호 제거스택을 통해 괄호쌍의 위치를 구할 수 있다. 각 괄호쌍을 놔둘지 없앨지 조합을 통해 카운트(모든 괄호를 건드리지 않는 조건은 제외)할 수 있다. 이를 통해 새로운 식을 만들어내어 사전식으로 정렬하자. 도출된 식이 중복 가능하므로 집합을 통해 체크.

타켓 넘버BFS를 통해 가능한 모든 수를 체크, 마지막 수까지 조합(+/-)한 결과가 타겟 넘버와 동일하다면 개수를 카운트.

멀쩡한 사각형직각 삼각형의 빗변이 전체 사각형과 마주칠 수 있는 최대의 경우를 먼저 뺀다. 이후 공통적인 부분은 다시 더해주는 게 포인트.빗변이 마주치는 최대의 경우는 위쪽으로 카운트할 때 w, 옆쪽으로 카운트할 때 w. 이중 공통되는 부분은 최대공약수라는 뜻. 사실

줄 세우기원래 있어야 하는 인덱스를 정렬되지 않은 값에 기록, 인접한 수(아이들의 키)가 정렬되어 있다면 그럴 필요 없다.

풍선 맞추기"해당 높이"에 해당하는 화살의 개수를 파악하기 위해 arrows라는 배열을 생성, 화살 존재 유무를 확인하자. 화살이 없다면 화살을 쏘고 풍선을 맞고 높이가 1 감소한 화살을 다시 한 번 기록하자. 화살이 있다면 맞춘 뒤 다시 높이가 1 감소한 화살을 다시

탈옥다익스트라를 3번 돌릴 때 원활하게 풀리는 문제다. '외부인'과 연결된다는 가정이 다른 다익스트라 알고리즘 문제를 풀 때에도 매우 유용한데, 이번 문제는 행렬로 주어졌기 때문에 주어진 문제 그래프를 감싸는 새로운 2개의 행/열을 추가해주는 게 관건이었다.

There is No Alternative원본 그래프의 MST를 구성하는 간선 정보 및 비용을 리턴받을 수 있다. MST 구성 간선을 반복문을 통해 간선 정보를 꺼내서, 이 간선 정보를 기존 그래프에서 제거한 새로운 그래프를 만들자. 이 새로운 그래프를 통해 구한 MS

Jungle Roads전형적인 MST 풀이

Underground Cables좌표값을 계산한 뒤 이를 통해 각 노드 간의 비용을 구하고, MST를 만든다.

판게아 1MST를 간선이 추가될 때마다 구해야 하는 문제. 우선순위 큐를 사용한다면 기존 pq를 구할 때마다 정렬을 할 필요가 없기 때문에 시간적으로 더 수월할 것. 스위프트에서는 우선순위 큐를 구현해야 했기 때문에 기본 정렬로 먼저 도전했는데, 통과가 되었다.

Moocast간선을 좌표 계산을 통해 직접 입력해 푸는 MST 문제. 특징은 MST 전체 비용이 아니라 MST 구성 간선 중 가장 큰 값을 리턴하는 것.

횡단보도두 노드를 연걸하는 비용은 주기를 계산해 얻어낼 수 있다. 이때 유의할 점은 이동 가능한 다음 주기는 현재 시간보다 값이 커야 한다는 점이다. 모듈러 연산자를 통해 주기를 카운트해 이동 시간 1을 포함해 다익스트라 알고리즘을 사용하자.

배무게 제한과 무게를 입력받고, 내림차순으로 정렬하자. 가장 제한이 큰 배보다 무게가 크다면 애초에 싣지 못하는 짐이다. 현재 시점의 무게 제한은 "가장 큰" 배이므로, 1분에 N개의 크레인을 써서 앞에서부터 실어나가자.

거리두기 확인하기행렬 그래프를 BFS를 통해 탐색, 특정 노드까지 걸리는 최소 거리 값을 얻어낼 수 있다. 모든 사람 (값이 P)을 시작 노드로 설정한 BFS를 돌리자. 한 번이라도 맨해튼 거리가 2 이하인 다른 사람과 만난다면 거리두기를 지키지 않은 것이므로 그 시점

트리의 지름BFS를 통해 주어진 트리 그래프 내 시작 노드에서 가장 길이가 먼 (가중치 누적합이 가장 큰) 노드를 리턴할 수 있다. 이를 이용해 트리의 '지름'을 파악하자. 루트 노드로부터 시작해 1). 루트에서 가장 떨어진 노드가 무엇인지 리턴하자. 2). 이 노드에

산책다익스트라를 두 번 사용해서 특정 노드 간의 경로 중 첫 번째 최단 경로에 사용된 노드를 제외한 새로운 최단 거리를 구할 수 있다. 이때 주의해야 하는 점은 s ~ e의 이동 시에 먼저 선택되는 최단 경로가 알파벳 순서이기 때문에, 같은 거리라도 이 과정에 따라 두

튜플(https://programmers.co.kr/learn/courses/30/lessons/64065?language=swift문자열을 다루는 문제. {, ,, } 등 괄호 및 콤마를 통해 구별 가능한 집합을 배열로 만들어 이차원 배열 속에 저장하고, 원

트리의 지름이전에 풀었던 문제와 동일한 지름을 구하는 문제. 루트에서 시작해서 가장 거리가 긴 노드를 리턴하고, 그 노드에서 가장 거리가 긴 노드까지 걸리는 비용이 곧 트리 전체의 지름이다.

간선 끊어가기처음에는 s-t의 연결 여부를 확인하면서 MST를 구할 생각이었는데, 계속해서 실패가 나왔다... 결과적으로 포스팅을 보고 공부했다.네트워크 플로우 문제로 s에서 t로 연결되는 유량의 최댓값/최솟값을 구하는 문제라 한다.'최댓값'을 리턴할 때 전체에서 '최

수 정렬하기 2수를 입력받고 정렬한 뒤 출력하기

다리 놓기조합 문제

게임 맵 최단거리일반적인 BFS 문제.

섬 연결하기일반적인 MST 풀이 문제

잃어버린 괄호마이너스 기준으로 카운트해야 한다. 마이너스가 나왔는지 불리언 값으로 체크, 최댓값까지 모아서 전체 값에 반영하자

벽 부수고 이동하기방문 체크용 배열을 3차원으로 만들어서 확인했다. 아직 미방문(값이 0인지 여부로 체크)했고 다음 노드가 0일 때 이동 가능 / 다음 노드가 1이고 아직 벽을 부순 적이 없을 때 이동 가능

Bad CowtractorsMaximum Spanning Tree

소트인사이드문자열 캐스팅 후 정렬, 그대로 숫자로 만들어서 리턴

한수세 자리 수 이상 수를 각 자리수 배열을 만들어서 특정한 수가 등차로 반복된다면 한수다.

피보나치 수 2dp를 통해 피보나치 수 파악. 기본부터 다시!

가장 긴 증가하는 부분 수열dp를 통해 "가장 큰" 수 자리 인덱스를 고정, 이 수보다 작은 수를 앞 인덱스에서부터 검사하면서 가장 큰 합이 되는 지점을 dp에 기록한다.

가장 긴 감소하는 부분 수열가장 긴 증가하는 부분 수열 문제에서 조건을 '작을 때'로 변경, 총합 대신 길이를 카운트하는 문제

가장 긴 증가하는 부분 수열 4가장 긴 증가한느 부분 수열을 통해 길이를 카운트, dp에 해당 dp의 길이를 기록하자. 거꾸로 거슬러 올라가면 스택에 해당 dp에 처음 나온 인덱스를 numbers에서 꺼내 기록한다.

날짜 계산브루트 포스로 E, S, M을 계산한다.

GCD 합조합으로 페어를 구한 뒤, 각 GCD의 총합을 구하는 문제.

토너먼트현재 라운드 경기 수 n의 홀짝 여부에 따라서 경기 순서가 달라진다. get_round 함수를 통해 이를 체크, 같은 라운드에 경기할 경우 플래그 비트를 참으로 변경, 반복문을 탈출한다.

부등호순열로 풀었더니 메모리 초과가 났다. check라는 불리언 배열을 통해 백트래킹으로 0~9까지의 수의 순열을 재귀적으로 만들어서 접근했다.

로또백트래킹 문제다. 조합을 백트래킹으로 푸는 방법은 check 불리언 값 참/거짓 변경과 함께 현재 어떤 인덱스까지 체크했는지 재귀 파라미터로 넘겨주는 것.

연산자 끼워넣기 (2)백트래킹 문제다. 기존의 연산자 끼워넣기보다 연산자 개수가 늘어났기 때문에 백트래킹 횟수로 인해 시간 초과가 나지 않도록 주의하자.

N과 M (12)백트래킹을 통해 중복 조합을 푸는 문제다.

N과 M (6)백트래킹을 통해 조합을 구하는 문제다.

N과 M (7)백트래킹을 통해 순열을 구하는 문제다.

N과 M (9)백트래킹을 통해 순열을 구하는 문제다. 이때 구해지는 순열에 중복 체크를 하자.

N과 M (11)중복 순열을 뽑는 방법.

N과 M (10)중복을 허용하지 않는 조합

에너지 모으기제거한 에너지 위치를 check로 비트 조정, 백트래킹한다.

1, 2, 3 더하기 2특정 수 합이 n이 될 때까지 백트래킹을 하면서 수 조합을 집합으로 기록하자.

근손실백트래킹을 통해 키트의 모든 조합에 대한 중량을 체크, 마지막 날까지 중량 조건이 500 이상이라면 가산한다.

크면서 작은 수정수 배열이 아니라 문자열 배열을 통해 쉽게 join 및 비교 가능하도록 구현.

스도쿠백트래킹 문제. 백트래킹 자체보다 유효 숫자를 판별하는 로직에서 시간 초과가 계속 났기 때문에 집합으로 바꿔주고, 중복 숫자를 해결했다.

스도쿠지난 번 스도쿠 문제와 동일. 유효 숫자를 정렬해서 주었기 때문에 먼저 출력되는 스도쿠는 가장 빠른 순서의 스도쿠다.

순열순열 문제. 백트래킹으로 풀 수 있는데, 마지막 입력값이 없을 때까지 제어하는 게 더 어려웠다.

촌수계산BFS로 푸는 문제. 이차원 배열을 통해 그래프를 구현한다.

영재의 시험시간 초과를 방지하기 위해 플래그 비트를 주었다. 마지막 두 번호의 값만 가지고 있고, 연속된 경우 플래그 비트를 참으로, 선택한 번호의 답과 마지막 경우가 같다면 패스한다.

제곱수의 합특정 수를 제곱했을 때 바로 그 수가 나온다면 (즉 2-4, 3-9...) 제곱수로 표현 가능한 개수는 1개로 최소다. 그렇지 않다면 현재 수 i에서 i보다 작은 게 보장된 수들의 제곱수를 뺀 dp에 기록된 값 + 1 중 최솟값이 가장 적은 개수로 표현된 제

꿀 따기벌 두 마리와 꿀통이 놓일 수 있는 경우의 수는 총 세 가지다. 꿀통을 향해 날아갈 때까지 꿀을 모을 수 있기 때문에 특정 경우 "가장 많이 모을 수 있는" 수는 정해져 있다. 이때 관건은 "겹치는" 자리가 어디인지 확인하는 것이다. 누적 합을 미리 구해놓은 뒤

보물최솟값을 구하기 위해서는 배열 1의 최솟(최댓)값과 배열 2의 최댓(최솟)값을 각각 곱해야 한다.

설탕 배달현 시점의 설탕이 5의 배수가 아니라면 3을 하나씩 빼보자.

주유소현재 시점에서 가장 저렴한 기름을 정한 뒤, 다음 도시로 가면서 해당 거리에 필요한 기름값을 계속해서 추가하자.

1. 문제 설명 >나무 자르기 2. 문제 분석 > 이분 탐색 문제. 기준이 되는 높이를 중간값으로 선정한 뒤 이 높이로 나무를 잘랐을 때 가져갈 수 있는 총 길이 total과 목표 길이 M을 비교하자. M 이상을 만족한다면 이 높이 mid를 자르는 게 허용되고, 이

특정 거리의 문제 찾기전형적인 다익스트라 문제. 단방향 그래프를 그리자.

악덕 영주 혜유MST를 구하면서 해당 문제의 트리 그래프를 구할 수 있다. 트리가 존재한다면 각 트리를 구성하는 '지름'을 BFS를 두 번 사용해 구할 수 있다. MST가 보장이 되기 때문에 0번 노드로부터 시작되는 노드 중 가장 길이가 긴 노드를 구할 수 있다. 이

ATM해당 사람 별 기다리는 시간 순서대로 오름차순 정렬을 한다. 각 개인이 기다리는 시간을 누적합을 통해 구하고, 그 누적합의 총계가 곧 total.

듣보잡집합을 통해 중복 이름을 체크

좌표 압축해당 좌표 배열을 집합화 -> 오름차순 정렬하자. 이 인덱스 순위가 곧 자신이 주어진 좌표들 가운데 몇 번째인지다. 딕셔너리에 기록한 뒤, 프린트하자.

색종이 만들기DFS를 통해 최소 조건에 다다를 때까지 4분할 탐색을 시도하자.

MooTube

소가 길을 건너간 이유 6BFS를 모든 노드별로 돌려서 다른 노드와 만날 수 있는 여부를 확인하는 문제다. 문제 이해(길의 사용 방법)로 인해 애를 먹었다. 딕셔너리를 통해 특정 노드-노드 간 길의 유무를 빠른 속도로 할 수 있다.

소가 길을 건너 간 이유 8DP를 통해 현재 왼쪽-오른쪽 소를 연결하는 지점까지 가장 많은 수의 횡단보도를 기록하자. 횡단보도를 만들 수 있는 기준은 주어진 값의 해당 인덱스 값의 차가 4 이하일 경우다.

개미개미 순서를 하나의 배열로 만든 뒤, 개미 집단을 집합을 통해 관리하자. 맞닿아 있는 인덱스의 개미들이 서로 다른 집단이라면 이동해야 한다.

이동하기BFS를 통해 이동 가능한 방향으로 이동하면서 dp를 통해 최댓값을 기록하자. 이때 모든 곳을 방문해보되, 여려 번 방문하는 경우만 조건문을 통해 인큐한다.

돌 게임 2dp를 통해 1, 3개를 뺀 경우가 누가 이겼는지 간단하게 기록할 수 있다.

그리드 네트워크파이썬으로는 부분 성공까지밖에 하지 못했던 문제. 동일한 로직으로 스위프트로는 성공.기본적으로는 MST. MST를 계산할 때 받아들이는 노드 및 비용을 받아들이는 방법만 유의하자. 서로 '다른' 노드인지 체크!

파티다익스트라를 풀기 위한 우선순위 큐 구현이 가장 힘든 문제. 힙만을 쓸 일은 딱히 없으므로 시간 문제 상 곧바로 우선순위 큐 구현에 들어가자!

탈옥우선순위 큐 구현 → 논리적 연결점(즉 주어진 그래프를 둘러싼 네 가지 벽 → 새로운 그래프) 체크 → 다익스트라를 통한 최솟값 체크우선순위 큐를 손에 익히자.다익스트라를 여러 번 돌릴 때 답이 나온다면, (0, 0) 등 문제 상에는 주어지지 않았지만 논리적으로 주

1. 문제 설명 >특정한 최단 경로 2. 문제 분석 > 3. 나의 풀이

도로포장우선순위 큐를 통해 다익스트라 문제를 풀 때에는 일반적인 케이스뿐만 아니라 dp 역시 적용 가능하다. 현재 시점에서 포장 도로를 깔아 무료로 이동이 가능할 때 포장 도로의 개수 역시 dp의 한 차원으로 넣고 우선순위 큐에도 함께 넣을 수 있다.

국왕의 방문다익스트라 알고리즘을 구현할 때 현재 시점의 국왕이 어디에 있는지를 확인해야 한다. intersectionData를 통해 특정 시간을 입력값으로 넣을 때 현 노드 ~ 다음 노드, 머무르는 시간을 리턴하는 함수를 구현했다. 이를 통해 현 시점의 다익스트라 알고

A와 B 2재귀를 통해 푸는 문제. 거꾸로 접근해야 한다.

동일한 단어 그룹화하기집합을 통해 중복 체크

구간 합 구하기 4구간 합을 미리 구해두고 인덱싱을 통해 특정 부분만의 구간 합을 얻어내자

합 구하기구간 합 구하기

다트 게임딕셔너리를 활용해 빠른 속도로 풀 수 있다. IDE 없이 하려면 여전히 잔오류가 많으니... 손에 익히자!

뉴스 클러스터링역시 딕셔너리. 해시를 애용하자!

프린터딕셔너리를 통해 현재 우선순위 종류 및 개수를 카운트하자. while 반복문을 통해 현재 인쇄하고자 하는 출력물의 위치 정보를 계속해서 갱신한다.

캐시집합을 통해 캐시를, LRU로 캐시 미스 경우 삭제할 캐시를 리스트 형식의 큐로 관리했다. 힙, 큐 등 일반 리스트가 아닌 자료구조를 사용할 때 LRU로 "가장 최신" 사용한 원소를 맨 뒤로, "삭제할 수 있는" 원소를 맨 앞으로 자동으로 오게 할 수 있을 것 같다

그룹 단어 체커딕셔너리로 풀었다.

단어 뒤집기개인적으로 문자열은 배열로 만든 뒤 다루는 게 편하다.

단어 뒤집기 2스택과 플래그, 배열을 통해 해결했다. 문자열에는 스택!

짝지어 제거하기스택을 통해 푸는 문자. String 형변환보다 있는 그대로의 Character 접근이 시간 소모가 적다.

메뉴 리뉴얼조합은 DFS로, 개수 카운트는 딕셔너리를 사용했다.

피로도던전을 도는 순서에 따라서 최대 방문 횟수가 달라지기 때문에 DFS를 통해 순열을 돌면서 현재 피로도를 기반으로 방문 횟수를 카운트한다. 최댓값을 기록해 리턴.

모음사전중복을 허용하는 순열을 DFS로 돌려서 다섯 개의 알파벳으로 가능한 모든 단어를 카운트를 통해 순서를 체크, 딕셔너리에 모두 기록했다. 이를 통해 주어진 단어가 해당 사전에 몇 번째에 기록되어 있는지 바로 해쉬했다. 사전 앞 부분에 나와 있는, 즉 DFS에서 조

괄호 변환재귀에 의한 문제 풀이. solution이라는 함수 자체도 재귀적으로 호출할 수 있다는 점을 유의하자.

H-Index정렬 뒤 현재 가능한 h를 변수로 넣고 가능한지 체크.

올바른 괄호스택을 통해 효율적으로 풀 수 있다.

가장 먼 노드BFS를 통해 현재 도달한 노드가 리프 노드인지 확인할 수 있다. 리프 노드라면 시작 노드에서 거슬러 온 노드의 개수가 곧 그 리프 노드에 대한 키가 된다. 키의 값을 +1 해주자. BFS 방문이 모두 끝났을 때 딕셔너리의 키 값 중 최댓값에 해당하는 값이

네트워크연결 그래프를 구한 뒤, 특정 노드에서 BFS를 돌리면서 방문한 노드를 전체 노드에서 하나씩 제거해 나간다. 모든 노드를 방문할 때까지 (시작 노드를 갱신하면서) 방문하자. 이때 BFS를 사용한 횟수가 곧 네트워크의 개수다.

합승 택시 요금플로이드-워셜 알고리즘을 통해 모든 노드에서 다른 모든 노드에 대한 최단 거리를 찾는다. 이를 통해 s에서 a, b를 들를 때 도착하는 최솟값을 알 수 있다. 즉 출발지인 s는 고정, x까지 함께 갔을 때 a, b에 도착하는 값을 합했을 때 최소인지 구할

양과 늑대DFS를 통해 재귀적으로 백트래킹하는 문제. 중복 방문이 가능하기 때문에 현재 양/늑대의 개수를 파라미터로 전달하면서 최댓값을 갱신한다. 이때 방문하지 않은 상태의 자식 노드가 양인지 늑대인지 info를 통해 확인, 다음 DFS에 넘길 파라미터를 맞춰준다. 이

순위연결 그래프를 만든 뒤, 부모-자식, 자식-노드으로 연결되는 노드의 개수가 주어진 노드의 개수와 동일하다면 (자신을 제외하고) 다른 모든 그래프와 비교, 순위를 얻어낼 수 있다는 뜻이다.

단어 변환문자열 인덱스를 잘 다루는 방법을 하나 배웠다!

경주로 건설dp를 3차원 배열로 구현, 해당 위치 + 현재 방향까지 모두 정보를 가지고 있자. 도착 노드에 위치했을 때 네 가지 방향 중 최솟값이 곧 답이다.

N으로 표현DP를 통해 숫자 N을 count개를 만들 수 있는 수를 두 개로 분할해서 생각해본다. count = 1 + count -1 / 2 + count - 2 ... / 이기 때문이다.

파괴되지 않은 건물누적합을 통해 $O(NM)$을 $O(K+N+M)$으로 줄일 수 있다.누적합 시 끝 인덱스에 더해주는 값의 반대 값을 누적하는 것을 잊지 말자.역시 카카오. 문제 깔끔하면서 어렵다. 생각의 발상, 아이디어를 간직하자!

소수 찾기주어진 숫자를 통해 만들 수 있는 모든 수들을 순열로 만드는데 DFS를 사용하자. 유효한 숫자를 가져왔다면, 해당 수가 소수인지 판별하고 그 개수를 카운트.

영어 끝말잇기문자열 집합을 통해 나왔던 단어인지 확인하고, 지난 단어의 마지막 캐릭터를 이번 단어의 첫 번째 캐릭터와 일치하는지 체크하며 끝말잇기 여부를 확인하자. 딕셔너리를 통해 특정 인물의 몇 번째 차례인지 확인할 수 있는데, 배열로 해도 충분할 것 같다.

위장옷 종류 별 개수를 카운트한 뒤, 가능한 조합의 개수를 고르자. 각 타입의 옷을 안 입을 수도, 모두 입을 수도 있기 때문에 (n+1)을 곱해주었고, 마지막에 모든 옷을 입지 않는 경우의 수 하나를 빼주었다.

베스트앨범딕셔너리를 통해 해시했고, reduce, map 등 고차 함수를 통해 정렬 시 필요한 정보를 캐치했다. 고차 함수를 연습해보는 파트.

여행경로연결 그래프를 만들고, 해당 간선을 모두 사용하는 경로 중 특정한 하나(가장 알파벳 순서대로 정렬된 경로)를 리턴하는 문제다. 문자열 형식의 티켓이기 때문에 해시 가능하도록 딕셔너리로 정리했고, 중복 티켓을 대비해서 각 티켓의 인덱스 값을 정수 배열로 간직하는

입국심사이분 탐색을 통해 심사관이 심사 가능한 최대 사람의 수를 구할 수 있다. 입국 심사가 가능한 가장 작은 시간을 찾자.총 시간 middle을 최솟값 0 ~ 최댓값 (가장 시간이 많이 드는 입국 심사 시간 \* 전체 사람의 수)을 사용해 구할 수 있다. 심사관 한

다단계 칫솔 판매BFS를 통해 루트 노드까지 이어질 연결 그래프를 만들고, 상납이 가능한 만큼 거슬러 올라가면서 해당 노드가 벌어들이는 돈을 가산하자.

추석 트래픽응답 완료 시간 및 작업 시간을 밀리 초 단위로 환산한 레코드를 만든 뒤, 해당 레코드 내 시작/끝 시간의 간격이 전체 레코드 상에서 겹치는 가장 많은 부분을 카운트했다.문자열 파싱 이후 특정한 숫자로 조작하는 데 익숙해져야 한다. 실수 단위라면 정수 단위로

셔틀버스문자열 파싱을 통해 시간을 정수로 만든 뒤 대기열에 도착하는 순서대로 정렬하자. 버스 시간표에 따라 아무런 이상이 없을 경우 버스에 타게 되는 순서를 배열을 통해 카운트, "마지막 버스"에 타게 될 경우를 얻어낼 수 있다. 마지막 버스에 자리가 남았다면 버스 도

불량 사용자가능한 조합을 숫자를 통해 표시, DFS로 백트래킹했다. 조합을 적절히 응용해서 풀자.불법 사용자 아이디를 통해 가능성이 있는 유저 아이디를 원소로 하는 이차원 배열을 만들자.중복 아이디가 없기 때문에 동일한 아이디는 서로 다른 불법 사용자 아이디가 될 수

신고 결과 받기첫 번째 방법은 중복 방지를 위해 배열에서 contains로 계속해서 확인해주었다. 시간 초과는 나지 않았지만, 생각보다 비효율적이라는 생각이 들어 1. 이름을 키 값으로 한 배열 인덱스를 리턴하는 딕셔너리를 생성, 2. 해당 인덱스로 접근 가능한 집합

신규 아이디 추천문자열을 조건에 따라 필터링하는 게 문제 풀이의 관건. 다소 까다로운 스위프트 문자열은 인덱스를 통해 접근하는데, 나 같은 경우 문자열 배열로 전환해서 대부분 해결한다. 물론 캐릭터 자체가 시간적인 측면에서 보다 효율적이긴 한데, 시간 초과가 나지 않는

숫자 문자열과 영단어딕셔너리 해시 성공 및 실패를 통해 제대로 된 숫자가 들어 왔는지 확인했다. DFS 재귀를 통해 시작 인덱스 ~ 끝 인덱스로 만들어지는 영단어가 해시 키로 사용되었고, 특히 한 글자인 경우에는 먼저 알파벳이 아니라 숫자인지 체크했다.

모의고사스위프트의 고차 함수 filter, map을 활용해 보았다.

크레인 인형뽑기 게임스택을 통해 현재 들어오는 인형의 종류와 가장 윗단에 존재하는 인형을 비교할 수 있다.

K번째 수부분 배열을 만들어서 정렬하는 간단한 문제

비밀지도10진수를 2진수로 변환하고, 문자열 인덱스를 통해 비교하면서 이차원 배열을 수정했다. 최종 결과를 위해 이차원 배열을 일차원 배열로 매핑했다.속도를 위해 문자열 인덱스를 사용해 보았다.

키패드 누르기딕셔너리를 통해 특정 패드의 위치를 알아냈다.

실패율총 사람의 수는 특정 스테이지를 건널 수록 저번 차례의 사람의 수를 빼야 한다.

양궁대회DFS를 통해 현재 쏠 수 있는 화살의 수를 카운트, 마지막 과녁까지 쐈을 때 라이언이 이겼고 로컬 최댓값보다 현재 점수 차가 클 때에만 라이언의 화살 정보를 업데이트했다. 이 경우 마지막에 차가 0이라면 비긴 것이므로 -1을 리턴하는 것에 주의하자.

스킬트리딕셔너리, 집합, 필터 고차 함수를 통해 쉽게 접근할 수 있었다.

로또의 최고 순위와 최저 순위교집합을 통해 현 시점의 변동치 않는 '맞은 개수'를, 0의 개수를 통해 최대 더 추가 가능한 '맞을 개수'를 얻어낼 수 있다.

성격 유형 검사하기딕셔너리를 통해 특정 성격의 검사 번호를 체크, 동의/비동의 기준에 따라 튜플 배열로 선언한 성격 검사지에 점수를 추가한다. 점수 추가가 종료된 이후에 순서대로 인덱싱을 하면서 해당 번호의 성격을 결정한다.

주차 요금 계산입차 및 출차를 체크하면서 특정 차 번호의 시간을 기록한다. 주차장을 사용한 시간이 각 차량 번호 별로 정해진 후, 전체적으로 요금을 계산한다.시간 문자열(시:분)을 정수 값으로 변환하는 함수특정 차 번호마다 총 주차 시간을 기록하는 딕셔너리입차는 들어온

1. 문제 설명 >프렌즈 4블록 2. 문제 분석 > 현재 상태의 없앨 수 있는 블록을 얻어내는 함수, 얻어낸 블록을 중복 처리하는 방법, 블록 처리 후 빈 공간을 없애는 함수를 반복한다. 주어진 배열을 2차원 배열로 만든 뒤, 2X2의 정사각형 블록을 스캔한다. 주어

방금그곡(https://school.programmers.co.kr/learn/courses/30/lessons/17683?language=swift타겟 음악 및 재생 음악의 음표 중 샵이 달린 음표를 소문자 알파벳으로 변환, 재생시간 중 재생되는 음표 내에

IOIOIIOI 반복 개수를 카운트, N개가 되면 전체 카운팅 1추가IOI가 현재 인덱스 ~ 인덱스 + 2 문자열이 맞다면 인덱스 += 2IOI가 아니라면 현재까지 N에 대한 카운트를 초기화, 인덱스 += 1

패션왕 신해빈가능한 조합의 개수 중 알몸인 경우를 빼면 된다. 일단 각 옷의 종류마다 각 종류별 입기 + 안 입기가 가능하기 때문에 곱을 통해 전체 조합의 개수를 구한 뒤, 모두 안 입는 경우 하나를 빼자.

1. 문제 설명 >베스트셀러 2. 문제 분석 > 딕셔너리 카운팅 + 정렬 및 필터링 3. 나의 풀이

압축주어진 문제 설명에 따라 문자열을 스캔하면서 현재 사전에 등록된 가장 긴 문자열이 무엇인지 찾는다. 이때 주의해야 할 점은 '등록된 문자열'이란 곧 현재 입력 문자열로 시작하는 문자 중 가장 긴 길이라는 점이다. 또한 현재 문자열에서 시작, 길이가 긴 문자열을 찾았

파일명 정렬(https://school.programmers.co.kr/learn/courses/30/lessons/17686?language=swift문자열 파일을 통해 파일 구조체를 생성한다. 이때 head, number, tail을 주어진 기준에 따라 분

k진수에서 소수 개수 구하기주어진 정수를 K진수로 변환한 뒤, 0을 기준으로 나눈다. 현재 구하려는 소수 P는 0을 가지고 있지 않고 0 주변을 둘러싸고 있는 소수로 표현되기 때문이다. 해당 수가 소수인지 판별하면 된다. 중복 소수까지 카운트하는 데 주의하자.문제의 핵

후보키DFS를 통한 후보 키 조합, 후보 키의 미니멀/유니크함을 판별하는 각 로직 두 개를 통해 풀 수 있는 문제다.가능한 후보 키 조합을 DFS를 통해 모았고, 조합에 들어간 칼럼의 인덱스 카운트를 오름차순으로 정렬해 처음부터 미니멀한 후보 키를 탐색하고자 했다. 후

n진수 게임가능한 수를 모두 구해놓고 말하는 순간의 인덱스만을 더한다.

보석 쇼핑투 포인터 문제. 딕셔너리를 통해 보석 종류를 카운팅, 보석 별 현재 포인터 범위 안에 해당 보석이 몇 개 있는지 파악할 수 있다. 최소 1개만 있으면 만족한다는 뜻이다. 만일 모든 보석 종류를 포함한다면, 줄일 수 있을 때까지 투 포인터의 범위를 줄인다. 줄

K번째 소수에라토스테네스의 체를 통해 풀었다.

소수&팰린드롬에라토스테네스의 체를 쓴 뒤 팰린드롬 체크를 했다.

소수의 자격에라토스테네스의 체를 통해 소수를 고르고, 인덱싱했다.

네 개의 소수네 개의 소수의 합을 통해 특정 수 N을 구한다. N이 짝수라면 4를 미리 빼주고 (2+2), 홀수라면 5를 미리 빼주자(2+3). 남은 수를 두 소수의 합으로 만들기 위해 에라토스테네스의 체와 조합을 사용했다.

소수의 연속합에라토스테네스의 체를 통해 주어진 수보다 작은 소수 배열을 구한다. 해당 소수 배열의 누적합을 구하고, 누적합을 통해 특정 구간의 합을 얻어낼 수 있다. 해당 구간의 합이 주어진 수와 같다면 곧바로 브레이크하면서 카운팅한다.

약수의 개수와 덧셈에라토스테네스의 체를 통해 특정 범위 내 소수를 특정한 뒤, 특정 수를 해당 소수를 사용해 소인수분해했다. 해당 약수의 개수는 소인수분해된 각 지수에 1씩 더한 값을 곱한 값이다.

두 개 뽑아서 더하기집합을 사용했다.

3진법 뒤집기십진법으로 된 일반 자연수를 특정 진수로 만들기. 특정 진법으로 쓴 수를 십진법으로 읽기.

예산정렬 뒤 그리디.

전력망을 둘로 나누기Union-Find를 통해 해당 노드의 루트 노드를 구하는 데, 특정 간선을 끊은 시점(즉 사용하지 않은 시점)마다 골라야 하기 때문에 간선의 개수만큼 Union-Find를 해야 한다. 이를 통해 해당 간선을 끊은 경우의 컴포넌트에 속하는 노드의 개

카펫가능한 행, 열을 통해 전체 노드의 개수를 카운트한다. 노드의 개수에서 바깥 테두리를 뺀 안 쪽 노란색 노드의 개수가 주어진 노란색 개수와 맞다면 성공.

피보나치 수dp를 통해 푼다.

최댓값과 최솟값정수화 후 최댓값, 최솟값 리턴

다음 큰 숫자String(number, radix:K)를 통해서 정수 number를 K진법으로 표현할 수 있다.

멀리 뛰기피보나치 DP와 상동

1. 문제 설명 >N개의 최소공배수 2. 문제 분석 > 최소공배수란 특정 두 수의 곱을 두 수의 최대공약수로 나눈 값이다. 불필요한 연산이 있었다. 주어진 수의 최댓값 이하의 모든 소수를 에라토스테네스의 체로 구한 뒤, 소인수분해를 하고, 소인수분해 결과값을 통해

JadenCase 문자열 만들기캐릭터를 하나씩 읽으면서 단어 별로 분할, 첫 번째 알파벳은 대문자로 나머지는 소문자로 넣었다. 공백이 반복될 수 있기 때문에 주의!

땅따먹기dp를 통해 풀었다. 파이썬으로 풀었을 때에는 BFS로 푼 것 같았는데...

등산코스 정하기다익스트라를 통해 출발지-산봉우리까지 가는 경로 중 비용의 최댓값을 기록한다. 다익스트라를 여러 번 돌리지 않고, 출발지로부터 시작하는 시작 노드를 우선순위 큐에 모두 넣은 채로 한 번만 돌린다.파이썬과 동일한 로직으로 푼 스위프트 풀이. 하지만 마지막

달팽이달팽이가 진행한 반대 방향으로 회전

KMP는 왜 KMP일까?맵과 조인으로 풀었다.

코딩 테스트 공부알고력, 코딩력을 통해 현재 풀 수 있는 문제에 드는 비용의 최솟값을 갱신해나가자. 알고력과 코딩력을 이중 반복문을 통해 하나씩 확인하면서 업데이트마다 모든 문제를 확인해야 한다는 게 시간 복잡도가 높아지는 이슈. 값 갱신이 일어날 때에만 이후 업데이트

감시 피하기그래프를 입력받으면서 백트래킹 가능한 빈 공간의 좌푯값을 미리 찾아두자. 3개 좌표의 값을 변경한 뒤 학생이 모두 숨을 수 있는지 확인하는 함수 isHidable()을 통해 확인하는데, 모든 경우를 찾아야하기 때문에 완전 탐색 + 브루트포스.

방문 길이중복 경로를 제거, 방문한 총 길이를 구하는 문제. Hashable 프로토콜을 사용하면 특정 구조체를 집합의 원소로 사용할 수 있기 때문에 경로(노드1-노드2, 노드2-노드1) 자체를 집합의 원소로 카운트했다.또 다른 방식으로는 2차원 불리언 변수 배열을 통해

기지국 설치현재 커서를 1에서부터 시작, 주어진 기지국이 커버하는 지점까지의 범위를 사용해 최소 몇 개의 기지국을 새로 설치해야 하는지 더해 나간다. 현재 커서가 위치하는 곳에 기지국의 범위가 존재한다면 기지국을 설치할 필요가 없고, 모든 기지국을 살펴본 뒤 나머지 뒷

가장 큰 정사각형 찾기이전 행/열 인덱스 값이 1일 때를 확인, 그 순간까지 얻을 수 있는 가장 긴 정사각형의 (가능한) 변 길이를 dp를 통해 기록해두고 전역 변수와 비교해가면서 답을 구한다.

호텔 방 배정유니온 파인드의 find 함수를 응용한다. 딕셔너리를 통해 해당 번호의 방에 접근 가능한지 체크, 그렇지 않다면 가능할 때까지 체크한다.

동굴 탐험양방향 그래프를 구현한 뒤 DFS를 통해 시작 노드인 0번 노드부터 출발한다. 정해진 순서에 적힌 노드를 만난다면 (before-after) 순서에 따라 행동한다. 이전에 방문할 노드가 있고 아직 방문하지 않았다면 현재 노드를 방문하기 전에 그 노드를 방문해야

지형 이동BFS를 여러 번 반복하면서 컴포넌트를 설정하고, 다른 컴포넌트와 만나는 지점에서 간선을 생성한다. 만든 간선을 가중치에 따라 오름차순 정렬하고 MST를 구하기 위해 크루스칼 알고리즘을 사용했다.

호텔 방 배정유니온 파인드를 새롭게 변형한 문제. 재귀적으로 접근했기 때문에 파이썬에서의 재귀 리미트를 설정해야 한다.

괄호 회전하기스택을 통해 올바른 형태의 괄호인지 체크 + 문자열 이동을 통해 새로운 문자열 생성

귤 고르기무게 별 귤의 개수를 딕셔너리를 통해 카운트한 뒤 내림차순으로 정렬하자. 즉 무게 별로 개수가 많은 순서대로 골라야 최대한 고르는 귤의 종류가 최소가 될 수 있다. enumberated를 통해 현 시점의 귤의 개수를 카운트했다.

명예의 전당 (1)원소 개수가 제한된 최소 힙을 통해 현 시점의 최소 점수를 O(N)에 손쉽게 얻어낼 수 있다. 참고로 실제로 코드 내 구현된 push 함수에 while을 통해 현재 큐 내 들어 있는 원소의 수가 limitedCount 이하일 때까지 반복해서 pop을

기사단원의 무기에라토스테네스의 체를 통해 특정 수 이하의 소수의 개수를 미리 구하자.특정 수의 약수의 개수는 즉 소인수분해를 한 뒤 각 인수에 1을 더한 값을 곱한 값주어진 조건에 따라 정답을 구한다.에라토스테네스의 체를 미리 구해 드는 시간을 줄여놓는다.

푸드 파이트 대회특정 인덱스의 음식 개수를 2로 나눈 값만큼 해당 인덱스를 놓는다. 왼쪽 사람이 먹을 순서를 정해둔 뒤, 물을 기점으로 거꾸로 답을 작성하자.

과일 장수주어진 과일을 점수 별로 정렬, 박스를 만들 수 있을 과일 개수만을 남기자. 박스 개수만큼 잘라가면서 해당 박스의 점수 p를 얻어내자.

햄버거 만들기스택을 통해 마지막에서 카운트한 음식의 종류가 햄버거를 만들 수 있는 것인지 체크하자. inout을 통해 들어온 정수 배열 자체의 값을 변경했다.

롤케이크 자르기왼쪽, 오른쪽에서 출발하는 각 누적합을 구한다. 형과 동생이 케이크를 자르는 단면 양 옆의 각 값이 동일할 때 카운트하자.

연속 부분 수열 합의 개수특정 인덱스부터 시작한 누적 합을 원소의 개수만큼 구하면서 집합으로 중복을 걸러주자.

할인 행사구매할 목록을 딕셔너리를 통해 관리한다. 10일 동안의 할인 품목 또한 딕셔너리로 관리해서, 후자에 전자 딕셔너리 값이 포함(값이 이상)이라면 구매 가능한 날짜로 볼 수 있다. 후자의 딕셔너리는 하루가 지날 때마다 가장 처음 앞 날의 물품은 빼주고, 다가올 날

삼총사DFS를 통해 조합을 구현했다. 더 이상 재귀가 돌지 않는 조건은 주어진 카운트가 3일 때.

옹알이 (2)이넘을 통해 말할 수 있는 단어 케이스를 지정, 연산 프로퍼티를 통해 각 단어로 생성되는 문자열 배열을 리턴이전 시점에 언급한 단어를 currentWord로 가지면서 주어진 단어를 모두 말할 때까지(즉 주어진 단어가 사라질 때까지) 반복. 스위프트에서 문자

숫자 짝꿍풀이는 간단하다. 두 수에 공통적으로 기록된 정수 중 최솟값을 가져와서 정렬하면 된다.이전에 풀었던 방법은 filter 등 고차 함수로 풀었는데, 시간이 다소 걸리기 때문에 특정 케이스에서 시간 초과가 났다. 결국 Int나 String으로 타입 캐스킹을 하지

문자열 나누기첫 번째 문자열을 기록하면서 제거할 때에는 교체해야 하기 때문에 캐릭터 옵셔널로 선언했다.