백준 9095 - 1, 2, 3 더하기
www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이전 포스팅과 마찬가지로 이번에도 다이나믹 프로그래밍 문제이다. 아주 기본적인 형태이다. DP(Dynamic Programming)문제를 풀 때, 가장 중요한 것 중 하나가 바로 점화식을 구하는 것이다. 점화식이란 말 그대로 어떠한 연속된 연산의 불을 붙여주는 기초 공식이라고 볼 수 있다. 즉, 이전 포스팅(백준 회의실 배정 문제)에서 살짝 언급한 바와 같이, 연속된 연산이 하나의 공식(점화식)하에서 계속 이루어지기 위해서는 모든 정점(상황)에서 항상 같은 규칙이 적용될 수 있어야 한다. 이 문제에서는 어떠한..
백준 1931 회의실배정 (C++, Python)
www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 백준 1931 회의실배정 문제는 백준 11000 강의실 배정 문제와 함께 그리디 알고리즘 입문에 있어 반드시 겪고 넘어갈 문제라고 생각한다. [그리디 알고리즘]이란 매 순간, 가장 최선의 선택을 하는 것을 말한다. 이후에 따로 다시 정리하겠지만, 문제에서 어떠한 상황들(정점)이 어떻게 서로 연결되어지고 관계를 맺는지(간선)를 파악하는 것이 매우 중요하다. 어찌 보면 가장 중요하다고도 볼 수 있을 것 같다. 하나의 정점(상황)에서 일정한 규칙에 의해서 다음 정점 또는 정점들로 이동한다면 DP(Dynamic Programming, ..
백준 1316 그룹 단어 체커 (파이썬)
www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때� www.acmicpc.net 이 문제는 파이썬 set을 활용하여 해결하였다. 파이썬에서 입력을 받을 때 sys.stdin.readline함수를 사용하는 게 속도면에서 빠르지만, 이 문제에서는 그냥 input()으로 받았다. 문제에서 주어지는 단어를 읽고, (이 문제에서에는 파이썬에 대해 잘 모르던 시절에 작성하였던 코드라 한 글자씩 일일이 받았다 ㅠㅠ) 새로운 글자가 나오면 set에 담고, 이전에 나왔던 ..
