본문 바로가기

728x90
반응형

백준 write-up/정렬 & 그리디

(84)
[백준] 멀티버스 Ⅰ : 20291번 - Python https://www.acmicpc.net/problem/18868 18868번: 멀티버스 Ⅰ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 문제를 풀면서 몰랐던 개념 (1) [Python] 리스트 원소들을 크기 순서대로 번호 매기기 arr = [10, 5, 1, 7] # 다음과 같은 리스트가 있음 s_arr = sorted(arr) # 순서를 찾기 위해 정렬 a_idx = [] # 순서 번호를 저장하기 위한 빈 리스트 선언 for i in arr: # 위에서 선언한 리스트에 s_arr에서 찾은 순서(index)를 추가하기 a_..
[백준] 파일 정리 : 20291번 - Python https://www.acmicpc.net/problem/20291 20291번: 파일 정리 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 www.acmicpc.net 문제를 풀면서 몰랐던 개념 [Python] 리스트 요소별 개수 구하기 1) dictionary를 사용하기 : 딕셔너리에는 키 값이 하나만 존재한다는 특징을 가지고 있기 때문에 각 요소별 개수를 구할 수 있다. dict = {} test = [1,2,1,3,4,5,3,3] for i in test: if dict.get(i): dict[i] += 1 else: dict[i] = 1 print(dict) #..
[백준] 스텔라(STELLA)가 치킨을 선물했어요 : 15905번 - Python https://www.acmicpc.net/problem/15905 15905번: 스텔라(STELLA)가 치킨을 선물했어요 경인지역 6개대학 연합 프로그래밍 경시대회 shake! 는 아주대학교, 경희대학교, 성균관대학교, 인하대학교, 한국항공대학교, 한양대학교ERICA가 함께하는 대학교 자체 연합 대회이다. shake! 는 매 www.acmicpc.net 문제의 접근 방법 입력 받은 값들을 정렬한 후, 5등 학생의 해결 문제 개수와 같은 그 다음 등수 학생들의 수 세기 문제 풀이 방법 참가자 수 N명 입력받기 -> 참가자가 해결한 문제의 개수(q)와 패널티(p) 입력받아서 arr에 추가하기 -> arr를 내림차순으로 정렬 -> 5등 학생의 해결 문제수와 같은 학생들의 수를 구하는 것이기 때문에 for문의..
[백준] 너의 핸들은 : 15819번 - Python https://www.acmicpc.net/problem/15819 15819번: 너의 핸들은 첫 줄에 현정이가 기억하고 있는 핸들의 개수 N과 I(1 ≤ I, N ≤ 100)이 주어진다. 이후 N개의 줄에 걸쳐 현정이 기억하는 핸들이 무작위 순서로 주어진다. 모든 핸들은 영어 소문자와 숫자로만 이 www.acmicpc.net 문제의 접근 방법 현정이가 기억하고 있는 핸들을 정렬하기 문제 풀이 방법 현정이가 기억하고 있는 핸들의 개수 N개와 I값 (나중에 현정이가 기억하고 있는 N개의 핸들 중 I번째 값 출력할 때 쓰임) 입력받기 -> N번 반복문을 돌려 N개의 핸들을 입력받아 미리 선언해둔 빈 리스트 arr에 추가 -> 리스트 arr 정렬하기 -> 인덱스는 0번째 요소부터 시작하기 때문에 I-1을 해주..
[백준] 치킨 TOP N : 11582번 - Python https://www.acmicpc.net/problem/11582 11582번: 치킨 TOP N 인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많 www.acmicpc.net 문제를 풀면서 몰랐던 개념 - 분할 정복 알고리즘 풀고자 하는 어려운 문제를 쪼갠 후, 쪼갠 문제를 합치는 것을 분할 정복(Divide and Conquer)이라고 한다. 문제의 접근 방법 이 문제에서는 N과 K값 모두 2의 거듭제곱 꼴이므로 위와 같은 규칙이 성립될 수 있다. 내가 막혔던 부분 인덱스 슬라이싱으로 끊어서 저장할 생각(한계) -> for문에서 증가치를..
[백준] 귀찮음 : 16208번 - Python https://www.acmicpc.net/problem/16208 16208번: 귀찮음 현우는 무슨 이유에선지 길이 a1, ..., an의, 총 n개의 쇠막대가 필요해졌다. 하지만 그가 가진 것은 길이 a1+...+an의 하나의 쇠막대뿐이었다. 현우는 이 막대를 직접 잘라서 원래 필요하던 n개의 쇠 www.acmicpc.net 문제의 접근 방법 * 현우가 가진 하나의 쇠막대 길이 = a1~an까지의 합. * 막대는 한 번에 n개로 나눠지는 것이 아니라 두 조각으로 나눈 후, 남은 조각을 또 두 조각으로 나누고... 이 과정을 반복. * 정렬이 불필요. 내가 막혔던 부분 길이 x+y인 막대를 길이 x,y인 두 개의 막대로 자를 때, 두 막대의 길이의 곱인 xy비용이 든다는 부분을 이해하지 못함. -> 두..
[백준] 줄 세우기 : 11536번 - Python https://www.acmicpc.net/problem/11536 11536번: 줄 세우기 이름이 증가하는 순으로 나타나면 INCREASING, 감소하는 순이면 DECREASING을 한 줄에 출력한다. 만약 위의 두 경우가 아니라면 NEITHER를 출력한다. www.acmicpc.net 문제를 풀면서 몰랐던 개념 [Python] 리스트의 정렬 여부 체크하기 -> sorted 함수 사용 arr = [30, 24, 10, 5, 2] is_sorted = (sorted(arr) == arr) # It returns False is_sorted = (sorted(arr, reverse = True) == arr) # It returns True 문제의 접근 방법 리스트의 정렬 여부 확인하기 내가 막혔던 부분 ..
[백준] 제 2회 IUPC는 잘 개최될 수 있을까? : 12788번 - Python https://www.acmicpc.net/problem/12788 12788번: 제 2회 IUPC는 잘 개최될 수 있을까? 2016년 5월 28일 제 2회 인하대학교 프로그래밍 경시대회(IUPC)가 개최된다. 이 대회는 다른 프로그래밍 경시대회와 다르게 손코딩으로 문제를 풀어야한다. CTP회장인 정은이는 모든 대회 참가자들 www.acmicpc.net 문제의 접근 방법 - 대회에 참가한 사람의 수를 어떻게 구할지 생각해보기 - 최소 인원의 회원들에게 펜을 빌리기 위해서는 가장 펜을 많이 가지고 있는 회원을 우선시! 내가 막혔던 부분 펜의 개수가 부족할 때 "STRESS" 를 출력하는 방법 -> break문을 걸어주지 않아서 반복 출력되게 함. 문제 풀이 방법 CTP의 회원 수 n명 입력 받기 -> 참가..

728x90
반응형