[3일차] Greedy&Brute-Force

오늘은 뭔가 제목과 강의가 딱 맞는 느낌은 아니었다. 이전 강의들에 비해서 강의 영상의 러닝타임이 꽤 길었지만 딱히 맛있다는 느낌을 받지는 못 했다. 그 와중에 버퍼링이 하도 걸려서 아주 괴로운 시간이었다.

 

그나마 이전에 배웠던 정수형 변수를 부분 집합으로 보는 방법을 사용해서 조합을 표현하는 부분이 재밌었다. 정수형 변수의 비트 중의 1의 개수를 세면 내가 원하는 크기의 부분 집합을 구할 수 있다. 물론 매번 1을 세어야 하는 오버헤드가 존재하긴 하지만 이런 방법이 효율적인 경우도 있을 것 같다. 매번 재귀 함수로만 조합을 표현했었는데, 이렇게 만드는 방법도 있구나 싶었다.

 

그리고 한 3주쯤 전에 TSP 문제를 백준에서 풀었었는데 이제서야 그 문제에 대한 이해도가 좀 높아진 것 같다. 사실 그때 비트를 사용해서 이미 방문한 노드를 표현하는 것이 이해하기 어렵지 않아서 뭐 까짓거 나중에 혼자서도 구현할 수 있겠지 했었는데 그 이후로 비트마스킹하는 꼴을 보면 영 탐탁치 않았다..ㅋㅋ

 

SWEA에서 주어진 문제를 몇개 풀었어야 했는데 오늘 문제들은 되게 쉽게 슥슥 풀려서 기분이 좋았었다. 그런데 마지막 문제를 푸는데 자꾸 테스트 케이스 10개 중에 9개만 성공했다. 아예 다 안 됐으면 모르겠는데 1개만 안되니까 반례가 있겠거니 싶어서 한시간동안 열심히 찾았다. 그런데 결국엔 초기화 문제였다. 테스트 케이스가 많지 않아서 생긴 문제인 것 같다. 변수를 만들었으면 초기화를 해야지^^