개발 언어 및 알고리즘 기초/C언어로 푸는 백준 (32) 썸네일형 리스트형 [백준 1463번/C언어] 1로 만들기, 동적계획법으로 풀이 백준 1463번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 백준 1473번: https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 내용은 아래와 같습니다. 사실 이전에 업로드한 모든 DP 문제들의 경우, 이 문제에서 막혀 DP에 대해 공부를 시작하면서 풀었던 문제입니다. 이 문제를 접할 당시만 해도 DP에 대한 지식이 없어, 고민을 정말 많이 했는데도 답이 나오지 않던 중, DP로 접근해서 풀어야 하는 문제임을 깨닫고, 더 쉬운 DP 문제부터 시작하여 다시 여기까지 와서 풀게 되었습니다. DP 개념을 모를 경우 풀기.. [백준 1149번/C언어] RGB거리, 동적계획법으로 풀이 백준 1149번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 백준 1149번: https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 내용은 아래와 같습니다. 예제 입출력이 더 준비되어 있으니, 위 링크를 통해 확인하시기 바랍니다. 이 문제 역시 이전에 업로드한 다른 DP를 이용한 문제와 마찬가지로 동적계획법 학습을 위해 푼 문제입니다. 따라서 동적계획법에 익숙하지 않으시다면, 아래 .. [백준 9461번/C언어] 파도반 수열, 동적계획법으로 풀이 백준 9461번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 백준 9461번: https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 내용은 아래와 같습니다. 이 문제 역시 이전에 업로드한 다른 DP를 이용한 문제와 마찬가지로 동적계획법 학습을 위해 푼 문제입니다. 따라서 동적계획법에 익숙하지 않으시다면, 아래 블로그를 참고해 주시기 바랍니다. 저 역시 동적계획법 문제를 처음 접해보기 때문에 다양한 글들을 꼼꼼.. [백준 2579번/C언어] 계단 오르기, 동적계획법으로 풀이 백준 2579번 문제를 Dynamic Programming (DP, 동적 계획법)으로 풀어보았습니다. 문제 내용이 길어 따로 캡쳐본을 첨부하지 않았으니, 링크를 참고하면서 봐주시면 됩니다. 백준 2579번: https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 이 문제 역시 이전에 업로드한 피보나치 수열과 마찬가지로 동적계획법 학습을 위해 푼 문제입니다. 따라서 동적계획법에 익숙하지 않으시다면, 아래 블로그를 참고해 주시기 바랍니다. 저 역시 동적계획법 문제를 .. [백준 2748번/C언어] 피보나치 수, 두 가지 접근법으로 풀기 백준 2748번 문제를 Dynamic Programming (DP, 동적 계획법)의 두 가지 접근 방법인 Top Down 방식과 Bottom Up 방식으로풀어보았습니다. 백준에 제출 시에는 실행 횟수를 절감할 수 있는 Bottom Up 방식만 제출했으니 참고해주시기 바랍니다. 백준 2748번: https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 문제 내용은 아래와 같습니다. 우선 피보나치 수열은 첫번째, 두번째 .. [백준 2751번/C언어] 수 정렬하기, Merge Sort로 풀이 백준 2751번 문제를 Merge Sort로 풀어보았습니다. 처음에는 Quick Sort로 풀이했으나, 계속 정답처리 되지 않아 찾아보니 Quick Sort는 거꾸로 정렬되어 있을 경우 O(N^2)의 시간복잡도가 발생하기 때문에 시간초과로 인한 오답이라는 정보를 얻게 되었습니다. 따라서 이를 보완하고자 Merge Sort로 풀이하여 최종적으로 정답처리될 수 있었습니다. 백준 2751번: https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net.. [백준 1436번/C언어] 영화감독 숌 브루트포스로 풀이 백준 1436번 문제를 브루트포스 알고리즘으로 풀어보았습니다. 백준 1436번 : https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 문제 내용은 아래와 같습니다. 예제 입출력은 7개가 준비되어 있으니, 접속하여 확인하기 바랍니다. 여기서는 최소한의 문제 이해를 위한 첫 번째 예제만 두었습니다. 우선 해당 문제를 해결하기 위해 브루트포스(brute force) 알고리즘을 알아보았습니다. 브루트포스를 직역하면 '무식한 힘'이라는 뜻으로, 그 뜻에 .. [백준 1018번/C언어] 체스판 다시 칠하기 브루트포스로 풀이 백준 1018번 문제를 브루트포스 알고리즘으로 풀어보았습니다. 백준 1018번: https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 내용은 아래와 같습니다. 예제 입출력은 7개가 준비되어 있으니, 접속하여 확인하기 바랍니다. 여기서는 최소한의 문제 이해를 위한 첫 번째 예제만 두었습니다. 우선 해당 문제를 풀기 위한 브루트포스(brute force) 알고리즘을 알아보았습니다. 브루트포스를 직역하면 '무식한 힘'이라는 뜻으로, 그 뜻에 .. 이전 1 2 3 4 다음
