알루 코딩

처음에 문제 이해를 제대로 못해서 애먹었던 문제다. 처음에 이해한 로직은 이렇다. N개의 센서가 있을 때, K개의 집중국을 설치해야 한다. 각 집중국은 센서의 수신 가능역역을 조절하는데, 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하면 됐다. 그러면, N개의 센서의 위치가 주어지면, 우선 그 위치를 오름차순으로 정렬한다음에, "하나의 집중국과 센서의 거리가 최소가 되려면" 평균거리로 접근하면 되는 줄 알았다. K개의 집중국을 설치해야 하므로, 평균적으로 N//K 마다 집중국을 설치하고자 했다. 말로 설명하려니까 이해가 안될 수 있으므로 그림으로 설명해보겠다. 예제 입력1을 기준으로 이해한 그림은 아래와 같다. 이렇게 하면, 예제 입력 1은 만족하는 듯 보였다. 예제 입력 2를 살펴보자. 결과가 ..

차근차근 문제에서 주어진 로직을 풀어보면, 그다지 어렵지 않은 문제였다. 문제의 로직은 따로 설명하게 없을 정도로, 문제에서 주어진 대로 그대로 구현하면 다들 풀 수 있을 것이다. 처음 입력받는 N과 M은 각각 '주차장 공간의 수'와 '차량의 수'이다. 모든 차량은 한 번씩 주차장에 들어갔다가 나오므로 (차량의 수 *2) 만큼의 출입 순서를 입력받아야 했다. 우선 index오류를 막기 위해, '요금을 나타내는 리스트'와 '각 차량의 무게를 나타내는 리스트'를 빈 리스트 [] 가 아닌 [0]으로 시작했다. 들어오는 출입 순서를 덱으로 큐화 시켰다. popleft()를 쓰기 위함이다. 이 출입리스트가 빌 때 까지, 계산을 반복한다. 이 문제에서 생각해야 할 관건은 크게 2가지만 생각해주면 됐다. 주차 가능한..

일단, 나도 처음에 틀렸던 문제다. 그리디 문제로 접근을 했었고, 문제를 풀었는데, '예제 입력 5' 와 같은 반례에 부딪혔다. 나의 로직은 이러했다. 문제에서 1번 사람부터 N번 사람까지 순서대로 잃는 체력리스트와 얻는 기쁨 리스트를 입력받는다. 세준이가 얻을 수 있는 최대 기쁨을 출력하는 것이므로, [hp(체력), joy(기쁨)]을 쌍으로 갖는 새로운 리스트를 만든 후에, joy(기쁨)을 기준으로 내림차순 정렬을 한다. 그러면, 큰 joy(기쁨)를 가지는 쌍이 앞에 오겠고 해당하는 hp(체력)을 초기 HP(100)에서 빼가면서 음수나 0이 아니면, 해당 joy(기쁨)을 그대로 더해주면서 for문을 순회하도록 로직을 짰다. 처음에 짠 로직은 아래와 같다. import sys input = sys.std..

작년에 풀었던 문제인데, 제대로 이해를 하지 않고 넘어갔었던 느낌이 들어 다시 풀어본 문제이다. 거의 기억이 안나서 새로 푼 문제나 다름이 없었는데, 총 3번의 시련을 겪었다. 가장 먼저, 잘못된 로직으로 문제를 풀어나가기 시작했다. 예를 들어, 입력값이 3 1 98 98 99 99 100 이 주어졌다고 하면, 답은 어떻게 나올까? 답은 3이 나와야 한다고 생각한다면, 나와 똑같은 실수를 한 셈이다. 답은 1이 나와야 한다. 1~98 , 98~99, 99~100 이렇게 겹치지 않고, 1강의실만을 이용해서 강의를 배정할 수 있기 때문이다. 첫 번째 시련을 겪고, 빠르게 로직에 대해서 생각해봤다. 대충 로직은 이러했다. 입력 받은 "강의가 시작되는 시간"과 "강의가 끝나는 시간"을 강의 리스트를 (강의 시작..

순차 탐색 이진탐색 알고리즘을 배우기 전에 가장 기본 탐색 방법인 순차 탐색 방법에 대해 알아보자. 순차 탐색이란, 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례로 확인하는 방법이다. 말그대로, 순차적으로 탐색을 한다는 의미인데, count() 함수를 이용할 때도 내부에서는 순차 탐색이 수행될 정도로 자주 사용된다. N개의 데이터에서 최대 N번의 비교 연산이 필요하므로 순차 탐색의 시간복잡도는 최악의 경우, O(N)이다. 순차 탐색 코드는 아래와 같다. import sys input = sys.stdin.readline # 순차 탐색 소스코드 구현 def sequential_search(n,target,array): # 각 원소를 하나씩 확인하며 for i in range(..