본문 바로가기

Algorithm

 (37)
[Javascript] 더 맵게 목차1. 문제 설명2. 문제 풀이3. 전체 코드1. 문제 설명모든 음식의 스코빌 지수를 K 이상으로 만드는 데 걸리는 횟수를 구하는 문제이다.K 이상으로 만들기 위해서, 연산을 해야하는데 그 연산은 다음과 같다.섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Key point제한 조건 : 2 가장 적은 두 개의 값을 계속 구해야하는데, 그때그때마다 새로운 적은 값을 구하기 위해서는 시간초과가 발생한다.👉 힙 알고리즘을 구현해내야한다. 2. 문제 풀이1) 기본 코드힙을 구현하기 위한 기본 구조는 다음과 같다.class MinHeap { constructor() { this.heap = []; // 힙 배열 } ..
[Javascript] 가장 큰 수 목차1. 문제 설명2. 문제 풀이3. 정답 코드 1. 문제 설명0 또는 양의 정수들을 집합이 주어졌을 때 그 수들을 붙여서 만들수 있는 가장 큰 수를 구하는 문제이다.입출력 예는 다음과 같다. 주의할 점numbers를 내림차순하여 이어붙인 것이 반드시 가장 큰 수는 아니다.만약, 2번째 예시를 내림차순 방식으로 답을 구한다면 → "9534303" 이다.하지만 가장 큰 수는 "9534330" 이므로, 다른 방식을 찾아야했다! 2. 문제 풀이만약 [3, 30] 이 주어진다면, 가장 큰 수는 "330" 이다.내림차순을 결정하는 수는 2개의 수를 더한 수이다. ( ≠ 각 수를 내림차순) (참고) 기본 sort 함수 사용법[1,2,3,4].sort((a, b)=> b - a); a는 뒷번호, b는 앞번호이다. b..
[Javascript] 롤케이크 자르기 목차1. 문제 설명2. 문제 풀이3. 정답 코드 1. 문제 설명다음 문제는 롤케이크를 자르는 문제이다.롤케이크에는 토핑이 올라가 있으며, 토핑의 종류는 숫자로 표시된다. (ex. 1, 2, 3...)철수는 롤케이크를 2조각으로 나눠 동생과 나눠가져야하는데,공평하게 나누기 위하여 다음 조건을 만족해야한다.=> 토핑의 가지수가 동일해야 함 이 때, topping의 개수가 1,000,000로 매우 큰 숫자임을 주의해야한다.  2. 문제 풀이topping의 개수가 1,000,000로 매우 큰 숫자이므로, 롤케이크를 자르는 행위는 선형 탐색으로 해결해야한다는 것을 알았다. 변수각 조각이 가진 토핑들을 저장할 객체와 가짓 수를 카운트할 변수를 선언해야한다. 로직1. 초기 상태 : 모든 토핑을 오른쪽 조각에 우선 배..
순열, 조합 문제 풀이 (with. Python) 목차1. 문제 이해하기2. 실전 팁3. itertools 라이브러리 사용4. 자주 나오는 예제1. 문제 이해하기모든 경우의 수를 구해야 한다면, 아래 조건들에 따라 분류합니다. "중복이 허용되는가?"허용된다면: 중복 순열, 중복 조합허용되지 않는다면: 순열, 조합"순서가 중요한가?"순서 중요: 순열, 중복 순열순서 중요하지 않음: 조합, 중복 조합"정렬 조건이 있는가?"오름차순 → 조합비내림차순 → 중복 조합"결과의 조건이 명시되어 있는가?"예를 들어, 총합 제한, 특정 숫자 포함 여부 등의 조건이 있을 수 있음.이 조건을 함수 호출 조건에 포함2. 실전 팁순열/조합 문제는 보통 백트래킹을 사용합니다.백트래킹에서 중요한 것은 1. 종료 조건2. 반복문 (n가지 중 1가지를 pick) ⭐ 추가적으로 결과 ..
백준 21315. 카드 섞기 목차1. 문제2. 구현3. 개선한 코드2. 구현가능한 k 조합을 2번 반복하더라도 시간 내에 풀 수 있으므로, 모든 조합을 생각했습니다. 1. 카드 섞기 함수를 제외한 나머지 코드를 완성 - max_k 는 입력 카드 수 N 에 대해 나올 수 있는 최대 kimport sysfrom collections import dequeinput = sys.stdin.readlinen = int(input())finish_list = list(map(int, input().split()))start_list = [i for i in range(1, n+1)]# max_k 구하기max_k = 10for i in range(max_k, 0, -1): if 2 ** i  2. 관건은 카드를 섞는 로직인데, deque을..
백준 14226. 이모티콘 풀이bfs 순회를 하면서 핵심은 이중 리스트로 방문처리를 해야한다는 것입니다.visited[화면 이모티콘 개수][클립보드 이모티콘 개수] 로 방문처리를 합니다.범위를 넘어가는 값에 대해서는 더 이상 진행하지 않는 것도 핵심입니다. import sysfrom collections import dequeMAX = 1000 # 최대 화면 이모티콘 수 (2  정리생각해내는 것이 쉽지 않았던 문제인 만큼 문제를 분석해야한다.다음 일을 처리하기 위해서 (화면 이모티콘, 클립보드 이모티콘) 조합이 필요하면 이를 2차원 배열로 방문표시하면 된다.예) 만약 3개의 조합이다? => 3차원 배열 ✔ bfs 문제1. visited 배열의 요소 (몇 개로 구성하면 좋을지: 차원의 수)2. 범위를 어떻게 구성하면 좋을지를 먼저 ..
백준 1074. 골드 Z 문제첫째줄에 N, r, c가 주어질 때 r행 c열을 몇번째로 방문했는지 출력한다.풀이이 문제의 경우 결국 스스로 해결하지는 못했지만, 유튜브 강의와 해설을 보고 이해할 수 있었다. - N = 1 x 4개 =>  N = 2를 만든다.- N = 2 x 4개 =>  N = 3을 만든다.관계를 본다면 N = 2를 해결하기 위해서는 4사분면으로 나누고 N = 1을 재귀적으로 호출하면 해결가능하다.사분면으로 나누기 위해서 절반을 기준으로 둔다.half = 2 ** (N-1)  그리고 half를 기준으로 대소 관계를 비교하여 사분면을 나눈다.N = 2일 때 i, j는 (3,3) 이지만 N = 1을 호출할 때 i, j는 (0,0)이다.만약 i, j가 half를 기준으로 넘어간다면, half를 자르면 된다.  # 사분면..
9935. 문자열 폭발 문제 풀이괄호 문제와 비슷한 방식이다.문자열을 순회하며 특정 패턴 문자열이 있을 때 제거하고, 변형된 문자열로 계속해서 반복 연산하는 문제이다. ⭐ [문자 추가] -> [조건 검사] -> [패턴 찾아 제거]1. base 문자열을 순회하며 스택에 각 문자(c)를 넣는다.2. 스택의 크기가 sub 문자열의 개수보다 작으면 같은 길이의 문자열 비교가 불가하므로, 다음 반복으로 넘어간다(continue 사용)2. sub 문자열과 스택의 끝에서 sub 문자열의 길이만큼 슬라이싱한 문자열을 비교하여 같다면 제거한다. (del 사용) # 문자열 폭발import sysinput = sys.stdin.readlinedef solution(base, sub): sub_len = len(sub) stack = [..

티스토리툴바