본문 바로가기

알고리즘204

[백준] 1563번 - 개근상 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법(Dynamic Programming) - 개근상 -> https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net cache[ i ][ j ][ k ]를 길이가 i이고 지각(L)이 j번이면서 끝문자의 연속 결석 회수가 k번으로 정의한다. 가령, 'LOAA'는 cache[4][1][2]의 한 요소이고, 'OALAO'는 cache[5][1][0]의 한 요소이다. 결석은 세번 연속으로 하지 않는 이상 개근상에 영향을 주지 않기 때문에 끝에 연속된.. 2021. 7. 6.
[백준] 1351번 - 무한 수열 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법(Dynamic Programming) - 무한 수열 -> https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 친절(?)하게도 점화식이 주어졌다. N의 범위가 10^12까지이므로 배열로 memoization 하는 것은 불가능하다. 또한 N이 P와 Q로 계속 나누어지기 때문에 10^12까지 인덱싱 하는 것은 비효율적이다. 따라서 map을 이용하여 memoization을 통해 기존 Top-down 방식의 Dp를 구현했다. C++ 소스코드) 2021. 7. 6.
[백준] 18870번 - 좌표 압축 (C++) 문제 및 풀이 문제) 백준 - 정렬(Sorting) - 좌표 압축 -> https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net n이 최대 100만이기 때문에 O(nlogn)으로 짜야한다. 좌표의 값과 인덱스를 저장 후 값에 대하여 오름차순으로 정렬한다. 그 후 ans에 압축 적용된 값을 넣는다. C++ 소스 코드) 2021. 6. 29.
[백준] 10422번 - 괄호 (C++) 문제 및 풀이 문졔) 백준 - 동적 계획법 (Dynamic Programming) - 괄호 -> https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 괄호의 길이가 L인 올바른 문자열의 개수를 구하고자 할 때, L은 다음과 같이 구할 수 있다. solve(n)를 길이가 n인 올바른 문자열의 개수라 하면, 위의 문자열에서는 solve(L) = ∑ {solve(i - 2) * solve(L - i)}임을 알 수 있다. 또한, solve(i - 2)를 구하기 위한 작.. 2021. 6. 29.
[백준] 14499번 - 주사위 굴리기 (C++) 문제 및 풀이 문제) 백준 - 구현 - 주사위 굴리기 -> https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 주사위는 고정시킨채(dice[0]: 주사위 윗면, dice[5]: 주사위 아랫면), map을 이동하면서 주사위 면의 숫자를 바꿔준다. C++ 소스 코드) 2021. 6. 29.
[프로그래머스] 2021 Dev-Matching - 로또의 최고 순위와 최저 순위 (C++) 문제 및 풀이 문제) 프로그래머스 - 2021 Dev-Matching - 로또의 최고 순위와 최저 순위 -> https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr ⊙ 풀이 당첨 순위의 최대와 최저를 어떻게 구할지 안다면 그다지 어렵지 않은 문제. 당첨 번호와 자신의 번호 중에 일치하는 것과 알아볼 수 없는 번호를 계산해 최고 순위와 최저 순위를 결정하면 된다. 완전 탐색을 이용해 O.. 2021. 6. 3.
[백준] 1715번 - 카드 정렬하기 (C++/파이썬) 문제 및 풀이 문제) 백준 - 우선순위 큐 (Priority Queue) - 카드 정렬하기 ->www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net C++ 소스 코드) 파이썬 소스 코드) 2021. 4. 14.
[백준] 11279번 - 최대 힙 (C++/파이썬) 문제 및 풀이 문제) 백준 - 우선순위 큐 (Priority Queue) - 최대 힙 -> www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net C++ 소스 코드) 파이썬 소스 코드) 2021. 4. 14.
[백준] 1927번 - 최소 힙 (C++/파이썬) 문제 및 풀이 문제) 백준 - 우선수위 큐 (Priority Queue) - 최소 힙 -> www.acmicpc.net/problem/1927 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net C++은 최소 힙 구현을 위해서 다음과 같이 선언한다. 기본은 최대 힙. 파이썬과 반대이므로 헷갈리지 않도록 유의하자. priority_queue heap; C++ 소스 코드) 파이썬 소스 코드) 2021. 4. 14.
반응형

티스토리툴바