본문 바로가기

백준6

(그리디) 백준 20365번 _ 블로그2 [Python] https://www.acmicpc.net/problem/20365 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 전형적인 그리디 문제이다. 아래는 내가 처음 풀려고 했던 방식인데 "BRBBRR"의 정답이 3인데 자꾸 4를 출력했다. a = "BRBBRR" answer = 1 start = a[0] for i in a[1:]: if start != i: answer += 1 start = i if a[0] == a[-1] and a.count(a[0]) == a.count(a[-1]) and answer !.. 2022. 10. 5.
(우선순위큐) 백준 1655번 _ 가운데를 말해요 [Python] https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 이 문제는 우선순위큐 알고리즘으로 해결해야 하는 문제이다. 처음 문제를 접했을때 큐를 사용해야겠다는 생각은 했으나, 중앙값을 리턴하는 메소드를 구현할때 sorted()를 이용하였다. 파이썬에서 sorted()를 사용하면 대다수의 경우에서 시간초과가 계속 나타나는데 역시나 시간초과로 해결하지 못하였다. 아래 코드는 내가 처음 시도했던 코드이다. import sys class myQu.. 2022. 6. 17.
(DP) 백준 12865번 _ 평범한 배낭 [Python] https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 DP문제(냅색문제)다. 처음에는 DP(다이나믹 프로그래밍)의 개념을 생각하지 않은 채 그냥 생각나는대로 코드를 적었다. 대부분의 테스트 케이스에서 맞췄지만, 아래에서 나오는 (4,6), (4,2), (4,10) 과 같이 같은 무게이면서 value가 여러개인 test case는 통과하지 못했다. # my answer (wr.. 2022. 5. 25.
(그리디) 백준 1543번 _ 문서검색 (+ Python 3 와 PyPy3는 무엇이 다를까) 이 문제는 맞은 문제이다. N = input("") k = input("") print(N.count(k)) 단 세줄의 코드를 PyPy3로 제출하면 정답이 나오는 어떻게 생각하면 되게 쉬운 문제이다. 그러나 이렇게 따로 정리하는 것은 두가지 이유 때문이다. 1. 위 파이썬 코드를 Python3 로 제출하면 런타임오류가 나와서 PyPy3로 제출했더니 정답처리가 되었다. 2. count라는 파이썬의 치트키를 사용하지 말고 직접 로직을 구현해보고 싶었다. 1. Python3 vs PyPy3 우선 Python3 와 PyPy3가 무엇이 다른지부터 알아보자 PyPy3는 파이썬으로 만든 파이썬이다. 우리가 일반적으로 사용하는 Python은 C언어로 구현 되어있고 그 구현체를 CPython이라고 한다. 이는 가장 처음.. 2022. 2. 5.
(그리디) 백준 21758번 _ 꿀 따기 [Python] https://www.acmicpc.net/problem/21758 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 그리디 알고리즘에서 "그리디" 즉 탐욕적이라는 말은 "현재 상황에서 지금 당장 좋은 것만 고르는 방법"을 의미한다. 이 문제를 풀면서 누적합과, A = max(A, B)를 통해 최댓값을 계속 업데이트 해주는 두 가지 개념에 대해 배울 수 있었다. 문제를 예시로 누적합에 대해 좀 더 자세히 말해보면, 우선 꿀 합에 대한 누적합은 다음과 같다. # 코드 (문제에 주어진 예시) n = 7 honey_place = [9,9,4,1,4,9,9] prefix_sum=[] prefix_sum.append(a[0]) for i in range(1,n).. 2022. 2. 2.
(그리디) 백준 2872번 _ 우리집엔 도서관이 있어 [Python] https://www.acmicpc.net/problem/2872 2872번: 우리집엔 도서관이 있어 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근 www.acmicpc.net 내가 생각하는 그리디 알고리즘의 핵심 키워드는 "규칙"을 것이다. 이 문제는 책 배열 정리의 규칙을 찾는 것이 생각보다 어려워서 풀지 못했던 것 같다. 또한 책을 빼는 순서까지 고려했었는데 다시 생각해보니 순서는 고려할 필요가 없다. 중요한 것은 "몇 권의 책을 재배열해야 하냐"이고 순서는 어차피 정해져있기 때문에 재배열 해야 할 책의 권수가 곧 정답이 될 것이다. 두 가지 예시를 들어보면,.. 2022. 1. 25.

티스토리툴바