알고리즘204 [백준] 9372번 - 상근이의 여행 (C++) 문제 및 풀이 문제) 백준 - BFS - 상근이의 여행 https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 어떤 그래프로든 풀이가 가능하다. bfs가 제일 편해서 구현했다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%205000~9999/9372_%EC%83%81%EA%B7%BC%EC%9D%B4%EC%9D%98%20%E.. 2021. 11. 7. [백준] 7579번 - 앱 (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - 앱 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 메모리를 memoization을 진행하면 메모리 초과로 터진다. dp[idx][Cost]: Cost로 idx번째 앱에서 얻을 수 있는 최대 메모리를 계산한다. Cost를 0부터 증가시켜 M보다 클 경우 break 하여 출력한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main.. 2021. 11. 7. [백준] 12852번 - 1로 만들기 2 (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - 1로 만들기 2 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net Top-Down 방식으로 해결했다. 1로 만들수 있는 모든 경우를 memoiztion을 진행하면서 trace에도 memo를 진행한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/12852_1%EB%A1%9C%20%EB%A7%8C%EB%93%A4%EA%B8%B0%202.cpp GitHub - Chocochip101/BO.. 2021. 11. 6. [백준] 11060번 - 점프 점프 (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - 점프 점프 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net cache[idx]: idx에서 n-1번 칸까지 갈 수 있는 최소 점프 횟수. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/11060_%EC%A0%90%ED%94%84%20%EC%A0%90%ED%94%84.c.. 2021. 11. 4. [백준] 9507번 - Generations of Tribbles (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - Generations of Tribbles https://www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보 www.acmicpc.net n이 3 이하 일 경우의 기저 사례 처리와 점화식을 이용해 memoization을 적용한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%205000~9999/9507_Generations%.. 2021. 11. 3. [백준] 14728번 - 벼락치기 (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - 벼락치기 https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 한정된 시간에 최대 점수를 내기 위해 선택해야하는 전형적인 냅색(배낭) 문제. DP(인덱스, 남은 공부 시간)으로 해결할 수 있다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999.. 2021. 11. 2. [백준] 13565번 - 침투 (C++) 문제 및 풀이 문제) 백준 - DFS - 침투 https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net dfs를 통해서 visited 배열을 갱신 후, inner side에 도달했는지 확인한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/13565_%EC%B9%A8%ED%88%AC.cpp GitHub .. 2021. 11. 1. [백준] 23251번 - 스물셋 (C++) 문제 및 풀이 문제) 백준 - 구현 - 스물셋 https://www.acmicpc.net/problem/23251 23251번: 스물셋 첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 둘째 줄부터 $T$줄에 걸쳐 정수 $k$가 주어진다. www.acmicpc.net C++ 소스코드) 2021. 10. 25. [백준] 17780번 - 새로운 게임 (C++) 문제 및 풀이 문제) 백준 - 구현 - 새로운 게임 https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 1000번 동안 체스판의 위에 말이 4개 이상 있는지 확인한다. 체스판 위에 말이 쌓여 있는 것을 표현하기 위해 이차원 벡터(vector ChessBoard[13][13])를 처음 사용해 봤는데를 사용했는데 익숙해질 필요가 있다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/ma.. 2021. 10. 24. 이전 1 ··· 13 14 15 16 17 18 19 ··· 23 다음 반응형
