PS 53
-
[간만에 스터디] LeetCode Compare Version Numbers
Compare Version Numbers 코드 접근 및 풀이방법 - 각 버전에서 . 기준으로 파트를 나누어 파트별 문자열을 정수로 치환 - 정수로 치환한 버전의 파트별로 대소를 구분 - 대소 구분이 되지 않는다면 같은 버전으로 취급
-
[간만에 스터디] LeetCode Path With Minimum Effort
Path With Minimum Effort 코드 접근 및 풀이방법 - minimum effort(최소 노력)을 구하기 위해 다익스트라 알고리즘 활용 - 경로상 최소 노력(최대 절대 높이 차이)를 유지하기 위해 이전에 구했던 최소 노
-
[간만에 스터디] LeetCode Number of Provinces
Number of Provinces 코드 접근 및 풀이방법 1. 그래프탐색(BFS or DFS)은 그래프에 존재하는 모든 간선을 통해 결국 모든 노드를 방문한다. 1. 단 이 문제의 경우 그래프가 양방향 간선이 존재하기 때문에 반드시
-
[간만에 스터디] LeetCode Longest Common Subsequence
Longest Common Subsequence 코드 최종 Accepted 코드 Wrong Answer 코드 접근 및 풀이방법 1. 중복문제를 정의하기 위해, 전체문자열이 아닌 현재 위치의 문자 기준으로의 공통 문자열이 구성될 수 있
-
[간만에 스터디] LeetCode Partition Array for Maximum Sum
Partition Array for Maximum Sum 코드 최적화 코드 (아래 최적화되지 않은 코드에 비해 약 270배 빠름) 불필요한 이전의 i - j(0..k까지의 내 부분배열)에 해당하는 최적해를 구하러 가는 것이 제거 되었
-
[간만에 스터디] LeetCode Decode Ways
Decode Ways 코드 접근 및 풀이 방법 아래 이미지 색깔별로 중복문제(메모이제이션 대상) 전체 풀이 기록: initi8ors/algorithm2024
-
[간만에 스터디] LeetCode Find the Original Array of Prefix Xor
Find The Original Array of Prefix Xor 코드 접근 및 풀이방법 1. 문제에서 묻는 결과 값은 입력으로 주어지는 값을 xor 연산 전의 원본값이다. 2. xor 연산의 특성을 고려해보니 xor을 연산 결과의
-
[간만에 스터디] LeetCode Best Time to Buy and Sell Stock II
Best Time to Buy and Sell Stock II 코드 접근 및 풀이방법 전체 풀이 기록: initi8ors/algorithm2024
-
[간만에 스터디] LeetCode Next Permutation
Next Permutation 코드 접근 및 풀이방법 - nums.length가 최대 100까지 가므로 실제 순열을 구하는 dfs 방식으로는 100! 까지 될 수 있기 때문에 불가능하다. - 뭔가.. 최대 N^2 까지 할 수 있도록
-
[간만에 스터디] LeetCode LRU Cache
문제 LRU Cache — capacity 만큼만 담는 캐시를 설계한다. get / put 모두 평균 O(1) 이어야 하고, 용량이 꽉 찬 상태에서 새 키를 넣으면 가장 오래 안 쓴(LRU) 항목을 버린다. - LRUCache(cap
-
[간만에 스터디] LeetCode Two Sum
Two Sum https://leetcode.com/problems/two-sum/description/ 3번만에 품 (분명히 몇년전에 알고리즘 공부를 한참 할때에도 몇번씩이나 풀어봤던 문제인데 역시나 오랜만에 다시 하려니 다시 백지
-
백준 13913 숨바꼭질 4
문제 수빈이는 점 N 에, 동생은 점 K 에 있다. 수빈이는 1초에 걷기 ( X-1 또는 X+1 ) 또는 순간이동 ( 2 X )을 할 수 있다. 동생을 찾는 가장 빠른 시간과, 그때 거쳐 간 위치들 을 출력하면 된다. - 입력 : N
-
백준 1038 감소하는 수
문제 높은 자리에서 낮은 자리로 갈수록 숫자가 계속 작아지는 수를 감소하는 수라 한다(예: 321 , 950 은 감소하는 수, 322 · 958 은 아니다). 한 자리 수와 0 도 감소하는 수다. N 번째 감소하는 수 를 구하면 된다
-
백준 12101 1, 2, 3 더하기 2
문제 정수 n 을 1 , 2 , 3 의 합으로 나타내는 모든 방법을 사전순 으로 정렬했을 때, k 번째에 오는 식을 구하면 된다. - 입력 : n k . - 출력 : 사전순 k 번째 식. 방법의 수가 k 보다 적으면 -1 . - 제한
-
백준 2251 물통
문제 용량이 각각 A , B , C 인 물통 셋이 있다. 처음엔 C 만 가득 차 있고 A , B 는 비어 있다. 한 물통에서 다른 물통으로, 받는 쪽이 가득 차거나 주는 쪽이 빌 때까지 물을 부을 수 있다. 첫 번째 물통( A )이
-
백준 1941 소문난 칠공주
문제 5 × 5 격자에 학생 25명이 앉아 있다. 각 자리는 '이다솜파'( S ) 또는 '임도연파'( Y )다. 다음 조건을 모두 만족하는 7명을 뽑는 경우의 수 를 구하면 된다. 1. 7명이어야 한다. 2. 7명이 가로·세로로 모두
-
백준 11053 가장 긴 증가하는 부분 수열
문제 수열 A 에서 가장 긴 증가하는 부분 수열(LIS) 의 길이를 구하면 된다. 부분 수열은 원래 순서를 유지한 채 일부를 고른 것이고, 증가는 강증가(앞보다 뒤가 크다)다. - 입력 : 1번째 줄에 N , 2번째 줄에 수열 A .
-
프로그래머스 부족한 금액 계산하기
문제 놀이기구의 기본 이용료가 price 인데, i 번째로 탈 때는 price × i 만큼을 낸다. 소지금이 money 일 때 count 번 타면 돈이 얼마나 부족한지 를 구하면 된다(부족하지 않으면 0). - 입력 : price (
-
백준 11003 최솟값 찾기
문제 수열 A 와 윈도우 길이 L 이 주어질 때, 각 i 에 대해 D i = A {i-L+1} … A i 구간의 최솟값 을 출력하면 된다(구간이 시작 전이면 존재하는 부분만). - 입력 : 1번째 줄에 N L , 2번째 줄에 수열 A
-
백준 11866 요세푸스 문제 0
문제 1 번부터 N 번까지가 원을 이루고 앉아 있다. K 번째 사람을 차례로 제거하고, 남은 사람들로 원을 이어가며 같은 과정을 반복한다. 모두 제거되는 순서(요세푸스 순열)를 구하면 된다. - 입력 : N K . - 출력 : <a,
-
코드포스 938D Buy a Ticket
문제 도시가 N개 있고, 양방향 기찻길이 M개 있다( i 번째 길은 u ↔ v 를 비용 w 로 잇는다). 각 도시 i 에는 콘서트 티켓 값 a i 가 있다. 각 도시 i 마다 , 어떤 도시 j 로 가서(머물러도 됨) 콘서트를 보고 다
-
백준 11375 열혈강호
문제 회사에 직원이 N명, 해야 할 일이 M개 있다. 각 직원은 자신이 할 수 있는 일들 중 하나만 담당할 수 있고, 각 일도 한 명 만 담당한다. 할 수 있는 일의 최대 개수를 구하면 된다. - 입력 : 1번째 줄에 N M . 이어
-
백준 11725 트리의 부모 찾기
문제 루트가 1번인 트리가 주어진다. 각 노드의 부모 노드 를 찾아 2번 노드부터 순서대로 출력하면 된다. - 입력 : 1번째 줄에 노드 수 N , 이어서 N-1 개 줄에 연결된 두 정점. - 출력 : 2번 노드부터 N 번 노드까지
-
백준 16118 달빛여우
문제 그루터기 N개가 오솔길 M개로 이어져 있다(각 길의 길이 d ). 여우 는 1번 그루터기에서 출발해 모든 길을 같은 속도로 달린다. 늑대 도 1번에서 출발하지만, 오솔길을 지날 때마다 빠르게(2배속) ↔ 느리게(0.5배속) 를
-
백준 1194 달이 차오른다, 가자
문제 미로를 탈출하는 최소 이동 횟수를 구한다. 빈 곳 . 은 지날 수 있고 벽 은 못 지난다. 열쇠 a f 는 밟으면 줍고, 문 A F 는 대응하는 열쇠가 있어야 지날 수 있다. 시작 0 에서 출구 1 로 가면 된다. - 입력 :
-
코드포스 1515A Phoenix and Gold
문제 서로 다른 무게의 금덩이 N개를 저울에 하나씩 올린다. 그런데 저울은 올린 무게의 누적 합이 정확히 x 가 되는 순간 폭발 한다. 누적 합이 한 번도 x 가 되지 않도록 올리는 순서를 찾으면 된다. - 입력 : 1번째 줄에 테스
-
코드포스 1514A Perfectly Imperfect Array
문제 길이 N인 배열에서, 곱이 완전제곱수가 아닌 비어있지 않은 부분수열(subsequence)이 존재하는지 판별하면 된다. - 입력 : 1번째 줄에 테스트케이스 수 t . 각 케이스마다 n 과 배열 a 1 … a n . - 출력 :
-
코드포스 1478A Nezzar and Colorful Balls
문제 공 N개에 비내림차순( a i ≤ a {i+1} )으로 수가 적혀 있다. 공을 색칠하는데, 같은 색끼리만 모았을 때 그 수열이 강증가(strictly increasing) 가 되어야 한다(길이 1 이하는 강증가로 본다). 필요한
-
코드포스 1472B Fair Division
문제 무게가 1 또는 2인 사탕 N개를 두 사람에게 무게 합이 똑같이 나눌 수 있는지 판별하면 된다(사탕은 쪼갤 수 없다). - 입력 : 1번째 줄에 테스트케이스 수 t . 각 케이스마다 n 과 사탕 무게 a 1 … a n (각 1
-
백준 2583 영역 구하기
문제 M × N 모눈종이에 K 개의 직사각형을 칠한다. 칠하지 않은 나머지 부분이 몇 개의 분리된 영역 으로 나뉘는지, 그리고 각 영역의 넓이가 얼마인지 구하면 된다. - 입력 : 1번째 줄에 M N K , 이어서 K 줄에 직사각형의
-
백준 16505 별
문제 별. 출력 예제의 규칙을 유추해 별을 찍는 문제다. 패턴은 시에르핀스키 삼각형 모양이다. 한 변이 2^N 인 정사각형 영역을 절반 크기의 네 사분면으로 나눴을 때, 오른쪽 아래 사분면을 비우고 나머지(왼쪽 위·오른쪽 위·왼쪽 아
-
백준 2447 별 찍기 - 10
문제 별 찍기 - 10. 재귀적인 별 패턴을 출력하는 문제다. 크기 N 의 패턴은 N×N 정사각형이다. - 크기 3의 패턴(기본): 가운데 한 칸만 공백이고 나머지 8칸은 별. - 크기 N(N 3)의 패턴: 전체를 3×3 으로 나눈
-
백준 3055 탈출
문제 숲이 격자로 주어진다. 고슴도치 S 는 비버굴 D 로 가야 하는데, 물 이 매 분 인접한 빈 칸으로 퍼진다. 고슴도치도 매 분 인접한 빈 칸으로 이동하며, 물이 찰 칸으로는 갈 수 없다. 돌 X 는 물도 고슴도치도 못 지난다.
-
프로그래머스 정수 삼각형
문제 숫자로 채워진 삼각형이 주어진다. 맨 위에서 시작해 아래로 내려가는데, 한 칸 내려갈 때는 바로 아래 또는 아래 대각선 으로만 이동할 수 있다. 거쳐 간 숫자들의 합이 가장 큰 경로의 합 을 구하면 된다. - 입력 : 삼각형 t
-
백준 9935 문자열 폭발
문제 문자열에 "폭발 문자열"이 들어 있으면 그 부분이 사라지고, 남은 양쪽이 다시 붙는다. 이 폭발은 더 이상 터질 게 없을 때까지 연쇄적으로 일어난다. 모든 폭발이 끝난 뒤 남은 문자열을 구하면 된다. - 입력 : 1번째 줄에 문
-
프로그래머스 불량 사용자
문제 응모자 아이디 목록 user id 와, 일부 글자를 로 가린 불량 사용자 패턴 목록 banned id 가 주어진다. 각 banned id 패턴에 맞는 user id 를 하나씩 배정해 만들 수 있는 제재 아이디 목록의 경우의 수
-
프로그래머스 무지의 먹방 라이브
문제 회전판에 음식 N개가 1 번부터 놓여 있다. 무지는 1 번부터 한 음식을 1초 먹고 다음 번호로 넘어가며, 마지막 번호 다음엔 다시 1 번으로 돈다. 이미 다 먹은 음식은 건너뛴다. 먹기 시작한 지 k 초가 지난 순간 방송이 끊
-
백준 7579 앱
문제 실행 중인 앱 N개가 각각 메모리 m i 바이트를 쓰고 있다. 새 앱을 실행하려면 M바이트가 더 필요한데, 앱을 비활성화하면 그 메모리를 확보하는 대신 (다시 켤 때 드는) 비용 c i 가 발생한다. M바이트 이상을 확보하면서
-
백준 4991 로봇 청소기
문제 방이 격자로 주어진다. 로봇 청소기 o 가 한 칸에 있고, 더러운 칸 이 여러 개, 빈 칸 . , 가구(벽) x 가 있다. 로봇은 상하좌우로 한 칸씩(1분) 움직이며 가구는 지날 수 없다. 모든 더러운 칸을 청소하는 데 드는 최
-
비트마스킹 (Bitmasking) 정리
비트마스킹 집합의 상태를 정수의 각 비트로 표현하는 기법. 원소가 N개인 집합을 N비트 정수 하나로 나타낸다. (i번 비트가 1이면 i번 원소가 집합에 있음) 집합 연산이 비트 연산 한 번으로 끝나 빠르고, 무엇보다 상태를 정수 하나
-
최소 신장 트리 (MST) 정리
최소 신장 트리 (MST) 연결된 가중치 그래프에서, 모든 정점을 잇되 사이클 없이(즉 트리로) 연결하는 부분 그래프 중에서 간선 가중치의 합이 최소 인 것. 정점이 V개면 간선은 정확히 V-1개를 쓴다. "모든 도시를 최소 비용으로
-
위상 정렬 (Topological Sort) 정리
위상 정렬 방향 그래프에서 선후 관계(A 다음에 B)를 어기지 않도록 정점들을 한 줄로 나열하는 것. "선수 과목을 다 들어야 다음 과목을 듣는다", "이 작업이 끝나야 저 작업을 시작한다" 같은 순서 제약을 만족하는 순서를 구할 때
-
유니온 파인드 (Union-Find) 정리
유니온 파인드 (서로소 집합) 여러 원소가 어떤 집합에 속하는지를 관리하면서, 두 연산을 빠르게 처리하는 자료구조. - find(x) : x가 속한 집합의 대표(루트)를 찾는다. - union(a, b) : a가 속한 집합과 b가 속
-
분할 정복 (Divide and Conquer) 정리
분할 정복 큰 문제를 같은 형태의 작은 부분 문제로 나눠서(divide) 각각 풀고(conquer), 그 결과를 합쳐(combine) 원래 문제의 답을 만드는 설계 기법. DP와 헷갈리기 쉬운데, 분할 정복은 보통 부분 문제들이 겹치
-
누적 합 (Prefix Sum) 정리
누적 합 배열의 앞에서부터의 합을 미리 구해 두어, 임의 구간의 합을 O(1) 에 답하는 기법. 매번 구간을 직접 더하면 질의 1번에 O(N) , 질의가 많으면 O(NQ) 로 터진다. 누적 합을 한 번 O(N) 에 만들어 두면 그 뒤
-
백트래킹 (Backtracking) 정리
백트래킹 가능한 모든 경우를 DFS로 하나씩 만들어 보되, 더 진행해도 답이 될 수 없다고 판단되는 순간 그 가지를 포기하고 되돌아가는 방법. 완전 탐색(brute force)과 뼈대는 같지만, "여기서 더 가봐야 소용없다"를 미리
-
이분 탐색 (Binary Search) 정리
이분 탐색 정렬된 배열에서 탐색 범위를 절반씩 줄여 가며 원하는 값을 찾는 방법. 매번 후보가 반으로 줄어드니 O(log N) . 핵심 전제는 단조성(monotonicity) 이다. "어떤 기준값 이전은 전부 참, 이후는 전부 거짓"
-
다익스트라 (Dijkstra) 정리
다익스트라 어떤 그래프 G와 시작 정점 st가 주어질 때, st로부터 다른 모든 정점으로의 최단 경로 길이를 구하는 알고리즘. 이러한 특징으로 시작점 고정 최단거리 알고리즘 이라고도 한다. 다익스트라 알고리즘은 매 단계마다 도달할 수
-
다이나믹 프로그래밍 (DP) 정리
다이나믹 프로그래밍 정의 복잡한 큰 문제를 재귀적인 방식(재귀적인 방식이지 재귀 함수로 구현해야 하는것은 아니다)으로 간단한 하위 문제로 나누어 최종 큰 문제까지 해결할 수 있는 알고리즘 설계 기법, 주로 모든 경우의 수를 일일이 다
-
투 포인터 (Two Pointer) 정리
Two Pointer 일반적으로 어떤 수열 $A = {1,2,3,4,5,6...}$ 에서 각각 다른 원소를 가르키고 있는 두개의 포인터를 움직이며 투포인터 없이는 $O(N^2)$ 만에 수행 할 수 있는 연산을 $O(N)$ 만에 해결하
-
너비 우선 탐색 (BFS) 정리
BFS (너비 우선 탐색) 시작 정점에서 가까운 정점부터 차례대로, 레벨 단위로 퍼져 나가며 탐색하는 방법. 큐(Queue)를 사용한다. DFS가 한 갈래를 끝까지 파고드는 것과 반대로, BFS는 시작점에서 거리 1인 정점들을 모두
-
깊이 우선 탐색 (DFS) 정리
DFS (깊이 우선 탐색) 그래프나 트리에서 한 정점을 시작으로, 갈 수 있는 곳까지 최대한 깊이 들어갔다가 더 갈 곳이 없으면 직전 갈림길로 되돌아와 다른 길을 탐색하는 방법. 되돌아오는(backtrack) 동작이 핵심이라, 재귀
-
그리디 (Greedy) 정리
Greedy 1. 앞에 놓인 선택지들 중 바로 보이는 것을 딱! 고르면 그게 항상 최선이 될 수 있도록 문제의 구성요소를 변형 및 접근하여 해결하는 방법 - 선택한것은 순간적으로는 최적해가 될 수 있지만, 그 선택들이 모여 전체적으로