남남이루의 고군분투 🌳

문제 [프로그래머스 전화번호 목록] 주어진 전화번호 목록에서, 어떤 번호가 다른 번호의 시작번호가 되는 지를 판단해라. 시작번호를 가지는 전화번호 목록이라면 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 함수 나는 계산식까지는 알았는데 이를 코드로 딕셔너리를 이용해 구현하는 방법을 몰랐다. 아래 참고한 코드..

문제 링크 보석 사이의 함정, 경보장치를 고려해 최대 가치의 보석을 구해라 함정 : 보석 줍다가 뒤로 못가 경보 : 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/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: # 몬스터 만남 ..

문제 문제 해석 n개의 집들에, c개의 공유기를 설치하고자 한다. 한 집에 하나씩 설치하고, 가장 멀리씩 설치할 때 가장 인접한 거리로 설치된 간격을 출력하라. 주요 변수 low, high : 탐색 범위 * high는 집의 끝과 끝에 설치했을 때가 가장 멀고, 공유기의 개수가 가장 적게 설치될 때의 간격인데 문제 조건에서 공유기가 2개 이상 주어진다고 했기 때문에 high는 양 끝집을 설치했을 때보다 길 수 없다. idx : 직전에 설치된 집의 좌표 mid : (띄워야 하는) 공유기의 최소 간격에 대한 변수 최종 코드 # 집 n개 # 공유기 c개 # 한 집에 하나, 가장 멀리씩 설치 max d import sys input = sys.stdin.readline n,c = map(int, input().s..

문제 바로가기 문제 해석 n개의 랜선 만들어야 함 이미 k개 있음 같은 길이로 만들자 최대 길이는? : 가지고 있는 랜선을 같은 길이로 잘라서 n개로 만들 것이다. n개는 고정인데, 길이를 가장 길게 한다면 그 값은 무엇일까? 주요 변수 다른 이분탐색처럼 low와 high로 탐색의 범위를 정한다. 문제의 조건에서 k