투투

문제 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다. 100,000이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자. 입력 첫째 줄에 N과 K를 입력하고 둘 째줄에는 N개의 숫자를 입력한다. N은 1이상 200,000이하, K는 1이상 100이하이다. 출력 조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다. 접근 투 포인터 알고리즘을 공부하기 위해 이 문제를 풀게되었다. 먼저 left와 right가 첫 번째 원소를 가리킨다. ..

https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 접근 최대로 건널 수 있는 사람부터 한 명까지 탐색을 한다. 그리고 건널 수 있는 사람의 명수를 stones에 있는 각각의 숫자와 빼준다. 이때 0이하인 숫자가 K개 이하라면 해당 숫자가 최대로 건널 수 있는 사람의 명 수가 된다. 하지만 stones에 있는 원소는 최대 200,000,000의 수를 갖기 때문에 효율성 테스트에서 통과하지 못할 것이다. 따라서 선형적으로 탐색하는 것이 아니라 이진탐색을 활용한다. 이진 탐색으로 건널 수 있는 사람의 명수를 찾는다. 구현 - le..

https://programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 접근 기지국의 영향을 받지 않는 곳의 크기를 구하고 이를 기지국이 영향을 주는 범위만큼 나눈다. 이제 몫을 올림하여 최종해에 더한다. 기지국의 영향을 받지않는 곳을 봤을 때 (2 * w + 1)로 나누면 필요한 기지국의 개수를 알 수 있다고 판단하였다. 구현 - 먼저 기지국의 범위를 (left, right)의 형태로 ranges에 추가한다. ..

https://programmers.co.kr/learn/courses/30/lessons/42627# 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 접근 힙을 활용했다. job의 시작시간이 특정 시간의 범위 내에 있을 때 힙에 넣는다. 힙에 넣을 때는 작업이 소요되는 시간을 기준으로 넣을 수 있도록 한다. 여기서 힙이 비어있을 때는 시간을 1씩 증가하도록 한다. 구현 - 먼저 지난 시간 last를 -1, 현재 시간 cur을 jobs 중에 가장 빠른 시작시간으로 초기화한다. - 이제 while문을 통해..

접근 두 명의 사용자가 이동을 할 때마다 주위에 충전할 수 있는 충전기를 모두 찾는다. 찾은 후에 성능을 기준으로 내림차순 정렬하여 두 명의 사용자가 최댓값이 되도록 충전기를 선택하도록 한다. 만약 같은 충전기 내에 두 명이 존재하면 배분을 해서 가져가야한다. 하지만 한 명이 다른 충전기 범위 내에도 존재하면 이 사용자는 다른 충전기를 선택하도록 해야한다. 구현 - 사용자 2명의 이동 경로를 move_info에 저장한다. - 충전기의 정보를 charge_info에 저장한다. - 이제 사용자들을 move_info에 기반하여 이동시키고 - 이동시킬 때마다 charge 함수로 위치를 보내서 최댓값으로 충전할 수 있는 양을 구한다. for tc in range(test_case): N = 10 M, A = ma..

https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 접근 대기실 내에서 사람의 좌표를 기준으로 BFS를 진행하고 맨해튼 거리가 2이하인 지원자..

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 접근 전달받은 numbers의 숫자들을 더하거나 빼서 target을 만들 수 있는 경우의 수가 몇 개인지 구해야한다. 따라서 DFS를 통해 모든 경우의 수를 먼저 구했다. 구현 - DFS 내에서 현재 인덱스와 지금까지 합을 더하거나 뺄 때로 나눠서 재귀호출을 진행하였고 - idx가 N이 될 때는 모든 선택이 ..

https://programmers.co.kr/learn/courses/30/lessons/72412 = score): answer.append(N - idx) else: answer.append(0) else: answer.append(0) 전체 코드 from itertools import combinations def binary_search(left, right, target, numbers): while left < right: mid = (left + right) // 2 if numbers[mid] < target: left = mid + 1 else: right = mid return right def solution(info_list, query): answer = [] table = di..

문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다. 접근 가장 긴 증가하는 부분 수열의 문제를 이분 탐색으로 풀면서 출력되는 부분 수..

https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 접근 딕셔너리를 활용하였다. 먼저 각 손님들이 주문한 메뉴를 통해 만들 수 있는 코스 조합을 생성한다. 이 때 코스에 포함되는 메뉴의 수가 주어지기 때문에 해당 수만큼 메뉴가 포함된 조합을 생성한다. 이후 생성된 코스 조합을 딕셔너리에 key로 저장하고 value에는 해당 코스 조합의 개수를 저장한다. 이제 course의 들어있는 코스에 포함된 메뉴의 개수들 중 ..