백준 온라인저지 2156번 포도주 시식 문제풀러 바로가기👇👇👇👇👇👇 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제풀이 다이나믹 프로그래밍을 이용해 문제를 풀 수 있다. 연속으로 3잔을 마실 수 없는 조건을 만족시켜야하고, 최대한 많은 포도주를 마셔야하기 때문에 점화식을 잘 세우고, max 메소드를 이용해야한다. wine 맨 앞에 0인 더미 값을 넣어줘 dp와 인덱스를 맞춰줬다. 아래 코드를 통해 점화식을 도출해보자. dp[1]와 dp[2]..
파이썬 속성 강좌 출처 "Data Science from scratch" - 저자 Joel Grus 1. 기본기 다지기 파이썬에는 설계 원칙에 대한 일종의 교리인 'The Zen of Python'이 있다. 여기서 가장 중요한 것은 "어떤 일에든 명확한-바람직하고 유일한 방법이 존재한다"라는 말이다. 명확한 방식으로 쓰여진 코드를 일반적으로 '파이썬스럽다(Pythonic)'이라고 한다. 이제부터 파이썬에 대해 알아보자. "아름다움이 추함보다 좋다. 명시가 암시보다 좋다. 단순함이 복잡함보다 좋다." 2. 파이썬 설치 python.org 또는 아나콘다(Anaconda) 배포판 3. 가상환경 matplotlib 라이브러리 사용하여 데이터 시각화를 해야하는데, matplotlib은..
백준 온라인저지 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..
