백준 write-up/정렬 & 그리디 (84) 썸네일형 리스트형 [백준] 행복 유치원 : 13164번 - Python https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 문제의 접근 방법 - 인접한 두 사람의 키의 차이를 비교하기 - N명의 사람을 K조로 나누었기 때문에 (N-K)까지의 키 차이를 더하기 내가 막혔던 부분 N명의 사람을 K개의 조로 나누었다는 생각을 못하고, 무조건 인접한 두 사람들의 키 차이가 가장 최소 비용을 산출해낼 수 있다고 생각함. (그래서 두 사람을 한 조에 넣으려고 함) N,K = map(int, input()... [백준] 생일 : 5635번 - Python https://www.acmicpc.net/problem/5635 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 문제의 접근 방법 - 가장 나이가 많은 사람과 적은 사람을 어떻게 정렬할 수 있을지 - 여러 개의 값을 입력 받아 리스트에 저장하기 내가 막혔던 부분 나이가 많은 사람이라는 것은 내림차순으로 정렬했을 때, 가장 첫 번째 인덱스 값을 의미하고 나이가 적은 사람이라는 거슨 오름차순으로 정렬했을 때, 가장 첫 번째 인덱스 값을 의미한다. 문제 풀이 방법 n명의 학생을 의미하는 n값 입력 받기 -> 나이가 많은 순서대로, 적은 순서대로 정렬할 수 있게 빈 리스트 두 개 arr1, a.. [백준] 동일한 단어 그룹화하기 : 16499번 - Python https://www.acmicpc.net/problem/16499 16499번: 동일한 단어 그룹화하기 첫째 줄에 단어의 개수 N이 주어진다. (2 ≤ N ≤ 100) 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 10을 넘지 않는다. www.acmicpc.net 문제의 접근 방법 단어를 알파벳 단위로 분리해서 정렬한 후 비교하기 -> 먼저 입력받은 문자를 알파벳 단위로 분리해서 정렬하여 저장한 후, 그 분리된 알파벳들을 합쳐서(join) 미리 선언해 둔 빈 리스트 arr에 없다면 추가해주기 ( 이미 입력받은 문자열을 정렬했기 때문에 만약 값이 같다면 arr에 추가하지 않고 넘어가게 되므로, 각기 다른 문자열들만 저장되게 된다 = 단어가 ar.. [백준] 비트 우정지수 : 12782번 - Python https://www.acmicpc.net/problem/12782 12782번: 비트 우정지수 진홍이는 숫자를 좋아한다. 오늘도 숫자를 가지고 놀던 진홍이는 두 숫자의 비트 우정지수를 구해보았다. 비트 우정지수란, 10진법으로 나타낸 두 정수를 이진수로 나타내었을 때, 두 숫자를 같 www.acmicpc.net 문제의 접근 방법 - 이진수 n과 이진수 m을 문자 하나씩 비교해서 문자가 다를 경우를 체크해주기 - n이나 m 둘 중 하나를 기준점으로 삼아서 문자가 다를 경우에 그게 0인지 1인지 체크해서 총 몇 개인지 계산해주기 - 그 두 값중 더 큰 수가 바로 최소 연산횟수! 내가 막혔던 부분 - 기본적인 아이디어를 생각하지 못했음. 내가 생각한 아이디어: 두 수가 같지 않으면 무조건 한 번은 바꿔야 하.. [백준] 이장님 초대 : 9237번 - Python https://www.acmicpc.net/problem/9237 9237번: 이장님 초대 입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000) www.acmicpc.net 문제의 접근 방법 - 묘목을 구입한 날이 1일: 1부터 시작함을 명심한다. - 묘목 하나를 심는데 걸리는 시간이 1일이기 때문에 다음 묘목을 심을 때는 1씩 늘어난다는 것을 유의. - 이장님은 묘목이 다 자란 후 오시기 때문에 1일이 또 추가됨을 안다. 문제 풀이 방법 심을 묘목의 개수 n개 입력 받기 -> n개의 묘목이 자라는데 걸리는 일수 입력받기 -> 리스트 day.. [백준] 사과나무 : 19539번 - Python https://www.acmicpc.net/problem/19539 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 문제의 접근 방법 - 두 물뿌리개는 반드시 동시에 사용해야 함. 1) 한 나무에 두 물뿌리개를 사용하는 방법 (3만큼 자람) 2) 각각 다른 나무에 사용하는 방법 (1만큼/2만큼 자람) 3) 나무가 없으면 물뿌리개를 사용할 수 없음 (0) 결론1 : 각 나무의 높이들을 더한 값이 무조건 3의 배수가 되어야 함!!! => 어떻게 물을 뿌리든 두 물뿌리개를 동시에 사용하기 때문에 한 번 물을 뿌릴 때마다 3씩 증가하기 때문이다. 나무가 자라나는.. [백준] Yangjojang of The Year : 11557번 - Python https://www.acmicpc.net/problem/11557 11557번: Yangjojang of The Year 입학 OT때 누구보다도 남다르게 놀았던 당신은 자연스럽게 1학년 과대를 역임하게 되었다. 타교와의 조인트 엠티를 기획하려는 당신은 근처에 있는 학교 중 어느 학교가 술을 가장 많이 먹는지 www.acmicpc.net 문제를 풀면서 몰랐던 개념 - 이중 반복문 안에서 입력 받은 값들을 각기 다른 리스트에 저장하는 방법 : 빈 리스트를 선언할 때 항상 전역 변수로만 선언했었는데, 첫 번째 반복문의 횟수만큼 두 번째 반복문이 돌아갈 때마다 리스트를 생성하려면 for 문 내에 선언해야 한다는 것을 알게 되었다. for _ in range(T): arr = []# 이거!!! N = int(i.. [백준] 방탈출 : 15729번 - Python https://www.acmicpc.net/problem/15729 15729번: 방탈출 첫째 줄에 N(1 ≤ N ≤ 1,000,000)가 주어지고 둘째 줄에는 쪽지에 적혀 있는 N자리의 수가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 문제를 풀면서 몰랐던 개념 (1) [Python] 일정구간 리스트 값을 한 번에 바꾸고 싶을 때 : 원소 하나만 바꿀 때는 해당 인덱스를 지정해서 바꾸면 되지만 구간을 정해서 여러 개를 한 번에 바꾸려고 할 때는 인덱스 슬라이싱을 이용하고 바꾸려고 하는 값 역시 해당 구간만큼(리스트 형식) 가지고 있어야 한다. A = [0, 0, 0, 0, 0] B = [1, 1, 1] # 리스트 A에서 0번째에서 2번째까지 리스트 B의 값으로 바꾸고 싶을 때 A[0:2.. 이전 1 2 3 4 5 ··· 11 다음
