오늘도 맑음

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

목표시작(start) 기둥에 있던 정렬된 원판을 목표(end) 기둥에 정렬한다.문제 풀이종료 조건- n이 1일 때, start => end 기둥에 꽂는다. => answer 배열에 저장 기본 재귀 형식1. n -1 까지의 원판을 other 기둥에 꽂는다.2. n번 째의 원판을 start 기둥에서 end 기둥에 꽂는다. => answer 배열에 저장3. other 기둥에 있는 n -1 개의 원판을 end기둥에 꽂는다.  https://school.programmers.co.kr/learn/courses/30/lessons/12946