📚 알고리즘
[백준 10026] 적록색약_bfs(c++)
1. 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G( www.acmicpc.net 2. 접근법 굳이 3차원배열로 안풀어도 될거같은데 저번주에 3차원배열로 푸는거에 꽂혀서 3차원 배열로 풀어봤다.. 적록색약인사람과 아닌사람의 방문체크배열을 따로 만들면 됐지만 나는 그냥 3차원 배열로 했다. 이것도 구역의 갯수를 구하는 것이기때문에 모든 정점을 다 방문해야 될것이라고 판단. 영역의 각 넓이는 구하지 않아도 되므로 전역변수로 area_cnt를 두고 영역의 갯수를 카..
[백준 11057] 오르막수_dp(c++)
1.문제 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 2.접근방법 이것도 처음에 dfs백트래킹인지 dp인지 헷갈렸음(결국 너무 생각해내기 어려워서 다른 사람들 아이디어 살짝 봤다..) 나의 바로 전에 숫자가 무엇이 오는지에 따라 고를 수 있는 수가 달라짐 3.문제풀이 dp[] (행의 인덱스) dp[][] (열의 인덱스 자리수를 표현 0~9까지의 숫자를 표현 n까지의 자리수 중에서 첫번째 자리수는 모든 숫..
[백준 2583] 영역구하기_bfs(C++)
1.문제 https://www.acmicpc.net/problem/2583 2.접근방법 bfs로 영역을 나눠야 겠다고 바로 생각!(게리맨더링이랑 비슷하다고 생각했다) 탐색시작점이 따로 없으니, 어디서부터 시작할지 고민했음 첫번째 영역의 탐색이 끝나고 나면(이동하면서 막혀서 더이상 이동할 수 없을때 영역이 정해짐) , 다음영역으로 어떻게 시작점이 넘어가야하는지 좋은 방법이 떠오르지 않음 결국 모든 점을 방문할 수 밖에 없겠다는 결론이 내려짐 ㅠ 한 점에서 시작 -> 큐가 비워짐 -> 첫번째 영역이 구해짐 -> 벡터에 넣는다 결국 벡터의 사이즈는 영역의 갯수가 됨 영역들의 넓이는 벡터 for문 돌면서 출력하면 됨 3.문제풀이 입력으로 주어진 사각형(넓이부분 전체 다 )을 map을 1로 만들어준다.(bfs를 ..