전체 글

✔ 문제 15649 N과 M(1) 문제 바로가기 💨 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 핵심 아이디어 백트래킹을 사용하여 N개의 자연수 중에서 M개를 고르는 모든 경우의 수를 출력해야 한다. 백트래킹은 가능한 모든 해를 탐색하는 알고리즘 중 하나로, DFS(깊이 우선 탐색)를 기반으로 한다. dfs 함수는 현재 선택한 숫자의 개수를 나타내는 n과 현재까지 선택된 숫자들의 리스트 lst를 인자로 받는다. 종료조건을 먼저보자. n이 M과 같아지면, 즉, M개의 숫자조합을 모두 선택했을 때는 lst를 ..

https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/description/ Algorithm 와...진짜 끙끙댔던 문제이다. 개인적으로 아이디어 떠올리기가 힘들었다. 결국 베스트 풀이를 봤는데...해시맵과 prefixsum의 결합이라니! 상상도 못했음...갈길이 참 멀군... 알고리즘은 여기를 참고했다. 방법은 다음과같다. 노드를 순회하며 prefix_sum을 해시맵에 저장해나간다. 이때 map에 prefixSum이 없다면 map에 저장하고, 이미 있다면 중간의 노드들을 제거하고, 중복된첫노드와 중복된두번째노드의 다음노드를 잇는다.(위 연두색 참고) 같은 prefixSum이 나왔다는건, 결국 중간의 합이 0이라는..

https://leetcode.com/problems/sliding-window-maximum/description Algorithm 누구나 첫 접근은 쉽지만, 시간 초과 해결이 관건인 문제이다... ㅎ monotonically Decreasing queue 개념을 이용하면 O(n)의 시간 복잡도로 풀 수 있다! queue q를 만들고,여기에 nums 원소 인덱스를 하나씩 추가해 나가며 monotonic q를 만든다. 이때, 값을 넣기전 현재값이 덱 끝값보다 크다면 덱에서 제거한다. (ex_ q = [1,2,3,4] 현재값=7 ~> 4,3,2,1 순으로 pop()하고 7을 넣는다.) 윈도우 크기가 k일대부터 결과에 최댓값을 추가하고, 슬라이딩 윈도우를 이동한다. Python from collections..

✔ 문제 2501 약수 구하기 문제 바로가기 💨 2501번: 약수 구하기 첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다. www.acmicpc.net PYTHON n, k = map(int, input().split()) div = [] for i in range(1, int(n**(1/2)) + 1): if n % i == 0: div.append(i) if i != n // i: # 중복을 피하기 위함 div.append(n // i) sorted_div = sorted(div) if k

https://leetcode.com/problems/car-fleet/description/ Algorithm 문제를 제대로 파악하지 못해 헤맸던 문제이다ㅜ. collide 할 경우, 앞에있는 차의 속도를 따라간다. 예를들어 (position,speed)가 (5,2) (7,1) 이 collide 할 경우 2의 speed를 가지는 것이 아니라 1의 speed를 가진다! 본 풀이는 스택을 이용할 수도 있고, 최대 도달시간 변수를 두고 풀 수도있다. 여기선 두가지 풀이를 모두 소개한다. 기본적원리는 모두 같다. 목적지까지 걸리는 시간을 계산하고 이를 앞의 것과 비교해 collide 여부를 판단한다. #1 스택 풀이 (position,speed) 리스트를 만든다. 스택을 거리 내림차순으로 정렬한다. for 문..

✔ 문제 2567 색종이-2 문제 바로가기 💨 2567번: 색종이 - 2 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 핵심 아이디어 먼저 2차원배열에 1로 색종이를 표시한다. 둘레 탐색은 두가지 방법이 있다. 1. 전체순회를 하며, 1을 만나면 해당 위치를 기준으로 4방향을 탐색해 0의 개수를 센다. 2. 함수를 가로,세로 방향으로 쭉 탐색하며 0>1,1>0 이 바뀌는 경계개수를 센다. 풀이에선 두번째 방법을 이용했다. +) 파이썬에서 전치를 할때는 zip(*list)를 이용했다. 예를들어, [ [1, 2, 3], [4, 5, 6], ..

✔ 문제 2563 색종이 문제 바로가기 💨 핵심 아이디어 2차원 배열로 저장 및 처리한다.시작점 좌표를 기준으로 해당 사각형크기만큼 배열에 1을 표시한다. PYTHON N = int(input()) arr = [[0]*102 for _ in range(102)] for _ in range(N): # [1] 해당 영역을 1로 표시 sj, si = map(int, input().split()) for i in range(si,si + 10): for j in range(sj, sj + 10): arr[i][j] = 1 # [2] 1의 개수를 cnt => 넓이 ans = 0 for lst in arr: ans += sum(lst) print(ans) JAVA import java.io.*; import jav..

✔ 문제 2798 블랙잭 문제 바로가기 💨 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 핵심 아이디어 브루트 포스로 완전탐색한다. ans = 0 으로 초기값을 두고, 모든 경우의 수를 탐색하며 ans보다 크고 범위내 숫자라면 갱신한다. PYTHON N, M = map(int, input().split()) lst = list(map(int, input().split())) ans = 0 for i in range(N-2): for j in range(i+1, N-1): fo..

https://school.programmers.co.kr/learn/courses/30/lessons/120852 Algorithm Idea 2부터 숫자를 늘려가며 나누어본다. 나누어지면 해당 숫자를 소인수분해 숫자 목록에 추가하고, 나누어지지않으면 1을 늘려 다음숫자로 나누어본다. +) Java에는 LinkedHashSet이라는 것이 있어 중복을 허용하지않고 순서까지 보장해 준다! Python def solution(n): answer = [] d = 2 while d

https://leetcode.com/problems/daily-temperatures/description/ Daily Temperatures - LeetCode Can you solve this real interview question? Daily Temperatures - Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer leetcode.com Algorithm 처음 완전탐색을 생각했으나 O(n^2)의 시간복잡..