알루 코딩

모각코 두번째 회의 후 PART2. 약점체크를 풀며 준비운동을 했습니다! 확실히 저번주보다는 난의도가 높은 문제들인 것을 체감했습니다. ✏️ 준비운동 PART2. 약점체크 재귀 탐색의 기본: 연산자 끼워넣기 (🥈실버 1티어) 스택의 응용: 괄호의 값 (🥈실버 2티어) 시뮬레이션 기본: 빗물 (🥇 골드 5티어) 완전탐색의 유연한 생각: 가르침 (🥇 골드 4티어) 그리디의 기본: 멀티탭 스케줄링 (🥇 골드 1티어) 투 포인터의 기본: 부분합 (🥇골드 4티어) 벨만포드 뼈대문제: 최소비용 구하기 (🥇 골드 5티어) Prime, Kruskal 뼈대문제: 최소 스패닝 트리 (🥇 골드 4티어) KMP 뼈대문제: 부분 문자열 (🥉 브론즈 2티어) 위상정렬: 줄 세우기 (🥇 골드 3티어) 1. 연산자 끼워넣기 impo..

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

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