남남이루의 고군분투 🌳

문제 숫자로 이루어진 배열을 조합해 가장 큰 수를 만들어라 주의 from itertools import combinations, permutations 순열이나 조합을 그대로 사용하면, 시간초과가 뜬다. 결정적인 차이 내코드 numbers.sort(key=lambda x: str(x), reverse=True) >>> [9, 5, 34, 30, 3] sorting 키를 사전순으로 함. 참고코드 nums_s.sort(key=lambda n : n*3, reverse=True) 참고 블로그 >>> [9, 5, 34, 3, 30] sorting 키를 x3한 숫자의 사전순으로 함. 3이 30보다 먼저 나와야 330 > 303 으로, 더 큰 수를 만들기 위한 정렬이다. *3 (곱하기 3) 이 왜 필요하냐면, 10..

문제 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요. 시간 초과를 주의해야 한다. 내 코드 import heapq as hq def solution(article): answer = 0 hq._heapify_max(article) # 내림차순 정렬 h = 0 for h in range(article[0]): # 가장 큰 값 기준으로 반복문 돌기 cnt = 0 for i in article: if i >= h: cn..

문제 스코빌 지수를 K이상으로 만들고 싶어서, 스코빌 낮은 음식을 더 맵게 만들기 위해 가장 맵지 않은 음식이랑 그다음으로 안 매운 음식*2 를 섞어서 새로운 음식을 만들거야. 모든 음식의 스코빌지수가 K이상이 될 때까지 반복한다면, 몇 번 섞어야 하니? [https://programmers.co.kr/learn/courses/30/lessons/42626] 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr heappop(배열) : 제일 작은 원소 꺼내기 heappush(원소, 배열) : 원소 넣기..

문제 [프로그래머스 전화번호 목록] 주어진 전화번호 목록에서, 어떤 번호가 다른 번호의 시작번호가 되는 지를 판단해라. 시작번호를 가지는 전화번호 목록이라면 false, 반대라면 true 를 반환해라. 교훈 해쉬 테이블의 효율성 해쉬는 자료를 검색하는 데 정말 빠르다고 한다. 배열과 비슷한 역할을 하도록 해도, 키 값에 접근하는 것이라면 해시가 더 빠름을 알 수 있었다. (ex. i in list vs i in dictionary) 또한, 이것처럼 중복 검색을 위해 dictionary 자료형을 임의로 생성하는 코드 형태를 엿볼 수 있었다. prefix 검색에 대해, ((마지막 최종코드 참고)) if prefix in dic 접두사를 찾는다고 하면 접두사인 번호를 먼저 넣고 검색해야겠다고 접근하게 되는데,..

문제 링크 옷의 조합 수를 구하는 문제였다. 원소가 한 개 이상인 조합을 하되, 카테고리별로 하나씩만 선택할 수 있는 조건이다. 카테고리가 0,1,2 인 옷들을 입력 받았을 때 각 카테고리별로 2가지, 2가지, 1가지라면, 00 11 2 로 표현할 수 있다. 이때 1개 이상을 고르는 조합이다. 문자열을 따로 받을 필요없이 (3₩3₩2-1)만 구하면 된다. 이 식은 각 카테고리의 옷 수 +1 을 곱해서 1을 빼주는 것이다. 옷 수 +1 을 해주는 이유는 해당 카테고리에서 아무것도 선택하지 않는 가지수를 포함시켜주기 위함이고, -1 은 전체에서 아무것도 선택하지 않는 것을 빼주는 것이다. 회고 count 함수 나는 계산식까지는 알았는데 이를 코드로 딕셔너리를 이용해 구현하는 방법을 몰랐다. 아래 참고한 코드..

해시함수는 해시함수는 문자열에 대해 숫자를 할당함으로써 일정 문자열을 입력했을 때, 값을 빠르게 반환하는 특징을 가지고 있다. (like 유능한 비서!) 문자열(키)로 값이 저장된 위치를 정확하게 알려주기 때문에 탐색을 할 필요가 없다. 그렇기 때문에 중복되는 키는 사용할 수 없다. 또한 중복을 확인하는 것도 array(배열)에 비해 훨씬 빠르다. 해시함수는 웹의 주소에 IP를 할당하는 작업인 DNS 확인 작업이나, 웹사이트 정보를 잠시 저장했다가 알려주는 캐싱에도 로딩 시간을 효과적으로 줄여줌으로써 유용하게 쓰인다. 따라서, 아래와 같은 때에 유용하다. 어떤 것을 다른 것과 연관시키고자 할 때 무언가를 찾아보고자 할 때 파이썬에서는 딕셔너리{} 가 해시테이블에 해당한다. 해시함수는 배열의 크기가 얼마나..

문제 링크 보석 사이의 함정, 경보장치를 고려해 최대 가치의 보석을 구해라 함정 : 보석 줍다가 뒤로 못가 경보 : m개 이상을 연속으로 주워야 빠져나올 수 있음 => 보석 줍기 시작하면 m개 이상 주워야 함 import sys input = sys.stdin.readline n,m = map(int, input().split()) dia = [0]+[int(input()) for _ in range(n)] dp = [0]*(n+1) for i in range(1,n+1): tot += dia[i] if 0

보호되어 있는 글입니다.

문제 https://www.acmicpc.net/problem/10211 최대 합을 가진 연속 부분집합 구하기. 주의할 점은, 그냥 합이 큰 부분집합아니고 연속 집합이어야 한다는 점..! 핵심 코드 i 인덱스까지 왔을 때, 끊고 가는게 크냐, 합이 크냐. dp[i] = max(dp[i-1] + x[i] , x[i]) 최종적으로 dp중에 max 찾아주면 가장 큰 부분집합의 합이 들어있는 value를 찾을 수 있다. 참고 원소 합이 가장 컸을 때를 구하기만 하면 되는 거면 dp[i] = max(dp[i-1] + x[i] , dp[i-1]) 을 통해 i 인덱스의 값을 합에 포함할 지 아닐지를 판단해주면 된다. 근데 위 문제는 앞에 달린 애들을 버릴거냐 말거냐이다.. 한끝 차이네. 최종 코드 t = int(in..

문제 https://programmers.co.kr/learn/courses/30/lessons/43238?language=python3 문제요약 n 명의 사람들이 대기하고 있다, list에는 창구별 대기시간이 주어진다. 사람들이 볼일을 다 보는 시간은 언제일까요? 풀이 어제 푼 도토리랑, k번째 숫자를 생각하며 하나씩 추가하는 관점이 아니고 그 시간이 됐을 때 몇 명이 빠졌을까를 생각해보니 답을 추론할 수 있었다. 6명이 대기하고 있다면, 6명이 다 빠졌을 시간을 구하는 것이다. n = 6, w = [7,10] 예를 들어, 7분이 됐을 때는 1명이 볼 일을 다 본 상태일 것이고 10분이 됐을 때는 2명이 볼 일을 다 봤을 것이다. 즉 ( time 을 기준으로 창구별 대기시간의 몫) 의 합이 이미 볼 일..