알고리즘을 평가하는 두 가지 주요 기준은 시간과 공간이다. 이 두 요소는 서로 상충하는 경우가 많다. 메모리를 아끼려면 속도를 희생하고, 속도를 높이려면 메모리를 희생하는 식. 통상 더 중요시되는 기준은 시간이다. 프로그래밍 대회를 나가거나 알고리즘을 발명할게 아니라면 대부분 코딩 테스트를 보는 입장에서, 시간 제한을 지키는 것이 문제를 해결하는 것 다음으로 중요한 태스크다.시간 복잡도란?시간 복잡도(time complexity)란 가장 널리 사용되는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것입니다. 알고리즘의 속도를 비교하는 가장 직관적인 방법은 실제 실행시간 측정이다. 그러나, 이는 알고리즘의 속도를 일반적으로 논하는 ..
파인만 알고리즘. 칠판에 문제를 적는다. 골똘히 생각한다. 칠판에 답안을 적는다. 구종만 선생님께서 제시하신 문제해결과정. 문제를 읽고 이해하기백준 알고리즘을 풀면서 정말 많이 느낀 점이다. 입력과 출력 예시가 부족하다고 할 수도 있겠지만, 애초에 ‘문제’를 꼼꼼히 읽었다면 문제를 오해하는 일은 일어나지 않을 것이다.변수의 값, 시간 등 제약조건을 이해하기 위해선 알고리즘 시간복잡도, 공간복잡도 분석과 언어의 값 범위에 대한 이해가 선행되어야 한다.문제에서 나오는 개념이나, 지문에서 묻는 전반적인 요구조건과 제약조건을 일단 이해하자. 문제의 재정의와 추상화…자신이 다루기 쉬운 개념을 이용해서, 문제를 자신의 언어로 풀어 쓰는 것입니다. 이 과정은 문제가 요구하는 바를 직관적으로 이해하기 위해 꼭 필요합니..
추상 자료형? 학교에서 자료구조 & 알고리즘 수업을 들으면서 추상 자료형(Abstract Data Type, ADT)이라는 개념을 알게 됐다. 언어에서 제공하는 원시 타입(primary type)들로는 해결이 어려운 문제들이 있다. 그럴 땐 기존의 원시 데이터 타입을 응용해서 새로운 자료 구조를 만들어야 하는데, 자료 구조를 만드는 방법은 상황마다, 언어마다 다양하다. 추상 자료형은 어떤 자료형을 값과 연산들의 집합으로 정의한 것이다. 구체적인 언어나 명령어가 아닌 한 단계 추상적으로 구현 방법을 설명한다. 구현에 의존하지 않는다. 즉, 추상 자료형은 how(구체적인 구현 방법)가 아닌 what(집합과 연산들의 목록)을 추상적으로 명시해놓은 것이다. 음식 레시피와 같다. 내가 어떤 환경(어떤 프라이팬을 ..
