고슴도치의 IT여행

풀이 문제 : 백준 11726번 2×n 타일링 풀이 언어 : C++ 알고리즘 : 다이나믹 프로그래밍 문제링크 : https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제요약 문제는 매우 간단하다. 접근 방식 처음엔 짝수랑 홀수를 따로따로 생각해봤는데 아무리 해도 답이 안나와서 알고리즘 분류를 봤더니 다이나믹 프로그래밍 문제였다,, 다이나믹 프로그래밍은 문제를 보자마자 알고리즘이 떠오르지 않아 어려운거 같다. DP문제인 것을 깨닫고 나서 처음엔 재귀함수를 짜서 풀었다. ..

풀이 문제 : 백준 1158번 요세푸스 문제 풀이 언어 : C++ 알고리즘 : queue 문제링크 : https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제요약 원으로 이어진 배열에서 돌아가며 k번째 수를 제거하고, 제거한 순서대로 출력하는 문제다. 접근 방식 처음엔 구현문제 처럼 풀었다. while 문으로 숫자를 점점 키우면서 k번째가 되면 정답배열에 넣고, used 배열(visited 배열) 에 사용 표시를 하는 식으로 구현했다. 정답은 맞았지만 풀면서 약간 갸우뚱해서 구현 후 정답 코드를 봤다. queue를 이용해 k만큼 돌면서 p..

풀이 문제 : 백준 10815번 숫자카드 풀이 언어 : C++ 알고리즘 : 이분탐색 문제링크 : https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제요약 상근이가 가지고 있는 숫자 카드 배열 N과, 다른 숫자카드 M을 받고 M배열에 상근이의 숫자카드 N이 존재하는 지 확인하는 문제다. 1920번 문제와 매우 유사하므로 이번 문제가 어려웠다면 1920번 문제를 풀어보는 것을 권한다. [백준] 1920번: 수 찾기 /..

풀이 문제 : 백준 1920번 수 찾기 풀이 언어 : C++ 알고리즘 : 이분탐색 문제링크 : https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제요약 배열 N, M 두개를 받고 M배열에 N배열 안에 존재하는 지 확인하는 문제다. 접근 방식 처음엔 간단히 이중 for문으로 구성했더니 시간초과가 나왔다. 각 배열 크기가 최대 100,000라서 2중 for문 돌리면 1초가 훌쩍 넘기 때문이다. 그래서..

풀이 문제 : 백준 1463번 : 1로 만들기 풀이 언어 : C++ 알고리즘 : DP 문제링크 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 요약 접근 방식 가능한 연산이 세가지 뿐이니까 세가지 연산을 모두 해보고 횟수가 가장 적은 것을 누적하며 구하고자 하는 값까지 찾아올라가는 방식으로, dp 알고리즘을 사용했다. 코드 #include #include using namespace std; int dp[1000000]; int main() { dp[1] = 0; dp[2] = 1; dp[3] = 1; int n; cin >> n; for (int ..

풀이 문제 : 백준 9095번 : 1,2,3 더하기 풀이 언어 : C++ 문제링크 : https://www.acmicpc.net/problem/2742 2742번: 기찍 N 자연수 N이 주어졌을 때, N부터 1까지 한 줄에 하나씩 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 요약 문제는 겁나 쉽다. 시간초과 겁나 쉬운 문제가 시간초과가 났다.. 시간초과난 코드는 다음과 같다 #include #include using namespace std; int main() { int x; cin >> x; for (int i = x; i > 0; i--) { cout x; for (int i = x; i > 0; i--) { cout

풀이 문제 : 백준 9095번 : 1,2,3 더하기 풀이 언어 : C++ 알고리즘 : DP 문제링크 : https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 요약 입력 값을 1, 2, 3의 합으로 나타낼 수 있는 모든 방법의 수를 구해야한다. 1 + 2 와 2 + 1 는 다른 것으로 취급된다. 접근 방식 일단 입력되는 값이 11 미만의 정수이고, 각 케이스마다 값이 정해져 있다는 점을 파악했다. 또한 입력 값의 수가 커짐에 따라 정답인 수의 크기도 커진다.. 여기서 피보나치와 비슷하다는 느낌을 받았다. 1 : 1 (1) 2 : 2 / 1+1 ..

https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 문제 접근 방법 1. 스트라이크, 볼 갯수로 경우의 수 나누기 처음에는 스트라이크, 볼 갯수에 따라 경우의 수를 나눠서 구하려고 했다. if strike == 0 : elif strike == 1 : elif strike == 2: else: if ball == 0: ... 위와 같이 하려다가 경우의 수가 너무 복잡해져서 짜놓은 코드를 다 지우고 다시 생각해보았다. (그런데 다른 분들 풀이를 보니..