Python48 [백준] 2579번 - 계단 오르기(C++/파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 계단 오르기 -> www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net Python 코드는 바텀업(Bottom-Up), C++코드는 탑다운(Top-Down)으로 구현했다. C++ 소스 코드) Python 소스 코드) 2021. 4. 9. [백준] 2217번 - 로프 (파이썬/C++) 문제 및 풀이 문제) 백준 - 그리디 알고리즘 (Greedy) - 로프 -> www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 그리디(Greedy) 같으면서도 완전 탐색(Brute Force) 같던 문제. 어렵지 않게 풀 수 있다! C++ 소스코드) 파이썬 소스코드) 2021. 4. 5. [백준] 1005번 - ACM Craft (파이썬) 문제 및 풀이 문제) 백준 - 위상 정렬 (Topology Sort) - ACM Craft -> www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 건물 간의 건설 순서 규칙이 주어졌을 때, 건물 W를 건설 완료를 위해 드는 최소 시간을 출력한다. 규칙(선후관계)이 존재하므로 위상정렬을 이용하여 문제를 해결한다. 진입 차수가 0인 것을 제거해가며 건물 W가 나오면 즉시 시간을 출력한다. Topology Sort ->2021.03.10 - [Algorithm_note/Al.. 2021. 3. 30. [백준] 9251번 - LCS (파이썬) 문제) 백준 - 동적 계획법 (Dynamic Programming) - LCS -> www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net dp를 해당 문자 이전까지 만들 수 있는 LCS라 하자. dp를 업데이트 해가며 만약 문자열이 같을 경우(string1[i] == strring2[j]), 이전 LCS의 길이(dp[i - 1][j - 1])에 1을 더해준다. 문자가 같지 않을 경우, 이전에 만든 LCS중 최대값을 그대.. 2021. 3. 29. [Code Jam] 2021 Code Jam 도전! Code Jam을 모르는 분들이 있다면 -> codingcompetitions.withgoogle.com/codejam Code Jam - Google’s Coding Competitions Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD. codingcompetitions.withgoogle.com 알고리즘 동아리 (AL林)에서 대회 공지가 올라와서 참가하게 되었다. Google 대회에 내가 참가하다니! 참가하는 것만으로도 영광스럽지 않을까 싶어서 호다닥 참가 신청했다. 한.. 2021. 3. 27. [백준] 2798번 - 블랙잭 (C++/파이썬) 문제 및 풀이 문제) 백준 - 브루트 포스(Brute Force) - 블랙잭 -> www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 카드를 세 장 뽑으므로, 삼중 반복문을 이용하여 카드 세 장을 선택하며 그 카드들의 합을 계산하여 확인한다. c++ 소스코드) #include #include #include using namespace std; int n, m, sum = 0; vector card; int main() { //빠른 입출력 io.. 2021. 3. 18. [백준] 2231번 - 분해합 (C++/파이썬) 문제 및 풀이 문제) 백준 - 브루트 포스(Brute Force) - 분해합 -> www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 1부터 n까지 완전 탐색을 수행한다. 만약 생성자를 찾을 경우, 그 즉시 반복문을 탈출한다. C++ 소스 코드) #include using namespace std; int n, ans = 0; //생성자 함수 int constructor(int a) { int res = a; while (a > 0) { res +.. 2021. 3. 18. [백준] 1707번 - 이분 그래프 (파이썬) 문제 및 풀이 문제) 백준 - 그래프 이론 (Graphs) - 이분 그래프 -> acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 그래프가 주어졌을 때, 집합을 둘로 나누어 한 집합에 속한 정점끼리는 인접하지 않게 분할하는 문제. 처음에 주어진 그래프가 당연히 연결 그래프일거라 생각해 약 2시간가량 맞왜틀(맞는데 왜 틀려)를 시전 했다. 연결 그래프가 아니어도 이분 그래프가 될 수 있음을 깨달았다. 그래프를 인접 리스트 형태로 선언하고, 각 노드가 어떤 집합에 포합 되.. 2021. 3. 12. [백준] 11725번 - 트리의 부모 (파이썬) 문제) 백준 - 트리 (Tree) - 트리의 부모 -> www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리 상에서 연결된 두 정점을 인접 리스트 방식으로 나타낸다. 문제에서 트리의 루트가 1번으로 주어졌으므로 dfs를 이용해 1번부터 시작해 노드에 연결된 노드들을 순회한다. parent 리스트에 부모를 채킹(Checking)하면서, 0일 겨우 방문하지 않은 노드로 인식해 부모 노드로 저장한다. 소스 코드) import sys sys.setrecursionlimit(10 ** 8) n = int(input()) tree .. 2021. 3. 12. 이전 1 2 3 4 5 6 다음 반응형
