반응형 Algorithm143 [DFS, 난이도 중하] 백준 11403번 경로 찾기 표를 직접 이용하는 방법 보다는 그래프로 도식화해서 해결하는 것이 더 편한 방법 같다. 고로 도식화를 하여 DFS로 해결 하였다. 아래 그림은 예제 입력2 의 인접행렬을 그래프로 도식화 한 것이다. 경로벡터 a에 간선 정보들을 모은 후 각 노드마다 dfs를 수행해주면 된다. dfs의 매개변수는 s, x로 설정했는데 s는 첫 출발 노드고, x는 현재 노드이다. 접근 할 수 있는 노드들을 모두 방문하며 ans[첫출발 노드][현재 노드]를 1로 갱신 해나가는 전략이다. 이 문제가 정답률이 52%로 높은 편인 이유는 예제를 2개나 주었고, 시간 및 노드 제한이 널널해서 인 것같다. 이 소스코드에서 노드별로 dfs를 수행할 때 자신보다 낮은 노드 번호를 가지는 노드의 접근 가능 노드 목록은 이미 계산이 되어 있는.. 2020. 8. 14. [그리디, 난이도 중] 백준 1931번 회의실배정 첫 그리디 문제풀이 포스팅이다. 다이나믹(동적계획법) 알고리즘과 그리디(탐욕) 알고리즘의 차이는 이 포스팅에서 다루었다. https://kimcoder.tistory.com/32 [동적계획법, 난이도 중] 백준 1463번 1로 만들기 첫 번째 동적계획법 문제풀이 포스팅이니, 동적계획법이 뭐하는 알고리즘인지 설명이 필요할 것이다. 동적계획법은 간단하게 말하면 바로 해답을 구하는 것이 아니고, 이전에 계산했던 값을 활 kimcoder.tistory.com 여러 회의들의 시작 시간, 끝 시간을 알아내어 최대한 많은 회의를 하는 경우를 계산해야 하는 문제이다. 회의가 끝나는 시각이 이른 순으로 정렬하고, 끝나는 시각이 같다면 시작 시각이 늦은 순으로 추가 정렬을 해준다. 이 문제의 정답률이 28%인 이유는 아마.. 2020. 8. 14. [BFS, 난이도 중상] 백준 2146번 다리 만들기 본인은 두 Step으로 나눠서 문제를 해결하였다. 큐는 각각 q,q2 이라는 이름의 큐 총 2개를 사용하였다. Step1에서는 q를 이용해 아래 그림과 같이 나라별로 숫자로 분류하였다. Step2에서 BFS를 수행하면서 어떤 나라를 만났을 때, 그게 자신의 나라인지 남의 나라인지 구별하는 과정을 거칠 것이기 때문이다. 이 과정 때문에 개인적으로 이 문제의 난이도는 중상으로 평가한다. Step2에서는 q2로 모든 지도를 탐색하여 방문하지 않은 바다 좌표를 만날 때마다 큐에 넣고, 방문 처리를 한다. 만약 탐색한 나라가 출발한 나라와 다를 경우, 구조체 node 에서 다리의 길이를 의미하는 depth 를 found 변수에 넣고 최솟값을 업데이트 해나갔다. g -> 나라 번호 depth -> 다리 깊이 x,y.. 2020. 8. 13. [동적계획법, 난이도 중] 백준 1463번 1로 만들기 첫 번째 동적계획법 문제풀이 포스팅이니, 동적계획법이 뭐하는 알고리즘인지 설명이 필요할 것이다. 동적계획법은 간단하게 말하면 바로 해답을 구하는 것이 아니고, 이전에 계산했던 값을 활용하는 알고리즘이다. 해답을 바로 구하는것은 그리디(탐욕) 알고리즘이다. 동적 계획법은 대부분 점화식을 요한다. 그런데 해답을 바로 구하는 것이 아니라는 말이 무슨말인가 이해가 안될 수 있다. 이번 문제가 이를 설명할 좋은 예가 될것이다. 예제 입력2 에서 입력값으로 10을 줬을 때 3이 출력되는데 아래 사진이 접근 과정이다. s배열=save배열 식을 보면 인덱스 0부터 순차적으로 계산해나가며 이전에 계산했던 값을 활용하고 있다. 다르게 말하면 입력값 10까지의 경우를 모두 계산했다는 말도 된다. 이러한 방식으로 접근하는 알.. 2020. 8. 13. [DFS, 난이도 중상] 백준 1987번 알파벳 DFS 첫 문제부터 조금 욕심을 내서 정답율 30%인 문제를 골랐다. 한 번만에 성공해서 되게 좋았다. DFS는 주로 스택이나 재귀 함수를 이용하는데, 개인적으로 재귀 함수가 훨씬 편한 것 같다. 제일 먼저 node라는 이름을 가진 구조체를 선언하였다. BFS 문제들을 풀면서, 탐색 문제에는 구조체를 활용하는것이 효과적이라는 사실을 깨달아서 바로 활용해 본 것이다. 구조체 안의 변수는 깊이,좌표 정보들로 구성시켰다. 시작점은 1행 1열이므로 좌표는 (0,0), 깊이는 1인 구조체 node를 맨 처음dfs 매개변수에 넣으며 시작했다. 상하좌우를 탐색하며 현재까지 처음 마주보는 알파벳만 그 좌표를 방문처리 하고 재귀함수를 호출했다. 그리고 재귀함수에서 나왔을 때 방문처리는 취소했다. dfs문 중간에서 -65.. 2020. 8. 12. [BFS, 난이도 중] 백준 14502번 연구소 내 접근 법은 연구실 지도에서 빈칸인 좌표를 모두 v벡터 안에 넣고 벽을 세울 3곳의 좌표를 고르는 모든 경우의 수를 탐색하는 것이다. 브루트포스와 짬뽕인 문제인것같다. 지도의 크기가 최대 8x8 이라 순열을 이용하여 모두 탐색해도 시간 초과는 나지 않는다. 모든 케이스마다 casemap 배열을 초기 map과 같게 해주고 바이러스가 들어있는 좌표를 모은 큐도 다시 채워줘야 한다. a=v.size()-3 b=v.size()-2 c=v.size()-1 일 때는 모든 경우를 탐색했다는 뜻이므로 break문으로 빠져나와서, 안전 구역의 넓이의 최댓값을 출력하면 된 문제가 해결된다. #include #include #include #include #include #include #include using name.. 2020. 8. 11. [BFS, 난이도 중하] 백준 2468번 안전 영역 Case(물에 잠기는 최대 높이)별로 안전 지역이 모두 다르기 때문에 casemap이라는 임시 배열을 두었다. map배열의 각각 요소에 물에 잠기는 최대 높이를 빼준 배열이 casemap이 된다. 즉 casemap배열의 요소가 1이상이면 그 좌표는 안전 영역이 되는 것이다. 이 casemap 배열로 BFS를 수행하여 while문을 탈출할 때마다 group변수에 1을 추가하여 몇 개의 안전 영역 그룹이 생기는지 계산한다. 물에 잠기는 최대 높이를 1부터 99까지 99가지 경우에 대해 탐색하여 케이스별 group을 구해내면 된다. 케이스가 종료 될 때마다 ans의 최댓값을 업데이트 해나가며, 모든 케이스를 다 탐색 했을 때 최종 ans 값이 이 문제의 해답이 된다. #include #include #incl.. 2020. 8. 11. [BFS, 난이도 상] 백준 2206번 벽 부수고 이동하기 정답율 23%의 다소 까다로운편인 문제이다. 아무리 고민해도 해결하지 못한 비슷한 유형의 문제가 있었다. 그 문제는 백준 13460번의 구슬 탈출2 이였다. 주어진 예제는 다 돌아가는데.. 반례가 생기고 그 반례까지 돌아가게 하니 또 다른 반례가 생기고... 나 자신과의 혈전이었다. 구슬 탈출 2의 해결법이 정말 궁금했던 나는 Google Chance를 썼다. 이 유형의 문제는 구조체 와 모든 방문경우 를 다뤄야 한다는 사실을 깨닫고 내가 깨달은 해당 유형의 문제 풀이법을 4줄 요약해보았다. 한 map 안에 여러 물체가 동시에 움직여야 하는 경우 구조체 이용 2개 이상의 물체가 겹칠 수 없는 경우의 처리 -> 겹침의 여부에 상관없이 일단 논리적으로 모두 이동시켜놓은 후에 조건에 맞게 2차 처리 수행 노드.. 2020. 8. 10. [BFS, 난이도 중상] 백준 2573번 빙산 지금까지 BFS를 풀어왔듯이 빙산이 몇 개의 덩어리로 되어있는지는 bfs의 while문이 끝날 때마다 1씩 추가하는 group변수의 최종 값으로 알 수 있다. bfs의 while문을 다 돌았다는 것은 덩어리 하나를 모두 방문했다는 의미다. BFS를 수행하기 전에 빙산이 녹을 때마다 즉, 1년마다 빙산이 녹은 상태로 map배열을 바꿔주어야 한다. 문제 해결 흐름은 1. map배열입력 2. 1년이 지난 후의 빙산상태로 map배열을 업데이트 3. BFS로 몇 덩어리인가 계산 4. 여전히 1덩어리일 경우 과정2번으로 이동, 2덩어리 이상일 경우 정답 출력 이런 흐름으로 이루어 진다. adjacent 배열은 주변에 인접한 바닷물칸의 수를 나타내는 배열이다. map 배열에서 빙산의 높이가 0보다 작아졌을 경우에는 .. 2020. 8. 10. 이전 1 ··· 12 13 14 15 16 다음
