Hokusai

핀볼게임 (SWExpertAcademy문제)를 풀었을 때 테스트케이스 50개 중 49개만 맞고 런타임에러(Runtime Error)가 떴었다. 기존에 알고 있던 런타임에러가 나는 상황은 배열의 인덱스를 벗어난 경우(-1이나 길이 50개짜리 배열에 50이라는 값의 idx를 참조) 정도만 알고 있었는데 검색을 해보니 굉장히 많은 상황이 있었다. 배열에 할당된 크기를 넘어서 접근했을 때전역 배열의 크기가 메모리 제한을 초과할 때지역 배열의 크기가 스택 크기 제한을 넘어갈 때0으로 나눌 떄라이브러리에서 예외를 발생시켰을 때재귀 호출이 너무 깊어질 때이미 해제된 메모리를 또 참조할 때프로그램(main 함수)이 0이 아닌 수를 반환했을 때 참고하자.

기존에 2개이상의 수(int 등)을 포함하는 배열을 활용하면 참 좋겠다 했는데 Pair 클래스, 즉 2개이상의 숫자를 담을 수 있는 배열을 선언할 수 있다는 것을 이제알았다...!!!!!!!배열느낌으로 항상 queue, stack으로 넣어서 풀었는데 pop하면 없어져서 다시 push하는 귀찮음이 존재했는데 그냥 배열 자체가 있다는 걸 알아내고 열이받았다.... 여태까지 그렇게 풀었는데...활용법은 간단하다. 아래 코드를 보자 실행결과도 잘 나온다. 하 이제 알았으니 잘 써먹어봐야겠다.

프로그래밍 대회의 시간 제한은 알고리즘의 시간 복잡도가 아니라 프로그램의 수행 시간을 기준으로 합니다. 따라서 어떤 알고리즘이 이 문제를 해결할 수 있을지 알기 위해서는 프로그램을 작성하기 전에 입력의 최대 크기와 알고리즘의 시간 복잡도를 보고 수행 시간을 어림짐작할 수 있어야 합니다. 물론 프로그램의 수행 시간을 짐작하는 것은 엄청나게 어려운 일입니다. 프로그램의 동작 속도에 영향을 끼치는 요소는 입력의 크기와 시간 복잡도를 제외하고도 엄청나게 많기 때문입니다. CPU의 클록 속도, 1클록마다 수행할 수 있는 CPU 명령어의 수, 프로그램의 메모리 접근 패턴, 운영 체제와 컴파일러의 버전, ... 목록을 만들자면 끝이 없습니다.그러나 많은 경우에는 시간 복잡도와 입력 크기만 알고 있더라도 어떤 알고리즘..