본문 바로가기

728x90
반응형

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

(84)
[백준] 먹을 것인가 먹힐 것인가 : 7795번 - Python https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 문제의 접근 방법 - 이분탐색 알고리즘 활용하기 내가 막혔던 부분 - 시간 초과 문제 풀이 방법 테스트 케이스 T개 입력 받기 -> T번 만큼 반복문을 돌려 a,b(A의 수와 B의 수) 입력 받기 -> A의 크기와 B의 크기 입력 받기 -> 중첩 반복문을 통해 brute force 방법으로 A의 값들과 B의 값들의 크기 비교 -> 만약 A[i]가..
[백준] 2+1 세일 : 11508번 - Python https://www.acmicpc.net/problem/11508 11508번: 2+1 세일 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 www.acmicpc.net 문제를 풀면서 몰랐던 개념 (1) 일정 부분 합 구하기 -> sum 메소드와 슬라이싱 사용!!! arr = [10, 20, 30, 40, 50] a = sum(arr[:2]) b = sum(arr[:3]) print(a) print(b) >> 30 >> 60 * sum 메소드는 합을 구해준다 (2) 리스트를 특정 크기의 리스트로 분할하기 arr = [1, 2, 3, 4, 5, 6, 7,..
[백준] 소가 길을 건너간 이유 1 : 14467번 - Python https://www.acmicpc.net/problem/14467 14467번: 소가 길을 건너간 이유 1 3번 소는 위치 1, 0, 1에서 관찰되었으므로 길을 최소 두 번 건넜음을 확인할 수 있다. 4번 소도 길을 한 번 건넜으며, 나머지 소는 길을 건넌 기록이 확인되지 않는다. www.acmicpc.net 문제를 풀면서 몰랐던 개념 (1) [Python] 딕셔너리 dict = {} dict['a'] = 3 dict['b'] = 5 print(dict) >> {'a': 3, 'b': 5} dict2 = {'a':3, 'b':5 } print(dict2['a']) >> 3 (2) [Python] in / not in 연산자 -> 딕셔너리 : 딕셔너리는 그대로 in / not in 연산을 사용하면 key..
[백준] 아시아 정보올림피아드 : 2535번 - Python https://www.acmicpc.net/problem/2535 2535번: 아시아 정보올림피아드 첫 번째 줄에는 대회참가 학생 수를 나타내는 N이 주어진다. 단, 3 ≤ N ≤ 100이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학생의 소속 국가 번호, 학생 번호, 그리고 성적이 하나의 빈칸을 사 www.acmicpc.net 문제를 풀면서 몰랐던 개념 (1) [Python] 2차원 배열 슬라이싱 -> 2차원 배열에서는 행에 대해서는 슬라이싱을 하지 않고 접근해야 한다! arr = [[1, 2, 3, 4], [5, 6, 7, 8]] [print(arr[i][:2]) for i in range(len(arr))] >> [1, 2] >> [5, 6] (2) [Python] asterisk(*) 사용 ..
[백준] 수 정렬하기 5 : 15688번 - Python https://www.acmicpc.net/problem/15688 15688번: 수 정렬하기 5 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이며, 같은 수가 여러 번 중복될 수도 있다. www.acmicpc.net 문제의 접근 방법 - 정렬 - 시간초과 문제 풀이 방법 앞서 포스팅했던 '수 정렬하기' 시리즈 문제들처럼 똑같이 하면 되지만, 시간 제한이 있기 때문에 import sys 라이브러리를 통해 단축시키기 소스코드 import sys n = int(sys.stdin.readline()) arr = [] for i in range(n): number = int(sys.st..
[백준] 통나무 건너뛰기 : 11497번 - Python https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 문제의 접근 방법 통나무의 높이를 크기 순서대로 정렬한 후, 가장 큰 통나무를 기준으로 양옆을 그 다음으로 큰 통나무로 채우는 형식으로 만들기 -> 가장 작은 높이차 * 가장 첫 통나무와 가장 마지막 통나무가 인접해있지 않다면 그냥 정렬만 해주어도 인접한 원소의 차이들을 최소로 만들어주지만 문제에서 가장 첫 통나무와 마지막 통나무가 인접해있다고 명시되어 있기 때문에 위처럼 정렬할 경우에는 첫 원..
[백준] 성적 통계 : 5800번 - Python https://www.acmicpc.net/problem/5800 5800번: 성적 통계 첫째 줄에 중덕 고등학교에 있는 반의 수 K (1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 각 반의 학생수 N (2 ≤ N ≤ 50)과 각 학생의 수학 성적이 주어진다. 시험 성적은 0보다 크거나 같고, 100보다 www.acmicpc.net 문제를 풀면서 몰랐던 개념 - 정수 출력 값 옆에 바로 붙여서 쉼표를 출력하는 방법 print("Max", str(save[i][0])+',', "Min", str(save[i][1])+',', "Largest gap", save[i][2]) : 정수 출력 값을 문자열로 바꿔주어서 출력해야 한다!!! 문제의 접근 방법 - 둘째 줄에 입력 받는 학생수와 수학 성적을 분리..
[백준] 거북이 : 2959번 - Python https://www.acmicpc.net/problem/2959 2959번: 거북이 첫째 줄에 거북이가 생각한 네 양의 정수 A, B, C, D가 주어진다. (0 정렬을 통해 구하기 (직사각형의 최대 넓이 = 가장 작은 수 * 두 번째로 작은 수) 소스코드 # 양의 정수 4개가 한방향으로 움직이기 시작하고 90도 회전한 후 새로운 방향 # 이런식으로 3번 90도 회전하고 4번 앞으로 움직여서 선분..

728x90
반응형