본문 바로가기

분류 전체보기89

[DP] 백준 2225 합분해 C++ https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 : 0 부터 N 까지 숫자 중 K개의 합이 N이 되는 경우의 수를 구하는 문제 dp인건 알겠는데 막상 풀려면 조금 막막하다. 숫자가 작은 경우 부터 생각하고 초깃값 설정과 점화식도출이 초점을 맞춰서 풀어보자! 우선 N이 값이 얼마든 한개를 뽑아서(K=1) N이 되게하는 경우? 당연히 1가지이다.(해당 숫자 N을 뽑으면 됨) 그다음 부터가 중요한데 작은 숫자부터 차근히 생각해 보자 내가 생각하는 가장 직관적인 풀이는 dp[K][N] = 0~N까지 K개의 수를 뽑아 합이 N이 되게하는 경우의 수 일때, dp[K][N] =.. 2021. 9. 1.
[이분탐색] 백준 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 풀이 : 기본적인 이분탐색 문제 풀이! STL라이브러리에 binary_search 함수가 정의 되어 있지만 이분탐색 문제를 많이 풀어보진 않아서 간단한 문제정도는 직접 함수를 구현해 보려한다. while문 사용도 가능하지만 재귀함수 사용해서 풀어봄 기본적인 원리는 배열을 정렬한 후 mid 값을 이용해서 목표값을 찾는 방법이다! 가령 [1,2,3,4,.. 2021. 8. 30.
[그리디] 백준 1339 단어수학 C++ https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 : 가장 긴 자리수를 가진 알파벳부터 순서대로 9, 8, 7 ... 이런식으로 대입해서 계산하면 된다. 그래서 각자리 수를 가진 배열을 따로 만들고.. 나름대로 방법을 적용했는데 실패해서 솔루션을 찾아본 문제 가장 긴 자리수를 어떻게 찾을까? -> 10의 거듭제곱을 사용하면 된다 예제에 나온대로 GCF + ACDEB 경우 각 자리수를 10의 거듭제곱을 이용해서 표현해보면 GCF = 10.. 2021. 8. 28.
[DFS] 백준 2468 안전영역 C++ https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 : 기본적인 dfs 문제지만 주의해야할 조건이 몇개 있어서 버그를 찾는데 애를 먹었다.. 접근 방법은 단순하다 앞서 영역의 갯수를 새는 문제는 몇번 풀어봤듯이 젖은 영역을 wet배열에 지정하고 젖은 땅의 경우는 탐색을 하지 않고 젖지 않은 땅중에 방문하지 않은 땅을 dfs로 탐색하면 된다! 그리고 총 호출되는 dfs횟수를 세면 영역의 수를 구할 수 있다! (dfs 내부에서 영역의 최솟값, 최댓값 이.. 2021. 8. 26.
[DP, DFS] 백준 1520 내리막길 C++ https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 : 일반적인 DFS로 풀었다가 시간초과나서 한참을 고민한 문제.. 결국 인터넷에서 풀이를 찾아봤는데 핵심은 DP를 쓰는 것이다 백트래킹인가 해서 삽질을 몇시간 했는데 결국 풀지 못함.. 결국 DP배열로 경로를 저장해두면 쉽게 풀린다. 경로를 저장한다는 개념이 좀 추상적인데 결국 map[0][0] 에서 map[m-1][n-1] 까지 가는 경로의 수를 구하는 문제 이므로 dp[i][j] 란 (i, j.. 2021. 8. 24.
[BFS] 백준 10026 적록색약 C++ https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 : 항상 느끼지만 백준 난이도는 좀 이상하다 실버 문제 못 풀때도 많은데 골드 문제라고 잔뜩 쫄아서 문제 읽어봤는데 그냥 BFS 두번 돌리면 되는거 아니야? 생각들어서 하나는 R과 G를 구분할 때 , 하나는 R과 G를 같은 색으로 취급할 때 이렇게 두개의 map을 만들어서 bfs함수를 두번돌렸더니 결과는 맞았다. 해결전략을 간단히 설명하면 주석에도 써놓았는데 R: 1, G: 2, B:.. 2021. 8. 18.

티스토리툴바