dfs
-
4012.요리사알고리즘/SW Expert Academy 2020. 8. 6. 22:41
이번에 풀어볼 문제는 SW Expert의 4012번 요리사이다. SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 지금까지 풀었던 SW Expert 문제 중에 문제가 가장 애매하게 출제된 거 같다. 그 이유는 식재료에 대한 중복내용이 없기 때문에 어떻게 풀어아햐는건지 확실하지 않다고 느꼈기 때문이다. 하여튼 간에 문제를 처음 읽어보면 어떤 부분이 애매한지 느낄 수 있을 것이다. 애매한 부분만 빼면 재귀함수를 연습하기에는 괜찮은 문제인 거 같다 => 나는 재귀를 잘못해서 조금 골치아팠다.. 이 문제는 결론적으로 조합 문제이다. 결국 시너지를 만들어 내기 위함인데 두 가지의 조합이 들어가있다. 1. 음식A와 B에 대..
-
2105.디저트 카페알고리즘/SW Expert Academy 2020. 6. 27. 12:05
이번에 풀어볼 문제는 SW Expert 2105번 디저트 카페이다. 재귀함수를 이용해서 풀면 간단히 풀리지만 중요한건 역시나 설계이다. 어떻게하면 불필요한 계산을 줄일지 고민해보고 풀어야한다. SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 각 모서리 값은 굳이 탐색을 할 필요가 없다 => 우리가 탐색하는 형태는 마름모 모양이므로 각 모서리는 탐색을 할 수 없다는 것을 인지 2. 항상 탐색의 시작은 아래로만 탐색하면된다. => Point !! => 탐색은 왼쪽에서 오른쪽으로, 윗줄부터 아랫줄로 탐색이 진행되는데 그림을 그려보면 알겠지만 윗줄에서 탐색한 내용들은 전부 아랫줄에서 위로 탐색하는 부분과 일치한다..
-
1767.프로세서 연결하기알고리즘/SW Expert Academy 2020. 6. 16. 23:37
이번에 풀어볼 문제는 SW Expert의 샘플 문제 1767번 프로세서 연결하기이다. 굉장히 재미있는 문제였던거 같다. 물론 한 번에 못풀었다.. 처음 도전했을 때는 끝에가서 설계를 잘못했다는 걸 깨달았고 다음날 다시 처음부터 풀었다. 항상 말하지만 충분한 생각과 설계가 중요하다. 두 번째 다시 도전했을 때 충분한 생각과 설계 후 한 번에 맞았다. => 한 번에 맞았다는 것과 나의 설계가 맞아서 그런지 기분이 좋다ㅎㅎ SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 나의 설계는 다음과 같다. 1. 벽면에 붙어 있는 Core들은 바로 전원이 연결되기 때문에 탐색에서 제외한다. 2. 나머지 Core들을 탐색하되 가..
-
1949.등산로 조성알고리즘/SW Expert Academy 2020. 6. 3. 22:51
이번에 풀어볼 문제는 SW Expert의 1949 등산로 조성이다. ( 아래링크는 SW Expert 로그인하고 눌러야함.. ) SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 난이도는 높지않지만 한 가지를 빼먹어서 테스트 케이스 50개중 48개만 맞았다.. 제엔자앙!!!!!!! => 완벽한 설계인줄 알았는데... 닿을 듯 말 듯하네.. ㅎㅎ 여기서 중요한 점은 깎는 점에 대한 처리인데 언제깎아야할지는 생각보다 간단하다. 0. 제일 높은 봉우리를 찾고난 뒤 => 제일 높은 봉우리 일때만 해당좌표를 시작으로 탐색을 진행한다. => 탐색(BFS)은 재귀함수로 진행!! => 그렇지 않으면 c..
-
2468.안전영역알고리즘/백준 BAEK JOON 2020. 5. 26. 23:01
이번에 풀어볼 문제는 백준의 2468 안전영역이다. BFS, DFS(재귀,스택,큐)로 풀이가 가능하다. 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 나는 BFS를 이용해서 풀이를 진행하였고 난이도는 역시 그렇게 어려운 편은 아니다!! 모든 문제가 그렇지만 설계단계를 잘생각해서 진입해야 헤매지 않고 풀이에 성공할 수 있다. 이 문제는 직전에 포스팅 한 문제들과 다를 바없이 탐색이 문제를 푸는관건이 아니라 탐색 이전까지의 로직을 구현해내는 것이 관건인 문제이다. 이 문제에서는 물에 잠기는 최소높이와 최고높이를 저..
-
7576.토마토알고리즘/백준 BAEK JOON 2020. 5. 25. 21:18
이번 문제는 토마토이다! 비교적 쉬운 문제에 속한다. BFS를 이용하면 간단히 풀 수 있는데 BFS로 퍼지면서(토마토가 익으면서) 내부의 값(걸리는 시간값)을 잘 지정해주어야한다! 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net #pragma warning(disable:4996) #include #include #define MAX 1001 using namespace std; int n, m; int map[MAX][MAX]; int dx[4] = { -1, 1, 0..
-
14502.연구소알고리즘/백준 BAEK JOON 2020. 5. 25. 07:09
이번 문제는 연구소이다. 꽤 많이 중요한 내용을 배우고 상기할 수 있는 문제였다. 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 이 문제를 푸는데 핵심은 맵을 복사해서 사용한다는 것과 나머지는 탐색이다. 난이도는 어려운 수준이 아닌 거 같지만 초보자에게 연습하기는 좋은 문제인 것 같다( 난 초보자 ㅠㅠ.. 너무좋네...) 재귀함수 관련된 문제를 조금 더 풀어봐야할 것 같다. * 문제풀면서 중요한점 1. 문자, 특수기호 실수 => 실수로 자꾸 if문 다음에 변수에 값을 대입할 때 "=" 대신 "=="를 사용하여 틀림 주의..
-
2667.단지번호붙이기알고리즘/백준 BAEK JOON 2020. 5. 21. 23:40
이번에 풀어볼 문제는 단지번호붙이기이다. 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 생각보다 이상한곳에 막혀서 시간낭비를 했다. 시간은 1시간 30분정도 걸렸고 목표한 시간보다 30분이나 초과되었다. 사실 30분컷 낼 수 있었는데 이걸 코드하나를 잘못집어넣어서 하루종일 걸렸다.. 후... DFS를 이용해서 풀었고 이 문제의 포인트는 Stack를 이용하되 Stack에 자신이 이동한 부분의 좌표를 넣어주는 것이다. 그래야지 DFS로 쭈욱 탐색하다가 막혔을 때 다시 돌아가서 탐색하지 않은 방향으로 탐색을 진행..