DFS5

• 

  백준 1303 : 전투 DFS BFS 풀이 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 문제 전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다. N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의.. Java - 알고리즘 2022. 7. 17.

• 백준 문제 풀이 : 14659 한조 서열 정리, 1339 단어 수학 오늘 스터디에서 풀었던 문제입니다. 한조 서열 정리는 어떻게어떻게 스스로 했는데...단어 수학 문제는 3시간 고민하고도 도저히 안될 것 같아서 결국 저보다 똑똑하신 많은 다른 개발자님들의 힘을 빌렸습니다ㅠㅠ 1. 한조서열정리하고옴ㅋㅋㅋ 이 문제는 다르게 푸는 방법도 있겠지만 저는 최근에 공부하고 있는 DFS 로 풀어봤습니다. 자세한 설명은 주석 참고 부탁드립니다 https://www.acmicpc.net/problem/14659 14659번: 한조서열정리하고옴ㅋㅋ 첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000) 둘째 줄에 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. (1 ≤ 높이 ≤ 100,000) 각각 봉우리의 높이는 중복 없이 www.acmicpc.n.. Java - 알고리즘 2022. 6. 25.

• DFS 문제풀이 : 중복순열 다루기, 거스름돈 계산하기 이번에는 중복순열을 Java 코드로 만들어보고, 관련 문제를 풀어볼 것입니다. 사실 저는 고딩때 순열, 조합 이런 것들을 정말 정말 싫어했었는데... 고등학교 졸업 후 약 10년 만에 이런 문제들을 다시 봤지만, 사람은 변하지 않나 봅니다. 여전히 싫네요ㅠ 1. 중복순열 다루기 ※ 설명 1부터 N 까지 적힌 구슬에서 중복을 허락하여 M번 뽑아서 나열하라 ※ 입력 첫 번째 줄에 자연수 N(3 for 문 시작 pm[0] = 1; && dfs(index+1) == dfs(1) // 2. dfs(1) 이 시작됨 => for 문 시작, i=1 일 때 pm[1] = 1 && dfs(index+1) == dfs(2) // 3. dfs(2) 는 곧 index == 2 임을 의미하고, m = 2 때문에 index == .. Java - 알고리즘 2022. 6. 19.

• DFS 문제풀이 : 바둑이 승차, 잔돈 계산하기 오늘은 DFS 관련 문제를 풀고 공부해봤습니다. 코드에 대한 설명은 주석에 달아두었습니다. 1. 바둑이 승차 ※ 설명 철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요. ※ 입력 첫 번째 줄에 자연수 C(1 Java - 알고리즘 2022. 6. 19.

• 

  자바 알고리즘 - 이진트리 순회, DFS 오늘은 DFS 깊이 우선 탐색에 대해서 공부하였다. 새로운 것 두 가지를 알았는데 - DFS 는 생각보다도 훨~~씬 어렵고 심오하다는 것과 - 바로 이 DFS 로 조합과 관련된 문제를 풀 수 있다는 것 이다. 사실 지금까지는 조합과 관련된 문제를 풀어보려고 몇 번 뒤적뒤적 했던 적이 있다. 그럴때마다 문제도 이해가 안되었지만, 대체 이걸 코드로 어떻게 짜는거지? 라고 생각될 때가 많았다. 그렇다, 문제가 어려웠던 것은 그렇다치고, 조합에 관한 부분을 대체 어떻게 짜는거지? 하면서 뭔가 풀이 방법조차 떠오르지 않았던 것은 바로 이 DFS , BFS 에 대해서 공부하지 않았기 때문이었다. 앞으로 적을 DFS 와 BFS 의 개념은 엄청 엄청!!! 아주아주 매우매우 중요하다. 이걸 쓰는 코딩 테스트 문제들은 물.. Java - 알고리즘 2021. 11. 11.