본문 바로가기

전체 글145

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.
적록색약 #10026 c++ 풀이 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 부끄럽지만, 빠르게 풀기위해서 함수를 비효율적으로 사용해서 풀었다. #include #include using namespace std; int n_R = 0; int n_R1 = 0; int n_G = 0; int n_B = 0; int n_B1 = 0; int N; int graph[101][101]; int graph2[101][101]; //적록색맹의 그래프 int visited[1.. 2023. 11. 1.

티스토리툴바