오늘도 맑음

목차1. 문제 설명2. 문제 풀이3. 정답 코드 1. 문제 설명다음 문제는 롤케이크를 자르는 문제이다.롤케이크에는 토핑이 올라가 있으며, 토핑의 종류는 숫자로 표시된다. (ex. 1, 2, 3...)철수는 롤케이크를 2조각으로 나눠 동생과 나눠가져야하는데,공평하게 나누기 위하여 다음 조건을 만족해야한다.=> 토핑의 가지수가 동일해야 함 이 때, topping의 개수가 1,000,000로 매우 큰 숫자임을 주의해야한다.  2. 문제 풀이topping의 개수가 1,000,000로 매우 큰 숫자이므로, 롤케이크를 자르는 행위는 선형 탐색으로 해결해야한다는 것을 알았다. 변수각 조각이 가진 토핑들을 저장할 객체와 가짓 수를 카운트할 변수를 선언해야한다. 로직1. 초기 상태 : 모든 토핑을 오른쪽 조각에 우선 배..

목차1. 문제 이해하기2. 실전 팁3. itertools 라이브러리 사용4. 자주 나오는 예제1. 문제 이해하기모든 경우의 수를 구해야 한다면, 아래 조건들에 따라 분류합니다. "중복이 허용되는가?"허용된다면: 중복 순열, 중복 조합허용되지 않는다면: 순열, 조합"순서가 중요한가?"순서 중요: 순열, 중복 순열순서 중요하지 않음: 조합, 중복 조합"정렬 조건이 있는가?"오름차순 → 조합비내림차순 → 중복 조합"결과의 조건이 명시되어 있는가?"예를 들어, 총합 제한, 특정 숫자 포함 여부 등의 조건이 있을 수 있음.이 조건을 함수 호출 조건에 포함2. 실전 팁순열/조합 문제는 보통 백트래킹을 사용합니다.백트래킹에서 중요한 것은 1. 종료 조건2. 반복문 (n가지 중 1가지를 pick) ⭐ 추가적으로 결과 ..

목차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을..

풀이bfs 순회를 하면서 핵심은 이중 리스트로 방문처리를 해야한다는 것입니다.visited[화면 이모티콘 개수][클립보드 이모티콘 개수] 로 방문처리를 합니다.범위를 넘어가는 값에 대해서는 더 이상 진행하지 않는 것도 핵심입니다. import sysfrom collections import dequeMAX = 1000 # 최대 화면 이모티콘 수 (2  정리생각해내는 것이 쉽지 않았던 문제인 만큼 문제를 분석해야한다.다음 일을 처리하기 위해서 (화면 이모티콘, 클립보드 이모티콘) 조합이 필요하면 이를 2차원 배열로 방문표시하면 된다.예) 만약 3개의 조합이다? => 3차원 배열 ✔ bfs 문제1. visited 배열의 요소 (몇 개로 구성하면 좋을지: 차원의 수)2. 범위를 어떻게 구성하면 좋을지를 먼저 ..

문제첫째줄에 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를 자르면 된다.  # 사분면..

문제 풀이괄호 문제와 비슷한 방식이다.문자열을 순회하며 특정 패턴 문자열이 있을 때 제거하고, 변형된 문자열로 계속해서 반복 연산하는 문제이다. ⭐ [문자 추가] -> [조건 검사] -> [패턴 찾아 제거]1. base 문자열을 순회하며 스택에 각 문자(c)를 넣는다.2. 스택의 크기가 sub 문자열의 개수보다 작으면 같은 길이의 문자열 비교가 불가하므로, 다음 반복으로 넘어간다(continue 사용)2. sub 문자열과 스택의 끝에서 sub 문자열의 길이만큼 슬라이싱한 문자열을 비교하여 같다면 제거한다. (del 사용) # 문자열 폭발import sysinput = sys.stdin.readlinedef solution(base, sub): sub_len = len(sub) stack = [..

