본문 바로가기

알고리즘

 (138)
[대회][BOJ][INU 코드페스티벌 2020] D번 20364 : 부동산 다툼 문제를 정리해보자. 1. 루트 땅의 번호는 1이다. 2. 어떤 땅의 번호가 K라면, 왼쪽 자식 땅의 번호는 2 x k, 오른쪽 자식 땅의 번호는 2 x (k + 1)이다. 1. 오리들은 한 줄로 대기시킨다. 맨 처음 오리들은 1번 땅에 있다. 2. 오리들이 서 있는 순서대로 원하는 땅을 가지도록 한다. 3. 오리가 원하는 땅까지 가는 길에 이미 다른 오리가 점유한 땅이 있다면 지나가지 못한다. 이 경우 처음 마주치는 점유된 땅의 번호를 출력한다. (지나가는 길에는 오리가 원하는 땅도 포함이다.) 4. 오리가 원하는 땅까지 간다면 0을 출력한다. 오리의 번호가 아래 식으로 루트 노드까지 간다. import sys input = sys.stdin.readline N, Q = map(int, input().s..
[대회][BOJ][INU 코드페스티벌 2020] C번 20363 : 당근 키우기 문제를 정리해보자. 1. 햇빛 1번은 온기 +1 2. 햇빛 10번은 온기 +10, 수분 -1 3. 물 1번 수분 +1 4. 물 10번 수분 +10, 온기 -1 수분과 온기는 음수가 될 수 없다. x, y = map(int, input().split()) if x < y: x, y = y, x print(x + (y // 10) + y) # y < x 이 문제는 처음에 얼마나 많은 햇빛 혹은 물은 주느냐가 관건이다. 예를 들어, 온기=10, 수분=10을 만들어야 한다고 하자. 최소한의 횟수로 만든다면 아래처럼 된다. 총 21회이다. 횟수/이름 온기 수분 1 0 0 2 10 0 3 9 10 4 10 10 하지만 다르게 생각해보자. 햇빛을 충분히 주어서 온기가 10보다 작은 상태를 만들지 않는다면 어떨까? 횟..
[대회][BOJ][INU 코드 페스티벌 2020] 후기 며칠 전 INU 코페 2021 대회에 참가 신청했고, 오늘 INU 코페 2020 문제를 풀어봤다. A~H번, 총 8문제가 출제되었다. 식사, 쉬는 시간까지 포함해서 약 6시간 풀었다. A, B, C, D, E번은 맞았고, F번은 틀렸다. G, H번은 접근하지 못했다. C, E는 쉬운 문제였다. 하지만 단순하게 생각하지 못하는 바람에 오래 걸렸다. B번은 시간 초과가 걱정되는 풀이로 해결했다. 왜 시간 초과가 안 났는지는 더 생각해볼 문제 같다. F번은 백 트래킹을 이용해서 풀었다. 하지만 시간 초과 문제를 해결하지 못해서 틀렸다. G, H번은 나중에 실력이 되면 풀어야겠다. (오늘 푼 문제 풀이는 따로 올렸다.) 교내 알고리즘 대회.. 아직 실력이 많이 부족하지만, 경험을 쌓기 위해 나간다. 선배들을 제..
[프로그래머스][Python] 프린터 순서도가 높은 인쇄 문서부터 인쇄하면 된다. 요청한 문서가 몇 번째로 인쇄되는지 구하는 문제이다. # A, B, C, D # 2 1 3 2 import collections def solution(priorities, location): priorities_cnt = dict((collections.Counter(priorities).items())) priorities_idx = [(num, idx) for idx, num in enumerate(priorities)] location = (priorities[location], location) answer = 0 while priorities_idx: check = priorities_idx[0][0] if check == max(priorities..
[프로그래머스][Python] 기능개발 문제를 정리해보자. 1. 각 기능은 진도가 100%일 때, 서비스에 반영한다. 2. 각 기능의 개발 속도는 모두 다르다. 3. 뒤에 개발이 먼저 완료되어도, 앞에 기능이 배포될 때 함께 배포해야 한다. 배포 순서대로 작업 진도 적힌 배열 : progresses 각 작업의 개발 속도 적힌 배열 : speeds 문제는 '배포마다 몇 개의 기능이 배포되는지' 찾는 것이다. def solution(progresses, speeds): answer = [] while progresses: progresses = list(map(lambda x1, x2: x1 + x2, progresses, speeds)) result = 0 while progresses: if 100
[프로그래머스][Python] 베스트앨범 문제를 정리해보자. 노래를 수록해야 한다. 그 기준은 아래와 같다. 1. 속한 노래가 많이 재생된 장르를 먼저 수록한다. 2. 장르 내에서 많이 재생된 노래를 먼저 수록한다. (재생 횟수가 같다면? 고유 번호가 낮은 노래를 먼저 수록한다.) 1번과 2번을 위한 딕셔너리를 각각 만들었다. 전자는 genres_sum, 후자는 genres_two_plays. 1번은 각 장르의 노래 재생 수를 다 더하면 된다. 2번은 조건문을 이용했다. 아래 예시로 설명하겠다. classic은 500, 150, 800을 가지고 있다. 그리고 pop은 600, 2500을 가지고 있다. classic은 800, 500, 150 순서가 되어야하고, 2개만 선택해야 하니까 800, 500만 남아야 한다. 따라서 재생 수가 높은 순으로..
[프로그래머스][Python] 위장 조합을 이용했다. (조합은 서로 다른 n개에서 순서에 상관없이 r개를 선택하는 것이다.) 예를 들어보자. 2개의 모자 종류와 1개의 안경은 종류가 있다. 아래와 같이 경우의 수를 구할 수 있다. 문제에서 '스파이는 하루에 최소한 한 개의 의상은 입습니다'라고 했다. 따라서 아무것도 안 입는 경우를 제외시켜야 한다. 빨간색으로 표시한 부분이 그 부분이다. (Π (의상 종류 + 1)) - 1 식은 이와 같다. def solution(clothes): dic = {} for li in clothes: c, k = li if dic.get(k, 0): dic[k] += 1 else: dic[k] = 2 answer = 1 for val in dic: answer *= dic[val] return answer -..
[프로그래머스][Python] 전화번호 목록 백준에서 트라이로 푼 문제이다. 이번엔 다른 사람 풀이를 분석해보자. def solution(phoneBook): phoneBook = sorted(phoneBook) for p1, p2 in zip(phoneBook, phoneBook[1:]): print(p1, p2) if p2.startswith(p1): return False return True print(solution(["12", "1235", "567", "88"])) 내장 함수에 대해 알아보자. 1. zip 순회할 수 있는 객체들을 받는다. 각 객체가 가지고 있는 원소를 Tuple 형태로 차례로 접근할 수 있는 반복자를 반환한다. (반복자란 내부의 요소를 순회하는 객체이다.) 2. startswith(시작 문자, 시작 지점) 문자열이 특..
[프로그래머스][Python] 완주하지 못한 선수 완주자의 이름을 key로 인원수를 value로 잡고, c_dic에 저장했다. 그리고 참가자 이름을 하나씩 꺼내서 비교했다. key에 해당 참가자 이름이 없거나 value에 해당 참가자 수가 0명이면, 그 사람은 완주하지 못한 참가자이다. def solution(participant, completion): c_dic = {} for key in completion: if not c_dic.get(key, 0): c_dic[key] = 1 else: c_dic[key] += 1 for key in participant: if (not c_dic.get(key, 0)) or c_dic[key] == 0: return key else: c_dic[key] -= 1 입력으로 'Hello'가 들어왔을 때, 'H'..
[BOJ] [Python] 5052 : 전화번호 목록 하나라도 문자열 전체가, 다른 문자열과 겹친다면 NO를 출력한다. (아니면 YES.) 트라이를 이용해서 해결했다. 주의해야 할 점은 '911', '91125426'과 같은 입력이 같이 들어올 때이다. 1. '91125426'이 먼저 들어오고 그 후에 '911'이 들어온다. search 함수에서, '911'이 트라이를 돌면서 문자열 전체가 겹친다면 True를 반환한다. 2. '911'이 먼저 들어오고 그 후에 '91125426'이 들어온다. search 함수에서, '91125426'이 트라이를 돌면서 data가 None이 아니라면 어떤 문자열과 겹치는 것이다. True를 반환한다. 1, 2가 모두 해당이 안 된다면 insert 함수를 실행시켜, 문자열을 트라이에 넣어준다. import sys class N..

티스토리툴바