🌱 → 🌳

https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 정보 문제 유형 : stack/queue 설계 방법 소요 시간을 미리 계산해두고 q에 저장 (q는 deque) q.popleft해서 앞에 있는 기능이 배포될 때 함께 배포될 수 있는 뒷 기능 저장 코드 실패 코드 from collections import deque def solution(progresses, speeds): answer = [] cnt = 1 q = deque() for i..

https://school.programmers.co.kr/learn/courses/30/lessons/42576 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 설계 방법 completion 돌면서 participant에 i가 있으면 completion 배열에서 i 지워주고, 마지막 남은 participant를 반환해주면 된다고 생각했음 근데 이렇게 하면 시간복잡도가 O(n^2) 이기 때문에 시간초과발생 문득 python 내장 sort() 함수가 O(nlogN)인 게 기억났음 내장함수 사용해서 정렬한 뒤, 순서대로 빼면 되겠구나 생각함 코드 시간초과 de..

문제 정보 문제 유형 난이도 걸린 시간 해결 유무 스스로 구현 성공 DFS/BFS level2 33m O O 설계 방법 numbers 돌면서 arr 모든 요소에 대해 -num과 +num을 해줌 arr 모든 요소를 돌 때는 arr.popleft()로 하나씩 빼서 사용 -num과 +num을 해준 요소는 arr.append() numbers 다 돌았으면 마지막 arr에 있는 요소 중 target과 일치하는 요소 카운팅 코드 내 풀이 from collections import deque def solution(numbers, target): arr = deque([0]) for num in numbers: for _ in range(len(arr)): v = arr.popleft() arr.append(v - ..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 설계 방법 비교 횟수가 가장 작으려면 가장 작은 값들부터 먼저 계산해야 한다. 단 하나의 값이 남을 때까지 가장 작은 값 2개를 계산, 추가 그리고 저장을 반복한다. 일반적인 배열로 처리할 경우 시간 초과가 발생한다. 정렬하는 과정을 우선순위 큐에 맡겨주면 해결 코드 시간초과 코드 import sys input = sys.stdin.readline n = int(input()) ca..

https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 정보 큐 실버4 20m O 설계 방법 queue class를 설계 후 코드 작성 코드 import sys input = sys.stdin.readline class Queue: def __init__(self): self.data = [] def size(self): return len(self.data) def empty(self): if len(self.data) == 0..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 정보 스택 실버3 1h20m X 설계 방법 입력한 수를 만날 때 까지 오름차순으로 push 입력한 수를 만나면 while문 탈출. 즉 cnt = num일 때까지 while문을 돌아 스택을 쌓음 stack의 top이 입력한 숫자와 같다면 스택의 top을 꺼내 수열을 만들어 줌 stack의 top이 입력한 수가 아..

다이나믹 프로그래밍( 동적 계획법) 다이나믹 프로그래밍 : 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식 탑 다운(하향식) 보텀 업(상향식) 일반적으로 프로그래밍 분야에서 동적(dynamic)이란? 자료구조에서 동적 할당(dynamic allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미 반면 다이나믹 프로그래밍에서 ‘다이나믹’은 별 의미 없이 사용된 단어 다이나밍 프로그래밍의 조건 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서..

탐색 알고리즘 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정함 이진 탐색 동작 예시 이진 탐색의 시간 복잡도 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 $log_2N$ 에 비례함 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개가량의 데이터만 남음 2단계를 거치면 8개가량의 데이터만 남음 3단계를 거치면 4개가량의 데이터만 남음 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 $O(logN)$을 보장함 파이썬 이진 탐색 라이브러리 bis..