https://programmers.co.kr/learn/courses/30/lessons/12913 자세한 문제는 programmers를 통해 확인 해 주세요. 문제 땅따먹기라고 하지만, 우리가 알고있는 땅따먹기와는 거리가 있습니다. 차라리 어렸을 적 하고 놀던 "사방치기"를 떠올리는 것이 조금 더 가깝습니다. 맨 첫줄 부터 시작해서 1 2 3 5 5 6 7 8 4 3 2 1 한줄씩 아래로 내려가는데, 일단 지금 밟은 열은 다음번 행에서 또 밟을 수가 없습니다. 예를 들어 첫 줄에서 5로 시작했다면, 다음 줄에서는 8을 밟을 수 없습니다. 탐욕법 무조건 지금 상황에서의 최선을 선택하는 "탐욕법" 으로 문제를 푼다면 다음 줄에서 더 큰 숫자의 기회를 잃을 수 있기때문에 다른 접근이 필요합니다. 위의 예시..

Intro DFS DFS는 트리나 그래프에서 한 루트로 검색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인 한 뒤, 다시 돌아가 다른 루트를 탐색하는 방식입니다. 미로찾기를 생각하면 쉬운데요, 한 방향으로 끝까지 들어갔다가 막다른 길에 다다르면 (트리의 바닥에 도착) 왔던 길을 돌아가서 다른 방향으로 갑니다. 이 일을 찾는 값이 나올 때까지 혹은 모든 트리를 순회 할 때 까지 반복합니다. DFS의 가장 큰 약점은 깊이가 무한으로 이어지면 빠져나올 수 없다는 점 입니다. 미로를 가다보면 왔던길이 또 나타나는 그런 미로도 있습니다. 가끔 등산을 할때도 그런 길에 들어갔다가 왔던 길에 다시 도착하는 경험을 해본 분들이 있을텐데요, 이럴 경우는 BFS를 이용해 해결 해야 합니다. BFS BFS는 너비우선탐색 ..

Intro 재미삼아 취미로 시간 날때마다 한 두 문제씩 풀었던 programmers의 코딩 테스트 연습이 어느덧 100문제를 넘어갔습니다. for문과 배열만 있다면 어떤 문제든 해결 할 수 있다고 말씀해주신 학원 초급 자바선생님의 말씀대로, 왠만한 문제는 머리속으로 떠올린 아이디어를 간단하게 노트에 적어 구체화 시킨 후에 그것을 IDE 상에 코드로 구현을 하면 해결되지 않는 문제가 없었습니다. 하지만 어느순간부터는 빈번히 막히는 일이 발생했고, 이제는 문제를 만났을때 "n중 for문 으로 풀어야지!" 라는 말도 안되는 해결 방안이 제시되기 시작했습니다. 그간 외면했던 DFS/ BFS를 정면으로 마주해야 하는 순간입니다. (물론 탐색하는 과정은 결국 동일합니다) DFS DFS는 깊이우선 탐색 Depth F..