본문 바로가기

분류 전체보기

 (435)
[이분탐색] 난이도1.5, Amazon 인터뷰 '고정점 찾기' (Python) 고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를 들어 수열 a={-15,-4,2,8,13}이 있을 때 a [2]=2이므로, 고정점은 2가 됩니다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 고정점은 최대 1개만 존재합니다. 만약 고정점이 없다면, - 1을 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받는다. 첫째 줄에 N이 입력됩니다. (1
[이분탐색] 난이도1.5, 이취코 197p '부품 찾기' (Python) 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N=5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M=3 [5, 7, 9] 이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다. 첫째 줄에 정수 N이 주어진다. (1
[완전탐색] 프로그래머스 L2 '소수 찾기' (Python) https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 종이 조각으로 여러 개의 조합을 만들어야 하므로 itertools 라이브러리 사용 중복된 숫자가 나올 수 있으므로 set() 사용 소수는 에라토스테네스의 체 공식으로 찾음 from itertools import permutations from math import sqrt def solution(numbers): s = set() for i in ..
[완전탐색] 프로그래머스 L1 '모의고사' (Python) https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 반복문 사용. 패턴을 answers 길이에 맞춤. 문제가 1개~10,000개일 경우 계산 채점할 수 있는 변수 필요. 가장 많이 맞춘 사람 걸러내기 #1차 시도 --> 몇개의 테스트케이스 실패 def solution(answers): answer = [] a1, a2, a3 = [],[],[] j=1 for i in answers: if i==j: a1.appe..
[알고리즘] 완전탐색(순차탐색)/이분탐색(이진탐색) 완전 탐색(=Brute Force) / 순차 탐색(=Sequential Search) 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색하는 효율성 관점에서 최악의 방법 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 시간 복잡도 : O(N) = 선형 복잡도 = 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것 [반복문] def solution(trump): for i in range(len(trump)): if trump[i]==8: return i return -1 def sequential_search(n, target, array): for i in range(n): if array[i] == target: return i+1 ..
[큐] 프로그래머스 L2 '다리를 지나는 트럭' (Python) https://programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 programmers.co.kr Queue 사용 def solution(bridge_length, weight, truck_weights): Q = [0] * bridge_length total_weight = 0 time = 0 while truck_weights: total_weight -= Q.pop(0) if total_weight + truck_weights..
[큐] 프로그래머스 L2 '기능개발' (Python) https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 100이 될 때까지 while문? speeds를 100이 될 때까지 더하는 for문? progresses가 100이 되면 answer +=1 하고 순서대로 삭제 #1차시도 : 1,5 런타임에러, 2 실패 def solution(progresses, speeds): queue = [] finish = [] for i in range(len(progresse..
[스택] 프로그래머스 L2 '주식가격' (Python) https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr prices의 길이만큼 시간이 지남 스택으로 사용할 타이머 생성 #1차시도 : 2,3,4,5,6,7,8,9,10 & 효율성테스트 실패 def solution(prices): stack = [0] answer = [0] * len(prices) for i in range(1,len(prices)): if prices[i] ..
LIST

티스토리툴바