해결방안가장 적은 두 값을 더하여 다시 넣는 행위를 반복하여 쉽게 해결할 수 있었다.시간 복잡도는 O(NlogN)이 나온다.   또 다른 방법으로는 2개의 큐를 이용하는 방법이 있다. 첫번째 큐: a는 cards 리스트를 정렬한 다음 만든 큐두번째 큐: b는 빈 큐 아래의 코드에서 보면 두 큐의 첫번째 원소끼리 비교하여 더 적은 숫자를 리턴하는데, a 큐에서는 이미 정렬된 상태이기 때문에 맨 앞이 가장 적은 숫자임을 보장한다.b 큐에서는 더한 값들을 순서대로 추가하는데, 이럴 경우 뒤에 더한 값들이 무조건 먼저 더한 값들보다 클 수 밖에 없다.따라서 b의 맨 앞이 가장 적은 숫자임을 보장한다. 이 경우도 힙과 마찬가지로 시간복잡도 O(NlogN)이 나온다. 정리일반적으로 가장 큰 원소를 뽑아내라? 이건 ..

큐 : FIFO 구조로 들어온 순서대로(enqueue) 나가는(dequeue) 자료구조이다.우선 순위 큐 : 우선 순위가 높은 것이 먼저 나가는 자료구조이다. 우선 순위 큐를 구현하는 방법은 다양하지만 그 중 heap 이라는 자료구조에서 enqueue, dequeue하는 방법이 가장 시간이 적게 걸린다. heap완전 이진 트리 형태로 우선 순위 큐를 구현하기 위해 만들어진 자료구조이다. ✔ min heap(최소 힙)"부모 노드 ✔ max heap(최대 힙)"부모 노드 > 자식 노드" 인 완전 이진 트리 Enqueue와 Dequeuemin heap 자료구조를 바탕으로 설명하겠습니다. "우선 순위가 높다"는 것은 숫자가 더 작다는 의미 [Enqueue]1) 새로운 노드를 마지막 노드에 추가2) 부모 노드와 ..

문제모든 도시를 방문하고 다시 현재로 돌아오는 데 걸리는 최소 비용을 구해라[입력]첫 줄에는 방문해야할 도시의 수를 입력받는다.그 다음에 도시 사이를 이동하는 비용을 배열로 받는데, cities[i][j]란 i -> j 도시로 이동하는 데 드는 비용을 의미한다.[정리]모든 도시를 거쳐야 한다.한번 거쳤던 도시는 재방문할 수 없다.마지막 도시를 거친 후 처음 도시로 돌아가야하는 데, 걸리는 최소 비용을 구한다.문제 풀이도시의 수(N)가 10개 이하이다. 모든 도시를 방문했을 때도 10! 이기 때문에 1초안에 실행이 가능하다.따라서 백트래킹을 구현하였다. ⭐ key point!if value > ans 로 만약 모든 도시를 방문하지 않더라도 이미 결과 저장 값(ans) 보다 크다면 즉시 리턴을 통해 시간을 ..

문제(1,1)부터 (N, M) 까지 가는 최소 칸의 수를 출력하는 문제이다.- 미로 바깥으로는 나갈 수 없다.- 0은 지뢰이므로 갈 수 없다.  문제 풀이기존 코드 - 미로를 탐색하기 위해 bfs를 사용했으며 visited라는 배열을 선언하여 visited[x][y] 까지 가는 데 지나친 칸 수를 저장했다.- 조건  1. 미로를 넘어간 경우  2. 지뢰인 경우 (map[x][y]가 0) - 여기서 방문 여부에 따라 다른 로직을 작성하였다.  - 방문 안한 경우 : 작업 큐(q)에 추가하고, visited[next_x][next_y]에  이전의 칸 수 +1 저장  - 방문한 경우 : 새로운 길이 visited에 저장된 수보다 적은 경우, visited[next_x][next_y]에  이전의 칸 수 +1 로..