haejun IT

정수삼각형 풀이 문제의 규칙을 하나하나 따져봤을 때, 다음의 규칙을 알 수 있다. i 횟수 예시 1 1 7 2 2 (7+3), (7+8) 3 4 (7+3+1), (7+8+1), (7+8+0) i 가 증가함에 따라 2^(n-1)번의 횟수가 적용된다는 것을 알 수 있다. 문제에서 주어진 입력의 크기가 1

백준 파도반 수열 풀이 백준 사이트 특성상 알고리즘의 분류가 되어 있어 DP 문제라는 것을 알 수 있지만 실전같은 경우는 어떻게 DP 문제라는 것을 유추할 수 있을까? 위의 문제에서 제시한 예시를 보면 이 전의 연산 결과에 따라서 다음의 연산 결과를 저장한다. 고로 작은 것을 통해 큰 것의 최적해를 찾는 것이기 때문에 DP를 사용하면 된다는 것을 유추할 수 있다. 또한 입력 N의 범위가 1

3.6 제어문 기계어 코드에서는 조건부 동작을 구현하기 위해 두 개의 기본적인 row level의 방법을 제공한다. 보통 C와 기계어 코드의 인스트럭션들은 모두 프로그램에 나타나는 순서대로 순차적으로 실행된다. 기계어 인스트럭션들의 실행 순서는 점프(jump) 인스트럭션으로 변경할 수 있다. 점프 인스트럭션은 결과에 따라 프로그램의 다른 일부분으로 제어를 넘겨준다. 3.6.1 조건 코드 정수 레지스터들과 함께 최근 CPU는 가장 최근 산술 또는 논리연산의 특성을 설명하는 단일 비트 조건 코드로 구성된 레지스터들을 운영한다. CF: Carry Flag. 가장 최근의 연산에서 가장 중요한 비트로부터 받아 올림이 발생한 것을 표시 비부호형 연산에서 오버플로우를 검출할 때 사용 ZF: Zero Flag. 가장 ..

문제 백준 1로 만들기 풀이 과정 그리디 알고리즘과 구분하기. 그리디 알고리즘은 각 단계에서 최적의 해를 보장해야하지만, 이 문제는 무엇으로 나눌지에 따라서 최적의 해가 달라지기 때문에 DP로 풀어야한다. 또한 입력 갯수와 시간 제한이 빡빡하기 때문에 이를 보고 유추했을 때, DP를 떠올릴 수 있다. 각 단계별로 네가지의 연산이 가능하기때문에 이 중에서 최솟값을 구해주면 된다. 따라서 이 문제의 점화식은 다음과 같다. min(ai-1, ai/2, ai/3 ai/5). 나머지를 구하는 연산은 각 조건에 해당할 때만 수행할 수 있어야 한다. (a의 i-1번째, a의 i를 2로 나눔, a의 i를 3으로 나눔, a의 i를 5로 나눔의 의미) 이를 코드로 구현하면 다음과 같이 구현할 수 있다. +1을 해주는 것은..