본문 바로가기

백준 문풀

(69)
2024 중앙대 프로그래밍 경진대회 후기 및 문풀(A1 - D2) 자.. 지금이 무슨 상황인고 하니, 자교 알고리즘 경진대회에 참여 후, 약 2시간이 지나지 않은 시점에서 쓰는 후기이다. 이번이 첫 오프라인 대회 참석이라 가벼운 마음으로 대회에 참여했다.그런데 웬걸?! 문제가 이전 대회 기출보다 굉장히 쉽게 나와 풀만 했다.결과적으로 2등을 했다! 그래서 커피와 에너지 음료에 절여져 흥분되어 있는 이 기분 좋은 여운이 가시기 전에 빠르게 후기를 작성하고자 오랜만에 도서관에 와 노트북을 켰다. 문제 등급별 분포문제는 9문제가 나왔고 각 등급별 분포는 다음과 같았다등급개수A1문제B3문제C3문제D2문제 등급별로 문제 난이도가 올라가고, 등급 내 문제 난이도는 순서와 상관 없다.(ex) B1은 A1보다 확실히 어렵다, 그러나 B2가 B1보다 어렵다는 보장은 없다) 나는 9문제..
[Python] 7983. 내일 할거야(골5) / 그리디-정렬 목차1. 문제2. 핵심 아이디어3. 코드4. 배운 점 1. 문제 https://www.acmicpc.net/problem/7983 2. 핵심 아이디어 요약- 끝나는 일자를 기준으로 내림차순 정렬합니다.- 이전 과제 시작일은 시스템 최대값으로 초기화합니다.- 이전 과제 시작일보다 현 과제 마감일이 더 이르다면 현 마감일자를 기준으로 시작일자를 초기화합니다.- 이전 과제 시작일이 현 과제 마감일보다 같거나 더 이르다면 이전 과제 시작일 전날을 기준으로 시작일자를 초기화합니다. 예시)3걸리는 시간마감일자28113310  우선 마감일자를 기준으로 내림차순 정렬합니다. 걸리는 시간마감일자11331028   우선 가장 이른 시작일자 구할 것이기 때문에 시작일자를 최대값으로 초기화합니다.start= sys.maxsi..
[Python] 1082. 방 번호(골3) / 그리디 + DP 목차 1. 문제 2. 핵심 아이디어 3. 코드 4. 배운 점 1. 문제 https://www.acmicpc.net/problem/1082 1082번: 방 번호 첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다. www.acmicpc.net 2. 핵심 아이디어 다른 사람의 풀이를 참고했음에도 사실 이해가 잘 되지 않았다. 어느정도 이해가 되니 문제는 풀렸지만 이런 사고를 어떻게 떠올리는지는 잘 모르겠다 한번 아이디어를 정리해보자 가장 큰 숫자라는 건 어떻게 정할 수 있을까? 아마 그리디한 사고로 높은 숫자부터 고려하는 것을 떠올릴 수 있다. 그러나, 이 문제가 어려운 점은 여기서 그치지 않고 예산이라는 제한이 들어가기 때문이다. 예산,..
[Python] 2538. 전구와 스위치 / 그리디 목차 1. 문제 2. 핵심 아이디어 3. 코드 4. 배운 점 1. 문제 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 2. 핵심 아이디어 https://staticvoidlife.tistory.com/143 [그리디 알고리즘] 전구와 스위치 예제 입력 1 3 000 010 예제 출력 1 3 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있..
[Python] 2872. 우리집엔 도서관이 있어(실2) / 그리디 목차 1. 문제 2. 핵심 아이디어 3. 코드 4. 배운 점 1. 문제 https://www.acmicpc.net/problem/2872 2872번: 우리집엔 도서관이 있어 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근 www.acmicpc.net 2. 핵심 아이디어 이 문제가 어려운 이유는 어떤 순서로 책을 꺼내야 하는지를 고민하기 때문이다. 그러나, 자세히 잘 바라보면 꺼내는 순서는 이미 정해져 있다. 예를 들어 다음 책의 배열이 있다고 가정해보자 5 4 3 2 1 이 상황에선 최대값 뒤에 있는 4 3 2 1을 앞으로 꺼내면 된다. 그리고 그 순서는 오름차순에 ..
[Python] 1783. 병든 나이트(실3) /그리디 목차 1. 문제 2. 핵심 아이디어 3. 코드 4. 배운 점 1. 문제 https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 핵심 아이디어 https://lipcoder.tistory.com/94 병든 나이트 (백준 - 1783번) 그리디 알고리즘을 사용하는 문제였다. 우선 나이트의 모든 이동방법이 위, 아래 오른쪽으로 무조건 1칸 이상 움직이므로, 세로 길이가 1인 체스판의 경우에 나이트는 한번도 이동 할 수 없다. lipcoder.tistory.com 3. 코드 #1783. 병든나이트(실3) n,m= ma..
[이코테 파이썬] #01. 그리디 알고리즘 >>강의 #1. 모험가 길드 >내가 푼 풀이 group=[] cnt=0 n= int(input()) scared= list(map(int, input().split())) scared.sort() for i in scared: group.append(i) if len(group)==max(group): cnt+=1 group=[] print(cnt) > 답안 소스코드 # 답안 소스코드 n= int(input()) data= list(map(int, input().split())) data.sort() result=0 # 총 그룹의 수 count=0 #현재 그룹에 포함된 모함가의 수 for i in data: # 공포도를 낮은 것부터 확인 count+=1 # 현재 그룹에 해당 모험가 포함시키기 if cou..
[Python] 2169. 로봇조종하기(골2) / DP + 방향에 따른 배열 할당 목차 1. 문제 2. 핵심 아이디어 3. 코드 4. 배운 점 1. 문제 https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 2. 핵심 아이디어 특정 칸에 다다르는 경로는 3가지 케이스이다. - 위에서 오기 - 왼쪽에서 오기 - 오른쪽에서 오기 예제 데이터를 기반으로 보자면 24가 적힌 칸에 다다를 수 있는 케이스는 이렇게 요약 가능하다. - 위에서 오기 (25가 적힌 칸으로부터) - 왼쪽에서 오기 (68이 적힌 칸으로부터) - 오른쪽에서 ..