남남이루의 고군분투 🌳

문제 링크 옷의 조합 수를 구하는 문제였다. 원소가 한 개 이상인 조합을 하되, 카테고리별로 하나씩만 선택할 수 있는 조건이다. 카테고리가 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 을 기준으로 창구별 대기시간의 몫) 의 합이 이미 볼 일..

문제링크 참고링크 https://goodsosbva.tistory.com/m/37?category=454008 https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=221432986308&proxyReferer=https:%2F%2Fwww.google.com%2F https://velog.io/@chang626/11662-%EB%AF%BC%ED%98%B8%EC%99%80-%EA%B0%95%ED%98%B8 백준 11662번 - 민호와 강호 출처 : 11662번: 민호와 강호 (acmicpc.net) 11662번: 민호와 강호 민호와 강호가 2차원 좌표 평면 위에 있다. 민호는 점 A(Ax, Ay)에서 점 B(Bx, By)를 향해 걸어가고 있고, 강호는 점 ..

문제 https://www.acmicpc.net/problem/10815 숫자가 카드안에 있는지 탐색하는 문제다. 문제조건에 두 숫자 배열의 크기가 50만이 넘기 때문에 find나 filter나 완전탐색으로 하면 시간초과가 뜨기 때문에 업다운 게임처럼 이분탐색으로 힌트를 줌으로써 탐색범위를 효과적으로 줄여야 한다. 코드 n = int(input()) card = list(map(int, input().split())) m = int(input()) nums = list(map(int, input().split())) def binary(mid): return card[mid] card.sort() ans = [] for i in nums: l = 0 r = n-1 j = 0 while l i: r = m..

문제 바로가기 https://www.acmicpc.net/problem/15732 문제 이해하기 주요 변수 import sys sys.stdin = open('.//이분탐색//input2.txt', 'rt') n,k,d = map(int, input().split()) rules = [list(map(int, input().split())) for _ in range(k)] # print(n,k,d) # print(rules) def dotori(mid): total = 0 for s, e, step in rules: beta = min(e, mid) if s

문제 링크 드래곤이랑 용사랑 싸울 건데, 용사가 이기기 위해 필요한 최소한의 hp가 얼마인가요? 1 try import sys sys.stdin = open('.//이분탐색//input2.txt', 'rt') n, yp = map(int, input().split()) # n 방 개수 # pw 초기 공격력 print(n,yp) # t a h # t = 1 몬스터, a 공격력, h 생명력 # t = 1 용사, a 공격력 증가, h 생명력 증가 g = [ list(map(int, input().split())) for _ in range(n)] def war(yp,yh): mp = 0 mh = 0 mid = yh for l in g: a = l[1] h = l[2] if l[0] == 1: # 몬스터 만남 ..