I.Jeong | Log

problem link: https://www.acmicpc.net/problem/1003 1003: 피보나치 (fibonacci) 함수 피보나치 함수 문제는 DP (Dynamic Programming, 동적 계획법) 로 풀지 않으면 시간 초과 오류가 발생한다. 이전 문제의 해를 기록하여 현재 문제의 해를 구할 때 사용하여 시간을 줄일 수 있다. 피보나치 함수에 대한 수도코드(?) 는 아래와 같은데 base case (n=0, n=1)을 제외하고는 fibo(n‐1) + fibo(n‐2) 로 해를 구하는 것을 확인할 수 있다. fibo(n) { if (n == 0) return 0; else if (n == 1) return 1; else return fibo(n‐1) + fibo(n‐2); } 즉 fib..

1. XOR 비트 XOR 연산자는 기술 인터뷰 / 알고리즘 문제에서 유용한 연산자이다. 많은 문제에서 활용되는데, 간단한 예로 모든 요소가 하나의 숫자를 제외하고 짝수 번 발생하는 일련의 숫자가 주어졌을 때, 홀수 번 발생하는 숫자 N를 찾아야 한다면 XOR 연산자를 사용하여 쉽게 풀 수 있다. 이는 XOR 연산자의 특징 때문이다. 줄여말해서 XOR 연산을 거치면 같은 비트 자리에 1이 짝수번 반복되어 나왔을 때 해당 자리는 0이된다. 0과 1을 XOR 연산하면 1이 된다. 이러한 특징으로 N을 쉽게 찾을 수 있게 된다. 1.1. 배열에 누락된 숫자 problem_link 크기가 N-1인 배열 C가 주어지고 하나의 요소가 누락된 1부터 N까지의 숫자가 있는 경우 누락된 숫자를 찾는다. 입력 첫번째 줄: ..