백준 온라인저지 2156번 포도주 시식 문제풀러 바로가기👇👇👇👇👇👇 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제풀이 다이나믹 프로그래밍을 이용해 문제를 풀 수 있다. 연속으로 3잔을 마실 수 없는 조건을 만족시켜야하고, 최대한 많은 포도주를 마셔야하기 때문에 점화식을 잘 세우고, max 메소드를 이용해야한다. wine 맨 앞에 0인 더미 값을 넣어줘 dp와 인덱스를 맞춰줬다. 아래 코드를 통해 점화식을 도출해보자. dp[1]와 dp[2]..
백준 온라인저지 10816번 숫자 카드 2 문제풀러 바로가기👇👇👇👇👇👇 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제풀이 알고리즘 분류에는 이분 탐색으로 되어있는 문제다. 그러나 Counter 함수, 딕셔너리 등 여러 가지 방식으로 풀이할 수도 있는 문제이다. 그냥 단순히 배열의 메소드인 count()를 사용하면 시간초과가 발생하니 알아두자. 나는 bisect를 이용해 문제를 풀었다. 일단 이분탐색을 하..
백준 온라인저지 18870번 좌표압축 문제풀러 바로가기👇👇👇👇👇👇 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제풀이 시간 복잡도가 굉장히 중요한 문제이다. 근본적인 알고리즘은 쉬운 편이다. 중복되지 않은 배열을 정렬해 그 인덱스를 가져오면 된다. 만약 여기서 리스트에서 인덱스를 가져오는 index()메소드를 사용하면 시간복잡도가 O(N)이다. 그런데 문제에서 N의 범위는 무려 1 ≤ N ..
백준 온라인저지 7576번 토마토 문제풀러 바로가기👇👇👇👇👇👇 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제풀이 1. 바이러스같이 퍼져가는 구조이므로 bfs를 사용해야한다. 2. 퍼져나가면서 1씩 증가시켜 기록하면 최대값을 통해 모두 익을 때까지의 최소 날짜를 알 수 있다. 3. dx, dy 배열을 이용해 사방에 있는 토마토들을 탐색하자. 4. 만약 bfs를 사용해서 탐색했는데도 0이 남아있다면 -1에 의해 가로막혀 있는..
백준 온라인저지 9184번 신나는 함수 실행 문제풀러 바로가기👇👇👇👇👇👇 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제풀이 문제에 점화식이 주어지기 때문에 그것을 그대로 사용하면 된다 다만 if dp[a][b][c]: return dp[a][b][c] 를 통해 재귀함수가 반복되지 않도록만 하자. dp = [[[0]*21 for _ in range(21)] for _ in range(21)] def w(a, b, c): if a 20: ret..
백준 온라인저지 1654 랜선 자르기 문제풀러 바로가기👇👇👇👇👇👇 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제풀이 이 문제는 이분탐색을 이용해야하는 문제이다. start는 1로 잡고, 랜선 중 최대길이를 end로 정한 다음 이분 탐색을 하면 다음과 같다. 첫 번째 mid는 402cm이다. 402cm로 자르면 랜선이 5개 밖에 나오지 않기 때문에 mid를 mid = (start + mid - 1) // 2 로..
