본문 바로가기

분류 전체보기162

RGB거리 #1149 c++ 풀이 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 집을 색칠할건데, 비용이 가장 작은 경우를 출력하라는 dp문제이다. 경우의 수는 다음과 같다. 이번에 R을 칠할 것이면, 다음에는 GB중 하나를 선택해야한다. 이번에 G을 칠할 것이면, 다음에는 RB중 하나를 선택해야한다. 이번에 B을 칠할 것이면, 다음에는 RG중 하나를 선택해야한다. 3가지 경우의 cost를 전부 세야하는구나를 알았다. 따라서 RGB로 시작하는 각각의 비용.. 2023. 11. 6.
N과 M 시리즈 ( 순열, 조합, 중복순열, 중복조합 ) 15649, 15650, ..등등 N과 M을 받았을때 순열과 조합을 만드는 코딩 문제를 해결하면서, dfs에 대해서 깊게 생각해볼 수 있는 계기가 되었다. 1. 정의 2. 코딩 3. 예제 순으로 글을 쓸 것이다. 나름의 정의를 내린다. 순열 : 순서에 따라 결과가 달라지는 수의 모임 {1,2,3} != {2,1,3} 조합 : 순서가 상관없는 수의 모임 {1,2,3} == {2,1,3} 순열과 조합의 코딩스타일을 이해하기 위해서 https://yabmoons.tistory.com/99 [ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++) 브루트포스 알고리즘에서 가장 많이 사용되는 방법이 순열과 조합등으로 모든 경우의 수를 모두 계산해본 뒤에 원하는결과 값을 찾는 방식이다. 이 글에서는, .. 2023. 11. 2.
BFS, DFS 활용 문제 고찰 BFS 문제를 많이 접하다 보니, BFS 문제 유형에 대해서 생각해보게 되었다. 나는 문제를 일반화 시키는 것을 선호한다. 만능은 없지만 정답에 가까워지기 편하기 때문이다. 먼저 그래프를 사용해야할 것 같다는 감이 올 때, 그 감에 대해서 정의해보려고한다. 그래프 문제의 경우 1. 어디부터 어디까지 도달한다 2. 가는 길을 묻는다 3. 가는 길의 횟수를 묻는다 4. 영역을 나눈다 5. 전염? 된다 이런 식의 힌트를 문제에서 제공한다. 의심의 여지없이 그래프를 사용해야하고, 그래프 탐색 알고리즘을 사용해야하는 경우가 많다. 그래프 탐색 알고리즘 중 bfs를 사용해야할 때와 dfs를 사용해야할 때는 명확한데, 각각의 특성을 고려했을때 그 문제가 어느 알고리즘으로 해결해야할지 더욱 명확해진다. - 결국 bfs.. 2023. 11. 1.
A -> B #16953 c++ 풀이 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net bfs가 단방향으로 한번만 도는 경우, visited가 필요없을 수 있겠구나 하는 생각이 들었다. #include #include using namespace std; long long int A, B; //int graph[100000000]; //int visited[100000000]; int cnt; void bfs(long long int A) { queue q; q.push(make_pair(A,0)); while (!q.empty()) { long long int curr = q.front().first; l.. 2023. 11. 1.

티스토리툴바