[백준] 태상이의 훈련소 생활

유승선 ·2022년 6월 9일
0

백준

목록 보기
15/64

군대를 전역한지 얼마 안돼서 그런지 문제의 제목을 보고 풀까 하고 고민을 많이 했었다. 실제로 군대에 있었을때 다른 소대였지만 태상이라는 선임이 실존했고 그 사람의 군번도 5월쯤 됐었다. 이런 추억을 뒤로 한체 문제에 집중을 했다.

이 문제를 알게 된 계기는 GP에서 근무를 하던 당시에 2022 카카오 기출 코딩테스트 문제를 풀던 와중에 레벨3 문제 난이도를 보고 너무 어렵다고 느꼈는데 나중에 풀이와 후기들을 보니깐 백준 문제중 "태상이의 훈련소 생활" 문제와 유사했다고 얘기를 했던게 생각이 났다. 그렇지만 그때 당시만 해도 문제 푸는 플랫폼을 옮기는데 많이 거부감을 느꼈었던 상태였고 백준 문제를 한번도 풀어보지 않았기에 그냥 이런 문제가 있었구나만 알고있었다. 그리고 이제 백준에 어느정도 익숙해진 상태에서 이 문제가 생각나서 풀게 되었는데 알고보니 실버1의 난이도 였고 그렇게 어렵지 않겠지 하고 풀어봤는데 더 어려운 골드 문제보다 많이 배운 느낌이였다.

우선, 이 문제는 Prefix Sum 에 대한 경험이 부족하거나 개념을 잘 모른다면 솔직히 거의 풀 수 없는 문제다. 문제 내용은 N길이만큼의 배열과 M만큼의 명령어 (x,y,z) 가 있을때 x 와 y 사이의 구간을 z만큼 더했을때 마지막에 나오는 최종 배열값을 출력하면 됐었다. 가장 쉬운 방법을 생각했을때는 명령어를 전부 저장하고 명령어 순서대로 읽으면서 배열을 업데이트 해주는 방법도 존재했다. 그러나 제한된 입력 개수를 보면은 N과 M은 각각 십만이고 만약 명령어인 x,y,z 의 x,y가 항상 1부터 10만까지 주어지게되면은 쉬운 방법을 선택하는 순간 10만 곱하기 10만의 런타임이라는 경의로운 시간을 기록할것이란거를 노트에서 적으면서 느꼈다.

그렇기에 색다로운 알고리즘이 필요했는데 선택한 알고리즘은 Prefix_sum 이다. 솔직히 난 코딩테스트 문제를 풀면서 좀 편식같이 문제를 푸는 경향이 있었는데 Prefix_sum 은 내가 편식을 했던 문제 유형 중 하나라 개념을 잘 몰랐다. 그렇기에 유투브에서 강의를 좀 참고했고 그 결과 이렇게 많이 누적되는 덧셈을 구할때 쓰이는 알고리즘이라는 것을 알았다.

일단은 이게 답 코드지만 분명히 헷갈리는 부분이 꽤 있을거다. 일단 prefix_sum 에 기본은 index 를 1부터 시작해야한다는 점에 있다. 말 그대로 전에 있는 값을 계속 누적하면서 더해야 하는것이 포인트이기 때문에

이런 이미지를 생각하면 더 편할것이다. sum[i] += sum[i-1] 을 적은 이유도 누적합에 특징을 살리기 위해서다. 그렇지만 이 문제는 어떤 값의 누적합을 더해야 할것인가에 대한 생각이 필요했는데. 가장 먼저 주어지는 배열 값에 누적합은 일단 아니다. 그 값은 원본 그대로 둔채로 나중에 정답을 구할때 쓰이는 배열이기때문에 마지막까지 냅두지만 우리가 구해야하는 누적의 뜻은 M만큼의 명령어를 누적시켜야했던것이다.

가장먼저 초기화된 벡터 [0,0,0,0,0] 에서 명령어중 하나인 x, y, z 가 1, 3, +2 라고 가정해보자,
그렇게 되면 [0,2,0,0,-2] 라고 나는 지정해줄것이다. 이해가 안갈수있지만 이것은 누적합을 위한 빌드업이고 생각하다보면은 왜 이런 식의 계산을 했는지 알게되는데.. 저렇게 누적합 세팅을 해주고 실제로 합을 구하다보면은,
sum[i] = sum[i-1] + sum[i] 의 값을 실제로 진행해보겠다.
[0,2,2,2,0] 이 된다, 왜냐면은 1부터 3번째 인덱스까지 전에 값을 계속 더하다보면은 0+2..2+0...2+0...-2+2가 되기 때문이다

이런 방식으로 누적합을 M만큼 해주고 해당 값을 원본 index값에 더하면서 출력하면은 결국 원하는 값이 나올것이다. 정말로 신기했던 방식이라 생각했고 내가 prefix sum에 대해 얼마나 몰랐는지도 알게되었다.

그 외에 prefix_sum 에 대한 정보로는 구간합 구하기 링크도 참고했다.

배운점:
1. prefix_sum 에 활용
2. prefix_sum 에 대한 이해도

profile
성장하는 사람

1개의 댓글

comment-user-thumbnail
2023년 5월 8일

형님 태상이 4월입니다 ㅋㅋㅋㅋㅋㅋ 저도 이거 풀 때 그 생각 했어요

답글 달기