[코테 공부] 오늘 공부량

 

평소에 노드도 공부하고 코딩테스트도 하고 굉장히 바쁘게 보내고 있다. 오늘은 5문제를 풀었는데 DFS,BFS 2문제와 그리디 알고리즘 3문제 일 것 이다. 아마도...

 

DFS, BFS도 마찬가지로 그림으로 그리라고 하면 아주 쉽게 그릴 수 있는데 구현을 어떻게 해야할지 몰라서 인터넷에서 코드를 보면서 나도 써보면서 문제에도 적용시켜보면서 하나하나 몸에 녹여나가는 중이다.

 

그리디 알고리즘은 이게 그리디 알고리즘이 맞는가??? 일단 내가 생각하기에 그리디 알고리즘 문제는 확실한 이해를 기반으로 한 꼼수(?)를 찾아내는 것 같다.

 

예시로

 

55-23+20

 

위와 같은 문자열이 주어졌을 때 괄호를 통해서 최소값을 구하라가 문제였다. 최소값을 구한다는 것은 빼기하는 값을 가장 크게 해버리면 되는데 위의 경우엔

 

55-(23+20)

 

위 처럼 괄호를 쳐버리면 된다. 만약에 수가 엄청 많아진다면

 

A + B + C + D + E - F + G + H - U + I + O ...

 

이런식으로 진행하게 된다면 그냥 -를 찾아서 그 뒤는 모두 뺀다고 생각하면 되겠더라

 

A + B + C + D + E - F + G + H - U + I + O ...

 

A + B + C + D + E - (F + G + H ) - (U + I + O ... +Z)

 

위 처럼 -가 한 번이라도 등장한다면 뒤의 모든 수들을 -로 만들 수 있어서 이런식으로 뭔가 발상을 통해서 문제를 해결하는 방법이 그리디 알고리즘인가 싶더라

 

근데 정답은 아무도 모르는일 물론 난 다른 사람 소스를 안보기는 했는데 한 번 봐야겠다.