엠제이
20
2015-11-02 19:34:30
11
5396

대학교 프로그래밍 경시대회 기출문제가 너무 어렵습니다


컴퓨터공학과로 전과를 준비하는 국어교육과 학생입니다.

휴학하고 공부하고 있는데 학교에서 프로그래밍 대회가 열려 참가하게 되었습니다.

저번달에 최호성님이 쓴 C언어 책을 끝냈고 자료구조와 알고리즘은 이제 책을 보기 시작했습니다. 

문제를 보는데.. 뭘 모르는지 모르는 상태라서 이렇게 질문을 올립니다ㅜ.ㅜ

작년 기출 11문제 중에 8문제를 풀었고 남은 3문제가 전혀 감이 오지 않습니다.


작년에 23팀이 참가해서 E를 한 팀이, H를 두 팀이 풀었고 K는 아무 팀도 풀지 못했습니다.

현업에서 고군분투하시는 선배님들께서 문제를 보시면 감이 오실 것 같습니다. 코드를 직접 짜 달라는 것이 절대 아니고, 어떤 개념이나 알고리즘이 관련 있는지만 알려주셔도, 공부해야 할 방향만 알려주셔도 제게 큰 도움이 됩니다...

기출문제 pdf파일

0
  • 답변 11

  • 갓섭
    108
    2015-11-02 23:39:54

    개념이나 알고리즘이 아니라 의견 정도인데

    K번은 입력받은 수열과 정렬된 수열을 비교하면서 swap할 케이스에 따라 비용계산 후에

    최소비용을 구해보는건 어떨까 하네요... 

    하수라서 예쁜 방법은 안떠오르는군요 ㅠㅠ

  • 갓섭
    108
    2015-11-02 23:44:07

    H번은 백트래킹에 대해서 알아보시면 될거같습니다~

  • ma0c
    100
    2015-11-03 12:29:13

    제한시간 2초 제한시간 3초.. 정말루요...??;;

  • byeworld
    3k
    2015-11-03 12:30:34

    헐.. 시간이..

  • 엠제이
    20
    2015-11-03 13:32:27

    갓섭님 감사합니다~

    제한시간은 문제 푸는 시간이 아니라 컴파일해서 실행했을 때 올바른 결과가 출력될 때까지 걸린 시간이더라구요.

  • 안움직여도쏜다
    2k
    2015-11-03 14:03:48

    E는 문자열을 숫자로 대입하여 풀어도 될거같습니다

    H = 1, U = 2, Y = 3 으로 놓고

    입력된 길이가 5라고 하면 나오는 패턴의 조건을 같은 숫자는 연속하지 않도록 기본적인 셋팅을 해주고 숫자가 각 자리 마다 랜덤한 수가 놓아 지도록 합니다.

    그리고 그 조건에 추가로 각 자리를 a,b,c,d,e 라고 하면 cd가 들어오는 시점에 ab와 비교하여 같은 수 라면 d의 숫자를 다시 놓게 하는 겁니다. 

    예를 들어

    a b c d e

    1 2 1

    데이터가 이렇게 쓰여 졌고 d에 다른 숫자가 쓰여지는 시점에 ab = cd 이면 d를 다른 숫자를 놓도록 하면 됩니다.

    출력값의 사전적 의미 배열은 숫자로 대입된 데이터들을 내림차순으로 보여주면 되겠네요

  • 더미
    14k
    2015-11-03 18:41:29

    문제 푸는 시간인줄..-_-;

  • 제주감자
    22
    2015-11-04 09:56:56

    K번

    1. 정렬

    2. 정렬한 데이터와 문제의 데이터와 위치를 비교

    3. 위치가 같지 않은 데이터만 추출

    4. 3에서 나온 데이터중 이동 가능한 짝들의 비용을 계산

    5. 가장 적은 비용의 짝들을 이동

    6 정렬된 데이터를 제외해서 4~5반복

  • 제주감자
    22
    2015-11-04 09:57:48

    E 번은

    1. h, u, y 순으로 글자를 늘려 갑니다.

    2. 글자를 늘릴때 마다 규칙체크, 

    규칙체크 :

    1. 앞 문자와 새로 추가하는 문자가 같은지 체크(hh(x), hu(0))

    2. 문자 길이 / 2 번째 까지 이웃하는 문자가 있는지 체크

    ex) huhyh 일 경우 5/2 = 2 (hu - hy 비교, uh-yh 비교)

    3. h, u, y 코드 모두 1,2를 충족 하지 못하면 앞에 문자를 빼고 그 다음문자부터 1~2를 재귀

    ex) huhyhuh를 넣을 경우 huhyhuhy는 안되므로 앞 문자를 뺀 huhyhu 와 u부터 다시 1~2번을 재귀


    설명하는 재주가 좋지 않아서..

    E번은 자바스크립트로 소스 짜봤는데 돌아가네요

    필요하시면 말씀하세요

  • 엠제이
    20
    2015-11-09 14:27:41
    제주감자 님 조언 듣고 E번문제 푸는데 성공했습니다 ㅜㅜ. 고맙습니다
  • 엠제이
    20
    2015-11-10 15:08:34

    K번은 최소비용으로 계산해봤는데 답이 아니었습니다.


    4 1 2 5 3의 경우 각 단계 최소비용으로 정렬하면 다음과 같이 됩니다.

    1단계: 4 2 1 5 3 (비용3)

    2단계: 4 2 3 5 1 (비용4)

    3단계: 1 2 3 5 4 (비용5)

    4단계: 1 2 3 4 5 (비용9)

    총 비용은 21이 됩니다.

    그러나 2단계에서 3단계로 넘어갈 때 1과 4가 아니라 1과 5를 바꿔주면 당장 비용은 6이 들겠지만 총 비용은 낮아집니다.

    1단계: 4 2 1 5 3 (비용3)

    2단계: 4 2 3 5 1 (비용4)

    3단계: 4 2 3 1 5 (비용6)

    4단계: 1 2 3 4 5 (비용5)

    총 비용은 18이 됩니다.


    E번 문제처럼 재귀형식으로 풀어야하나봅니다 ㅜ.ㅜ

  • 로그인을 하시면 답변을 등록할 수 있습니다.