|
|
|
|
| |
|
| 글쓴이: 관리자 |
제목: 지역본선 문제 풀이(중등부) |
조회수: 3441 |
|
국제정보올림피아드(IOI) 출신 강사가 분석한 문제 풀이법입니다. 이번 시험에 응시한 학생들은 참고하시기 바랍니다.
1번은 그냥 for를 돌려도 되고, 유클리드 알고리즘을 사용해도 됩니다.
2번은 각각의 문자열을 정렬한 뒤 앞에서부터 하나씩 비교해 가는 방법과 각 문자열에서 A~Z까지 각각의 문자의 개수를 센 뒤 서로 비교하는 방법으로 풀 수 있습니다.
3번은 N이 100이어서 각 정점에서 BFS를 하여 쉽게 해결할 수 있습니다.
4번은 위상정렬 문제입니다. 1번 정점을 출발 정점과 도착 정점으로 분리하면 사이클이 없는 acycle graph가 되고, 이것을 위상정렬하여 순서를 정한 뒤 dynamic programming으로 최장 경로를 구하면 됩니다.
5번은 dynamic programming 문제입니다. KOI 문제와는 다른 문제이구요, 최소횟수 에디터와 비슷한 문제입니다. 단 부분 서열에서 최대 유사도 쌍을 찾는 것이기 때문에 테이블의 칸을 채울 때 한 문자씩으로 이루어진 쌍을 고려해 주어야 하고, 최대값을 찾을 때 마지막 값을 보는 것이 아니라 테이블 전체에서 최대값을 찾아 주어야 합니다.
특별히 어려운 문제는 없었던 것 같고 전반적으로 기본적인 실력을 테스트하는 문제였습니다.
어쩌면 다들 쉽게 느꼈을지 모르겠지만 실제 점수는 채점 결과를 받아 보아야 알 수 있을 것 같네요.
|
|
|
|
|
글쓴시간 : 2004-05-22 21:51:30 |
|
|
|
|
|
