GREEDY
-
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 DFS를 활용한 풀이 : 시간 초과 문자 조합을 구성하기 위해서 DFS를 활용했다. 조합 구성 시, 순서를 유지하기 위해서 start 변수를 도입해 탐색 범위를 제한했다. 시간 초과가 발생했다. 풀이의 시간 복잡도는 ${n \choose k}$ 인데, n과 k가 최대 100만 까지 가능하기 때문이다. 더보기 DFS 함수의 시간 복잡도 T(dfs) = (n-k) choose (k-1) + (n-k+1) choose (k-1) + ... + n choose (k-1) = (n+1) choos..
[Python] 프로그래머스 큰 수 만들기 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 DFS를 활용한 풀이 : 시간 초과 문자 조합을 구성하기 위해서 DFS를 활용했다. 조합 구성 시, 순서를 유지하기 위해서 start 변수를 도입해 탐색 범위를 제한했다. 시간 초과가 발생했다. 풀이의 시간 복잡도는 ${n \choose k}$ 인데, n과 k가 최대 100만 까지 가능하기 때문이다. 더보기 DFS 함수의 시간 복잡도 T(dfs) = (n-k) choose (k-1) + (n-k+1) choose (k-1) + ... + n choose (k-1) = (n+1) choos..
2023.03.09 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 섹션이 이미 순서대로 정렬돼 있다. 그래서 앞에서부터(뒤에서부터) 차례로 칠하기만 해도 최소 덧칠 횟수가 만족된다. # N 개의 구역 (1 ~ N 라벨) # M 미터 -> 구역 초과 X # 반복해도 되지만, 최소화해야 함 # 끝에서 부터 확인하면 될 듯 -> 윈도우가 범위 안 넘어가면 색칠 # 순서 유지돼야 함 -> 윈도우 내 최소 값 보다 마지막 성분이 큰 경우 pop() def solution(n, m, section): cnt = 0 # 모든 영역을 다 칠할 때 까지 반복 while..
[Python] 프로그래머스 덧칠하기 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 섹션이 이미 순서대로 정렬돼 있다. 그래서 앞에서부터(뒤에서부터) 차례로 칠하기만 해도 최소 덧칠 횟수가 만족된다. # N 개의 구역 (1 ~ N 라벨) # M 미터 -> 구역 초과 X # 반복해도 되지만, 최소화해야 함 # 끝에서 부터 확인하면 될 듯 -> 윈도우가 범위 안 넘어가면 색칠 # 순서 유지돼야 함 -> 윈도우 내 최소 값 보다 마지막 성분이 큰 경우 pop() def solution(n, m, section): cnt = 0 # 모든 영역을 다 칠할 때 까지 반복 while..
2023.03.06 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 한 번에 최대 2명을 태울 수 있기 때문에, 최적의 구성은 무거운 사람 + 가벼운 사람을 태울 경우다. 무거운 사람, 가벼운 사람의 무게 합이 제한 무게를 넘는지 확인하기 위해서, 무게 순으로 people을 정렬 했다. 정렬 뒤엔 시작 점과 끝 점을 비교하기 위해서 투 포인터를 활용했다. # 한 번에 최대 2명 # 최적 -> 무거운 사람 + 가벼운 사람 def solution(people, limit): people.sort() answer = 0 # 투포인터 시작 - 끝 점 start,..
[파이썬] 프로그래머스 구명보트 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 한 번에 최대 2명을 태울 수 있기 때문에, 최적의 구성은 무거운 사람 + 가벼운 사람을 태울 경우다. 무거운 사람, 가벼운 사람의 무게 합이 제한 무게를 넘는지 확인하기 위해서, 무게 순으로 people을 정렬 했다. 정렬 뒤엔 시작 점과 끝 점을 비교하기 위해서 투 포인터를 활용했다. # 한 번에 최대 2명 # 최적 -> 무거운 사람 + 가벼운 사람 def solution(people, limit): people.sort() answer = 0 # 투포인터 시작 - 끝 점 start,..
2023.02.02 -
문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 박스에 담을 사과 개수가 $m$으로 고정돼 있어 내림차순 정렬만으로도 최대 가격을 설정할 수 있다. 내림차순으로 정렬하게 되면 매번 $m$ 번째 사과의 점수가 전체 사과 상자의 가격을 결정한다. # 점수가 가장 낮은 사과가 가격을 결정 # 따라서 점수가 높은 사과끼리 묶어야 최대 가격 설정 가능 def solution(k, m, score): answer = 0 score.sort(reverse = True) # idx 대소 비교 과정에서 계속 계산되기 때문에 미리 계산 score_len..
[파이썬] 프로그래머스 과일 장수 풀이문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 박스에 담을 사과 개수가 $m$으로 고정돼 있어 내림차순 정렬만으로도 최대 가격을 설정할 수 있다. 내림차순으로 정렬하게 되면 매번 $m$ 번째 사과의 점수가 전체 사과 상자의 가격을 결정한다. # 점수가 가장 낮은 사과가 가격을 결정 # 따라서 점수가 높은 사과끼리 묶어야 최대 가격 설정 가능 def solution(k, m, score): answer = 0 score.sort(reverse = True) # idx 대소 비교 과정에서 계속 계산되기 때문에 미리 계산 score_len..
2023.01.18 -
Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트에서 문제를 확인해주세요. 나의 풀이 앞에 있는 로봇들이 자신의 왼쪽에 위치한 물류 부터 선택하게 하면 결국 최대 로봇 수를 구할 수 있다. import sys line_len, robot_range = map(int, input().split()) line_info = list(input()) count = 0 # 앞에서부터 조회 for idx, obj in enumerate(line_info): if obj == "P": for j in range(idx - robot_range, idx + robot_range + 1): if j line_len - 1: continue elif line_i..
[파이썬] 소프티어 스마트 분류Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트에서 문제를 확인해주세요. 나의 풀이 앞에 있는 로봇들이 자신의 왼쪽에 위치한 물류 부터 선택하게 하면 결국 최대 로봇 수를 구할 수 있다. import sys line_len, robot_range = map(int, input().split()) line_info = list(input()) count = 0 # 앞에서부터 조회 for idx, obj in enumerate(line_info): if obj == "P": for j in range(idx - robot_range, idx + robot_range + 1): if j line_len - 1: continue elif line_i..
2022.05.19