백준(3)
-
백준 1003번 피보나치 함수
백준 1003번은 기초적인 동적 계획법(DP, Dynamic programming) 문제입니다. 시간제한이 0.25초로 매우 빡빡한 편이라서 시간복잡도 O(n)으로 풀어야 해결 가능합니다. 다음 소스는 문제에서 주어진 $N$번째 피보나치 수를 구하는 C++ 함수입니다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } 이와같이 재귀적으로 N번째 피보나치 숫자를 구했을때 0과 1이 각각 몇번씩 return되는지 구하는 문제인데, $fib(n)$ 을 $n$번째 피보나치 숫자를 반환..
2020.01.15 -
백준 2580번 스도쿠
https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 백트래킹 구현시 항상 search()함수를 void 타입으로 구현했는데, int형으로 수정되어 최초해가 나오면 바로 모든 search()함..
2020.01.07 -
첫 코드포스 도전 후기
저는 소프트웨어학과를 올해(2019) 입학한 학부 신입생입니다. 그리고 소프트웨어학과는 프로그래밍을 배웁니다. 프로그래밍을 배우는 과정에서 개발자 커뮤니티나 동기, 선배 등 제가 가야 할 길을 미리 거쳐간 많은 사람들의 조언을 들을 수 있었는데, 그들이 입을 모아 말하는 것이 한 가지가 있습니다. 문제를 많이 풀어봐라. 고등학생때 비록 잘하지는 못했지만 수학이라는 학문을 공부한 경험으로 왜 하나같이 입을 모아 이런 말을 하는지 알 수 있었습니다. 어떤 학문에 있어서 그 법칙과 개념들은 객관적인 것들입니다. 그러한 것들은 우리가 공부를 통해 받아들일 수 있습니다. 하지만 그러한 법칙과 개념들을 응용하는 것은 그저 그것을 알게 되는 것과는 전혀 다른 차원의 문제입니다. 여기서 프로그래밍 선배들이 해주신 조언..
2019.11.25