본문 바로가기

Coding/알고리즘 오답13

(그리디) 백준 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.
(그리디) 이것이 코딩테스트다 11장 Q4 _ 만들 수 없는 금액 [Python] [문제] 동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요. 예를 들어, N = 5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다. 또 다른 예시로, N = 3이고, 각 동전이 각각 3원, 5원, 7원짜리(화폐 단위_ 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다. [입력 조건] 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1 2022. 9. 23.
(우선순위큐) 백준 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.

티스토리툴바