Little cabin in the woods

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/2012📌 문제 탐색하기목표각 사람의 예상 등수가 주어졌을 때, 불만도의 합을 최소가 될 때의 불만도 출력하기입력[첫 줄] 사람 수 N (1 ≤ N ≤ 500,000)  [둘째 줄] 각 사람의 예상 등수 (500,000 이하의 자연수)출력불만도의 합을 최소로 할 때, 그 불만도 출력하기해야 할 것불만도의 합이 최소가 되는 규칙 찾기아이디어1. 불만도의 합이 최소가 되는 규칙 찾기 불만도 = (예상등수 - 실제등수) 의 절대값이다.일단, 하나씩 모든 경우를 다 해보는 방법을 떠올릴 수 있다. 이 경우 N개의 등수를 N개의 자리에 배열하는 경우의 수이므로 N!의 연산이 필요하다. 하지만 N의 최대값이 5*10^5 이므로..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/25305 📌 문제 탐색하기목표상을 받는 사람들 중 점수가 가장 낮은 사람의 점수 출력하기해야 할 것N명의 학생 중 점수가 가장 높은 k명 추출하기추출된 k명 중 가장 점수가 낮은 학생의 점수 출력하기입력N : 응시자 수 ( 1≤N ≤1000)k : 상을 받는 사람의 수 ( 1≤k ≤N ) 둘째 줄부터 : 학생의 점수 x 출력 ( 0≤x≤10000 )아이디어N명의 점수를 내림차순으로 정렬한다. ➡️ 시간 복잡도가 O(nlogn) 이고, N의 범위가 10^3 이니까 충분하겠다.k 번째에 있는 사람의 점수를 출력하자.📌 코드 설계하기1. N명의 점수를 리스트로 저장하고, 내림차순 정렬한다. (sort함수 사용)2. k-..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/10814 📌 문제 탐색하기목표회원들을 조건에 맞게 정렬하여 출력하기해야 할 것회원들을 나이를 기준으로 오름차순으로 정렬하기나이가 같을 경우, 먼저 가입한 사람이 앞에 오도록 정렬하기입력N : 회원의 수 ( 1 ≤ N ≤ 100,000 )둘째 줄 부터 : 회원의 나이, 이름 ( 1 ≤나이 ≤ 200 , 이름의 길이 ≤ 100 )입력되는 순서가 곧 가입한 순서이다.아이디어입력 값의 범위가 10^4 이므로 O(nlogn) 이하의 시간복잡도를 가지는 알고리즘을 사용해보자.먼저 가입한 사람을 어떻게 저장할까?리스트로 데이터를 받고, 인덱스 값으로 가입한 순서를 판별하자.sort()를 사용해서 정렬할 때, 나이가 같으면? 자동..

이번에 풀어 볼 문제는 다.https://www.acmicpc.net/problem/2309  📌 문제 탐색하기목표키의 합이 100이 되는 난쟁이 7명 찾기가능한 정답이 여러 가지인 경우에는 아무거나 출력해야 할 것9명의 난쟁이 중 7명을 그룹으로 묶기7명의 키의 합이 100이 되는 그룹 찾기입력총 9줄에 걸쳐 난쟁이의 키가 주어진다.난쟁이의 키는 모두 다르다.아이디어입력 값의 개수가 9개로 고정되어 있기 때문에 가능한 모든 조합을 모두 계산해보아도 시간초과가 발생하지 않겠다.더할 7개를 선택하는 것보다 뺄 2개를 선택하는 것이 탐색할 경우의 수가 적어 효율적으로 보인다.📌 코드 설계하기1. 배열을 생성하고 난쟁이들의 키를 저장한다.2. 현재 9명의 난쟁이들의 키 합을 계산한다.3. 첫 번째 원소부..

오늘 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/5635 📌 문제 탐색하기목표생일을 보고 가장 나이가 적은 사람과 가장 나이가 많은 사람을 출력하기해야 할 것가장 나이가 적은 사람 찾기가장 나이가 많은 사람 찾기입력n : 학생 수 ( 1 ≤ n ≤ 100 )둘째 줄 부터 : 문자열 , "이름 dd mm yy" 형식아이디어생일을 어떻게 비교하지?먼저 연도를 비교, 연도가 같으면 월을 비교, 월이 같으면 일을 비교[ 연도, 월, 일 ] 형식으로 저장하고 정렬하면 원하는 우선순위대로 비교가 가능하다이름이 같거나, 생일이 같은 사람은 없다고 했으니 [ 연도, 월, 일, 이름 ] 형식으로 저장하고 정렬해도 이름까지 정렬되지 않고 생일을 기준으로만 정렬이 완료되겠다.📌 코드..

더보기눈높이 개발 코딩테스트 챌린지 5기에 참여했다. (https://litt.ly/whydevsaysno)첫 이틀은 놓쳤지만 앞으로 꾸준히 참여해 볼 예정이다. 알고리즘 관련 공부가 부족한 상황이라 시간 내에 풀지 못하고 한 문제마다 한참 헤매고 있지만.. 하다 보면 늘겠지.. 오늘 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/1181 📌 문제 탐색하기목표단어를 조건에 맞게 정렬하여 출력하기해야 할 것길이가 짧은 순으로 정렬길이가 같을 경우는 사전 순으로 정렬중복된 단어는 하나만 남기고 제거하기입력N : 단어의 개수 ( 1 ≤ N ≤ 20,000 )둘째 줄 부터 : 문자열 ( 길이는 50 이하 )아이디어N의 범위가 20,000 개이니까 시간복잡도가 O(n^2) 의 경..