아주 간단한 풀이 스케치

저작권의 철퇴를 맞기 싫어서 프로그래머스에 기출문제가 업로드되기 전 까지는 문제 내용을 공유할 수도, 제가 제출한 코드를 공개할 수도 없습니다 ㅠ_ㅠ 그로 인해 아주 두루뭉술하게 작성하는 점 양해부탁드려요

 

Q1

알고리즘 분류 : STL map, 구현

예상 난이도 : S4

 

특이사항 X

 

Q2

알고리즘 분류 : 수학

예상 난이도 : S4

 

서술이 조금 더 매끄러웠으면 좋았을 것 같긴하다만 아무튼 특이사항 X

 

Q3

알고리즘 분류 : 배열, 구현

예상 난이도 : S4

 

특이사항 X

 

Q4

알고리즘 분류 : 그리디

예상 난이도 : S1-G4

 

정확성은 n발을 10곳에 나누어 배치하는 모든 경우를 따져서 챙길 수 있을 것 같고, 효율성은 라이언이 챙겨갈 점수를 선택하고 나면(ex : 10,8,3점만 챙기겠다) 라이언이 각 점수에 화살을 몇 발 맞춰야하는지가 정해짐. $2^{10}$개의 모든 조합을 확인하는 방식으로 통과 가능

 

Q5

알고리즘 분류 : 트리, 비트마스크, BFS/DFS

예상 난이도 : G5-G3

 

정확성은 백트래킹으로 챙길 수 있을 것 같고, 효율성은 비트마스킹을 통해 상태를 관리하고 방문 표시를 남고 방문한 상태에서 또 계산을 안하도록 하는 방식으로 $O(2^{17})$에 통과 가능

 

Q6

알고리즘 분류 : DP

예상 난이도 : G4-G2

 

BOJ 11660 응용 ㅠㅠ 11660번을 봐도 감이 안오시면 2d update query constant 라고 검색해보세요

 

Q7

알고리즘 분류 : 게임이론, 백트래킹

예상 난이도 : G2-P5

 

맨 처음에는 모든 상태를 다 저장한 후 BFS로 풀릴 줄 알았는데 상태의 수가 $O(2^{25} \cdot 5^4)$일 것으로 보여서 뭔가 이상하다 싶었음. 답의 최대값이 어떻게 될지 모르겠어서 시간복잡도를 가늠하지 못한 상태로 일단 해보자는 생각으로 그냥 가상의 minimax tree 그리면서 재귀적으로 풀어냈는데(게임 이론에 안익숙하면 BOJ 16571가 비슷하게 풀릴것 같으니 참고) 그냥 바로 통과됐음.

 

간단한 총평 : 작년에는 3번부터 난이도가 확 올라갔는데 올해의 경우 1, 2, 3번은 충분히 풀만한 난이도로 출제되었다. 작년에 비해 알고리즘 분류가 그렇게 다양하지는 않았는데 7번은 좀 생소한 유형의 문제였다. 맨날 한 자리 해먹던 투 포인터/이분탐색/최단경로 문제는 등장하지 않았다. 반면 비트마스킹은 뒷쪽 문제에서 여러번 필요했다.

 

응시자의 입장에서 6, 7번은 어려워서 버린다고 해도 1,2,3,4번과 5번의 부분점수는 챙길만했다고 생각한다. 만약 1, 2, 3번에서 오랜 시간이 소모되었거나 세 문제 중에서 풀어내지 못한 문제가 있다면 구현력을 더 올릴 필요가 있어보인다.

 

고생 많으셨습니다!

  Comments
  • ㅇㅇ
    알고리즘방 BKD가 바킹독 님인가요 ? ㄸㄸㄸ
  • jshine
    총평 잘 보고 갑니다 123번만 겨우 시간 맞춰 다풀엇는데 반성합니다 ㅠㅠ
  • zero2 vec
    앞으로 열심히해서 n년후 올솔브를 보여드리겠습니다.
  • 성깔있는말티즈
    1에서 말렸네요. 결국은 꾸역꾸역.. ㅠㅠ
  • 바킹독Fan
    바킹독님 감사합니다~
    항상 2문제에서 3문제만 풀었었는데 바킹독님 덕분에 많이 배운것 같아요
    이번에 작년이나 재작년에 비해 쉬웠다고는 하지만 그래도 성장한 것 같아 기분 좋습니다
    5문제 풀었습니다!!
    감사합니다~~
  • ㅇㅇㅇ
    안녕하세요, 바킹독님.
    저번 기출 해설도 그렇고 이번 총평도 잘 보았습니다. 감사합니다.

    혹시 질문을 몇 개 드려도 될까요?
    1. 5, 7번과 같은 문제의 경우, 특히 5번의 경우 문제 없이 잘
    풀 수 있으려면 알고리즘 분류에 해당하는 문제를 많이 접해봐야 하는건가요?
    5번의 경우 bfs로 해놓고 방문한 상태를 처리하는 방법을 생각하다가 비트마스킹이 떠오르지 않아
    시간만 잡아먹고 결국 못 풀었습니다..ㅠㅠ 이런 유형에 유독 약한 것 같은데 조언 부탁드립니다..

    2. 그리고 구현력을 높이기 위해서는 그저 꾸준히 문제를 접하는 방법밖에 없을까요?
    이 시험 전에 라인 코테도 같이 봤었는데 어떤 idea(특정 알고리즘이라기 보다 구현방식?에 가까운 것 같습니다)를 생각해 내서 그 아이디어를 코드로 구현하는 문제들이 있었던
    것 같습니다. (저도 두루뭉술하게 적어서 죄송합니다..) 이런 유형도 보통 구현/시뮬으로 분류할 수 있는지 궁금하고,
    아이디어를 생각하는데 시간이 많이 지체되는 편인데 이건 문제를 많이 접하는 방법밖에 없는지 궁금합니다.

    아무쪼록 감사드립니다!
    • 1
      5, 7 둘다 꽤 어려운 문제였다고 생각합니다. 7은 대놓고 생소한 유형의 문제였고 5는 사실 노드의 수를 보고 비트마스크를 떠올릴 수 있다면 좋았겠지만 그렇게 쉽지는 않았겠죠. 7은 솔직히 대비가 힘든 문제라고 생각하고, 5같은건 앞으로 n이 작으면 비트마스크를 생각해봐야겠다고 머릿속에 담아두는 방법밖엔 없어보이네요.

      2
      라인꺼는 제가 안쳐서 문제를 모르니 적어주신 상황이 어떤건지 감이 잘 안오네요. 그냥 일반적인 얘기를 해보면, 문제를 풀어내기 위한 핵심적인 관찰을 빠르게하기 위해서는 결국 좋은 문제를 많이 풀고 여러 아이디어를 습득해놓는 방법 말고는 딱히 왕도가 없어보입니다.
    • 답변 감사드립니다..

      계속 풀면서 아이디어를 담아두는 연습이 더 필요하겠네요 ㅠㅠ 라인꺼는 문제 적기가 조심스러워서 커뮤 같은 곳에 검색해봤는데 빡구현 문제들이었다고 표현하네요.. 카카오 1~3은 괜찮았는데 뭔가 아직 구현에서 난이도가 더 올라가면 제가 버거워하는 것 같아서.. 글에서도 언급하신 것처럼 구현력을 좀더 끌어올려야 할 것 같습니다.

      아무튼 감사합니다. 좋은 주말 보내시길 바랍니다!
댓글 쓰기