알고리즘 문제 해결 전략4 2022.07.23 p151~200 보글문제 -완전 탐색 이용. 1. 문제의 분할 word 의 시작 위치 (y,x)와 인접한 여덟 칸을 모두 시도하며 답을 찾자. 2. 기저 사례의 선택 더 이상의 탐색 없이 간단히 답을 낼 수 있는 경우를 기저 사례로 선택하자. a. 위치(y,x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패 b. (1번 경우에 해당되지 않을 경우) 원하는 단어가 한 글자인 경우 항상 성공 이때 두 조건의 순서는 바뀌어선 안됌. c. 현재 위치가 보글 게임판을 벗어난 경우 d. 첫 글자가 일치하지 않는 경우 *간결한 코드 작성의 팁: 입력이 잘못되거나 범위에서 벗어난 경우도 기저 사례로 택해서 맨 처음에 처리하기 -> 함수 호출 시점에서 오류 검사할 필요 없어짐. 3. 구현 4. 시간 복잡도.. 2022. 7. 24. 2022.07.15 p101~150 지수 시간 알고리즘 다항 시간 알고리즘보다 시간 훨씬 더 많이 걸림. 모든 답을 한 번씩 다 확인하는 경우 전체 걸리는 시간은 만들 수 있는 답의 수에 비례함. 지수 함수는 알고리즘의 전체 수행 시간에 엄청난 영향을 미침. 아직 지수 시간보다 빠른 알고리즘을 찾아내지 못한 문제 아주 많음. 다항 시간과 지수 시간 사이의 경계는 전산학에서 효율적으로 해결할 수 잇는 문제와 없는 문제를 가르는 경계. 따라서 다항 시간 알고리즘이 있는 문제는 계산적으로 쉬운 문제, 없는 문제는 어려운 문제임. 소인수 부해의 수행 시간 소인수 분해 문제에서는 입력으로 주어지는 숫자가 알고리즘의 동작에 직접적인 영향을 미치므로 숫자가 특정 범위 안에 있다고 가정할 수 없음. 비트의 수가 하나 증가할 때마다 표현할.. 2022. 7. 16. 2022.07.13 p51~100 자주 하는 실수 1. 산술 오버플로 2. 배열 범위 밖 원소에 접근 3. 일관되지 않은 범위 표현 방식 사용하기 (반열린구간으로 통일하기 [a,b)) 4. Off by one 오류 (계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 오류) 5. 컴파일러가 잡아주지 못하는 상수 오타 6. 스택 오버플로 (재귀 호출의 깊이가 너무 깊어져서 옴. 대회에서 사용하는 환경의 스택 허용량 알아둘 필요 있음. C++의 경우 자동으로 힙에 메모리를 할당하는 STL 컨테이너 사용하거나 전역 변수 사용하기) 7. 다차원 배열 인덱스 순서 바꿔 쓰기 8. 잘못된 비교 함수 작성 -> 크기 비교, 사전순 비교만을 사용하더라도 충분한 문제에 복잡한 비교 함수를 작성하지 말자. +연산자의 성질(str.. 2022. 7. 15. 2022.07.11 p1~p50 지식을 진정 자신의 것으로 만들어 활용할 수 있기 위해서는 학문이 발전하는 과정에서 일어난 발견과 깨달음을 학생 자신이되짚어갈 수 있어야 한다. 프로그래밍 대회는 알고리즘들을 베껴 쓰기만 하면 해결할 수 있는 문제만 있는 것이 아니라 알고리즘에 사용된 원칙들을 이해하고 변형해야 풀 수 있는 문제들이 많이 출제되므로 이런 경험과 깨달음을 얻기 위한 좋은 통로임. 많은 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력은 분야를 막론하고 좋은 프로그래머가 되기 위한 필수 조건 프로그래머가 사용하는 언어나 라이브러리, 알고리즘에 대한 지식들 = 퍼즐 조각, 문제 해결 능력 = 적재적소에 퍼즐을 배치하고 이들을 연결해서 큰 그림을 만드는 능력 프로그래밍 대회는 다양한 알고리즘 설계 기법과 .. 2022. 7. 12. 이전 1 다음