코드 낙서장

문제 주소 : programmers.co.kr/learn/courses/30/lessons/1831 코딩테스트 연습 - 4단 고음 4단 고음 I'm in my dream~↗ ~↗ ~↗ IU는 본인의 장기인 3단 고음으로 유명하다. 그러던 그녀가 어느 날 4단 고음을 성공했고 그녀의 고음은 학계에서 연구가 될 만큼 유명해졌다 [1]. [1] 견두헌, 배명 programmers.co.kr 문제 확인 간단하게 시뮬레이션처럼 풀 수 있지만 시간 초과가 납니다. 또한 단순 dfs로 풀어도 시간 초과가 나게 됩니다. 따라서 가지치기, 혹은 추가 조건을 통해서 통과할 수 있습니다. * 이후에 2개의 + 가 나와야 하므로 이를 이용하여 조건을 만들 수 있습니다. 하향식 dfs와 가지치기를 통해 풀 수 있습니다. 풀이 ..

문제 주소 : programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 문제 확인 dp문제 처음 집을 선택하는가에 따라 2가지 스텝으로 분류합니다. 풀이 처음 집을 선택한 경우 마지막 집을 선택할 수 없으므로 size -1 까지 탐색을 합니다. 선택하지 않은 경우는 size 까지 모두 탐색을 합니다. n개의 배열을 둘 필요없이 2칸 단위로 잘라 최댓값을 지정하기 위해 3칸의 배열을 사용합니다. 현재 집을 털었을 때 비용과 털지 않고 ..

문제 주소 : programmers.co.kr/learn/courses/30/lessons/12902 코딩테스트 연습 - 3 x n 타일링 programmers.co.kr 문제 확인 dp 문제로 수열식으로 풀 수 있습니다. 홀수인 경우 모든 답이 0이며 짝수인 경우 생길 수 있는 경우의 수를 체크하면 쉽게 풀 수 있습니다. 풀이 n을 2 단위로 생각하면 두 가지 종류로 나눌 수 있습니다. 영역이 겹치는 문양 : 매 단계에서 새로 생기는 문양 영역이 분리된 문양 겹치는 문양의 경우 매 단계에서 2개 추가됨 분리된 문양의 경우 따라서 n이 2 증가할 때 생각할 수 있는 경우의 수는 다음과 같습니다. 이를 수식으로 나타내면 f(n) = f(n-2) * 3 + f(n-4) * 2 + f(n-6) * 2 + ....

경북대학교 고리콘 대회 문제 : www.acmicpc.net/contest/view/545 2020 경북대학교 Goricon 사용 가능한 언어 C++17 Java 8 Python 3 C11 PyPy3 C99 C++98 C++11 C++14 Java 8 (OpenJDK) Java 11 C++20 Python 2 PyPy2 C99 (Clang) C++98 (Clang) C++11 (Clang) C++14 (Clang) C11 (Clang) C++17 (Clang) C++20 (Clang) C90 C2x C90 (Clang) C2x (Clang) www.acmicpc.net 문제 주소 : www.acmicpc.net/problem/20119 20119번: 클레어와 물약 첫 번째 줄에는 세상에 존재하는 물약의 ..

경북대학교 고리콘 대회 문제 : www.acmicpc.net/contest/view/545 2020 경북대학교 Goricon 사용 가능한 언어 C++17 Java 8 Python 3 C11 PyPy3 C99 C++98 C++11 C++14 Java 8 (OpenJDK) Java 11 C++20 Python 2 PyPy2 C99 (Clang) C++98 (Clang) C++11 (Clang) C++14 (Clang) C11 (Clang) C++17 (Clang) C++20 (Clang) C90 C2x C90 (Clang) C2x (Clang) www.acmicpc.net 문제 주소 : www.acmicpc.net/problem/20120 20120번: 호반우와 리듬게임 호반우가 모든 노트를 처리하면 3×1..

문제 주소 : www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 문제 확인 특별한 알고리즘을 필요로 하는 문제는 아닙니다. 각 시험자의 응시자 수가 먼저 입력으로 주어지므로 배열에 저장해둔 후 감독관 정보를 받아 해결합니다. 각 시험장의 학생의 수가 총감독관이 감시 가능한 학생의 수를 넘는다면 계산이 필요하고 넘지 않는다면 1명을 추가합니다. 풀이 시험장에 있는 학생의 수가 총감독관이 감시할 수 있는 학..

위키피디아 : ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%ED%9E%99 이항 힙 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 이항 힙에 대해 설명한다. 컴퓨터 과학 분야에서는 이항힙(binomial heap)은 이진힙(binary heap)과 유사하지만, 이항힙(binomial heap)이 ko.wikipedia.org 이항 트리 시각화 사이트 : www.cs.usfca.edu/~galles/visualization/BinomialQueue.html Binomial Queue Visualization www.cs.usfca.edu 이항 힙은 이항 트리가 결합된 구조로 이루어져 있으며 n차수의 이항 트리는 2개의 n-..

경북대학교 고리콘 대회 문제 : www.acmicpc.net/contest/view/545 2020 경북대학교 Goricon 사용 가능한 언어 C++17 Java 8 Python 3 C11 PyPy3 C99 C++98 C++11 C++14 Java 8 (OpenJDK) Java 11 C++20 Python 2 PyPy2 C99 (Clang) C++98 (Clang) C++11 (Clang) C++14 (Clang) C11 (Clang) C++17 (Clang) C++20 (Clang) C90 C2x C90 (Clang) C2x (Clang) www.acmicpc.net 문제 주소 : www.acmicpc.net/problem/20118 20118번: 호반우가 길을 건너간 이유 격자의 왼쪽 위가 0, 0 ..

문제 주소 : www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 문제 확인 다익스트라 알고리즘을 활용하여 세금 인상 전 최소비용 경로를 구하고 경로의 개수에 가중치를 두는 문제입니다. 개인적으로 이 블로그가 설명을 잘해 둔 것 같습니다 다익스트라 기본 개념 : mattlee.tistory.com/50 기본개념과 알고리즘 # 최단 경로 최단 경로(shortest path)문제는 정점 u와 ..

문제 주소 : www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net c언어 스타일로 벡터 등 컨테이너 없이 풀면 메모리는 적게 나오지만 가끔 0ms가 나오지만 보통 4ms가 나옵니다. 빈 배열과 나무 나이 등 조건이 더 많아지기 때문에 처리해야 할 조건문이 많아지기 때문인 것 같습니다. 문제 확인 따로 특별한 알고리즘이 필요하지 않습니다. 제한시간과 메모리 초과가 관건입니다. 문제 조건 봄 : 나이가 낮은 순 부터 나무가 땅의 양분을 먹고 나이가 ..