컴퓨터공부하기

DFS를 이용한 완전탐색을 수행하였다.

이때, 중간에 계산 한 값이 이전에 계산한 MAX보다 작거나 같은경우는 더이상 들어갈 필요가 없다.

곱해주는 값이 1보다 작은 수 이기 때문에, DFS를 수행할수록 작아질 수 밖에 없기 때문이다.

sum < max 로 하면 시간초과가 발생하고 

sum <= max로 해야 PASS할 수 있다.

아직 방문하지 않은 방이고, 

OPT[i][j] = 좌표 (i, j)에서 가질 수 있는 최대 값으로

이미 값을 가지고 있으면 해당 값을 바로 리턴하며, 아직 구하지 않은 겨우에는 4방향을 탐색하여 값을 계산한다.

OPT[i][j] = OPT[i+k][j+k] + 1;

주어진 문자의 역할대로 코드를 구현하면 된다.

여기서 주의할 점은, '?'는 무작위 방향이 되는데, 이것 때문에 문제가 발생한다.

나는 DFS를 통해 해당좌표가 일정 횟수 이상 들어가거나 DFS콜이 너무 많이 호출되면 불가능하다고 판단하고 빠져나오도록 했다.

계산기로 만들 수 있는 모든 숫자를 미리 계산해 놓으며, 각 숫자를 만드는데 버튼을 몇번 클린해야 하는지 계산해 놓는다.

계산하고자하는 X부터 나누기 시작하여, 필요한 버튼을 계산한다.

1일 때는 버튼 1이 가능한 상태인지만 체크하여 별도로 예외처리가 필요하다.

SWEA홈페이지 Solving Talk에 가면 홍준님이 올려주신 Shortest Path Faster Algorithm(SPFA) PDF 파일이 있다.(링크)

이 내용을 바탕으로 구했다.

SPFA는 평균적으로 O(E)의 수행복잡도를 보여주는 효과적인 알고리즘 이라고 한다.

DFS로 점원들의 키를 합치며, 가장 작은 값을 찾아낸다.

지렁이를 2개의 집합으로 나누어

각각의 집합에서의 벡터의 합을 구한 후 |V|를 계산한다.

원래는 제닉스 TESORO EXCALIBUR(?) 청축 모델을 사용했었다.

내가 사용하던 모델은 2015년에 구매했었는데, 지금은 단종돼고 v2가 새로 나온 것 같다.

첫 기계식 키보드였고, 아무것도 모르는데 급하게 사야해서 그냥 청축으로 구매했었는데.....

사고보니 엄청 시끄러워서 ㅋㅋㅋ 조금 후회했던 키보드다.

키 다빼고 2번쯤 청소했었는데, 여름이라 창문 열어놓고 생활하니 또 먼지가 수북하게 쌓였다.

문제는 작년쯤? 그러니까 한 3년 사용하고나니...... T버튼과 3버튼이 맛이 갔다.. 버튼을 눌러도 안눌릴때가 있거나 연속적으로 눌릴때가 많았다.

특히 코딩을 해야하는데 int를 치면 intttt이러니까 백스페이스를 자주 눌러줘야했다.

최근에는 Q 버튼조차 맛이 가서 결국 고민하다가 키보드를 구매하기로 마음 먹었다.

키보드 종류가 워낙 많지만 유명한 레오폴드 제품중에서 고르기로 맘먹었다. 

레오폴드 중에서는 오른쪽 숫자패드 없는 텐키리스 제품들도 많았지만 나는 오른쪽 숫자 있는게 좋아서 숫자 있는 제품으로 선택.

한글표시 있는 제품들은 전부 품절이라, 급한 나는 그냥 영문만 적힌 것으로 구매했다. 어차피 키보드 자판은 다 외웠으니 큰 상관 없었다.

조금만 더 여유가 있다면 리얼포스로 구매했을 텐데, 이건 나중에 취업하고 나서 구매하기로 하고.

레오폴드 FC900R PD 적축 무소음으로 선택. 구매했다.

이전에 쓰던게 청축이라 시끄러웠으니... 이번엔 조용한 것으로 선택했다.

가격은 네이버에서 검색한 온라인 최저가보다 레오폴드 홈페이지에서 구매하는게 더 싸다. 다른 블로그에서 후기 찾아보니 다른 인터넷 몰에서는 키캡리무버랑, 키캡 여분을 더 주는가보다. 난 필요없으니까 그냥 더 저렴한 공식 홈페이지에서 구매했다.

배송은 우체국 택배로 왔고, 역시 주문하고 하루 뒤면 받을 수 있어서 좋다 ㅎㅎ.

레오폴드 FC900R PD 구매 후 느낀점.

청축 쓰다가 적축 무소음 사용하니 신세계다. 키보드 누를 소리가 전혀 없는 것 처럼 느껴진다.

이제 밤늦게 게임코딩해도 된다.

제닉스 테소로는 키를 더 쎄게 눌러야 하는 느낌이 있었는데, 레오폴드 FC900R은 부드럽게 치면 된다.

이게 소리가 안나기 때문에 부드런운 건지 헷갈린다...

그리고 키 덮개도 있어서 먼지가 많이 쌓이는 내방 환경에서는 좋은 것 같다.

사실 24시간 중에 18시간은 컴터 사용하니;; 큰 효과는 없겠지만 없는것 보단 낫다고 생각한다.

키보드 구매하고 바로 SWEA 들어가서 한문제 풀어봤는데, 느낌 나쁘지 않다.

조금만 더 적응 하면 될 것 같다.

레오폴드 FC900R PD 만족한다! 이제 오래오래 리얼포스 살때까지 잘 써야징

평면 xy에 수많은 점들이 주어진다. 이때, 두 점을 이어서 직선을 만들 것인데, 이전에 그렸던 직선과 평행한 직선은 다시 그을 수 없다.

문제를 해결하기위해 먼저 각각의 좌표를 오름차순으로 정렬했다.

그리고 각각의 점들간의 모든 기울기를 계산하여 set에 저장했다.

알고 있듯이 set은 중복되는 값은 알아서 저장하지 않기 때문에, 중복되는 기울기는 제외하고 점들간에 계산된 기울기는 set에 모두 저장된다.

그러므로 set의 크기가 곧 상원이가 그린 직선의 최댓값이 된다.

많은 개수의 빵을 사기 위해서는 가장 싼 값의 빵을 최대한 많이 사면 된다.