adfsfsf   1년 전

본 문제에서 제시하는 알고리즘들은 다음과 같습니다.

- 수학

- 정수론

- 누적 합

- 소수 판정

- 에라토스테네스의 체

- 조화수

이들 중, 조화수는 본 문제와 전혀 관련이 없습니다.
조사를 해보니 '조화수'는 '에라토스테네스의 체'의 '시간 복잡도 검증'에 쓰입니다.
BOJ에도 이에 대한 '잘못 구현한 에라토스테네스의 체'라는 문제가 있기는 하지만 해당 내용이 본 문제에서 사용되지는 않습니다.

풀이에 혼란을 줄 수 있으니 조화수를 본 문제의 알고리즘 목록에서 지워주셨으면 합니다.

또한 '누적 합'에 대해서도 조금 의심스럽습니다.
누적 합 알고리즘은 N개의 수에 대해 '인덱스가 0인 값부터 인덱스가 i인 값까지의 합'인 N개의 합을 구하고, 이를 활용한 '구간 합'을 구하기 위한 알고리즘입니다.
이에 대해서는 '단계별로 풀어보기'에 있는 '누적 합' 알고리즘 문제들을 풀어보면 알 수 있는 사항입니다.
물론 문제에서의 g(N)이 일종의 누적 합이며, N의 값은 무작위 순서로 주어지기 때문에 큰 수가 먼저 나오고 작은 수가 나올 경우 큰 수에 대한 g(N)을 구할 때 알게 된 작은 수의 g(N)을 다시 구하는 것을 방지하려면 '누적 합'을 버리지 않아야 합니다.
하지만 본 문제에서는 '구간 합'을 필요로 하지는 않으므로 '누적 합'이 알고리즘으로서 사용되었는지에 대해서는 의문이 듭니다.
이에 대해서도 다시 검토가 필요하며, 저는 누적 합 또한 알고리즘 목록에서 지우는 것이 혼란을 방지할 수 있다고 생각합니다.

skuru   1년 전

첫째로, 조화수는 에라토스테네스의 체의 시간 복잡도를 증명하기 위해서도 맞지만 조화수 꼴의 연산 횟수를 갖는 알고리즘의 시간 복잡도 검증을 위해서 추가된 태그입니다. 이 문제에서 f(x)를 에라토스테네스의 체와 비슷하게 구하는 경우 연산 횟수가 조화수가 되므로 필요하다고 생각합니다.

둘째로, (1 ~ n)까지의 합도 구간 합입니다. 따라서 누적 합 태그가 필요하다고 생각합니다.

그리고 알고리즘 태그는 백준이 아니라 solved.ac 유저 기여에 따라 자동으로 부여됩니다. 알고리즘 태그나 티어 조정 관련 건의사항은 solved.ac 디스코드에 남겨주시면 좋을 것 같아요.

adfsfsf   1년 전

제가 디스코드를 들어가는 것은 좀 거부감이 들기도 하고, 여기서 알고리즘 분류에 대한 의견을 제기하는 게 문제가 되지는 않는 것으로 알아서 여기 적었습니다.

또한 알고리즘 태그는 '문제를 풀기 위해 사용하는 알고리즘'들을 적어야 하는 것이지, '문제와 관련된 모든 개념'들을 적는 곳은 아니라고 생각했습니다.

'조화수'의 경우 '알고리즘의 검토'를 위해 사용하는 개념이기는 하지만 '문제 풀이를 위한 알고리즘'이라고 보기에는 무리가 있다고 생각합니다.
문제의 풀이 코드에서 '조화수'의 개념을 사용하지 않는다는 점에서 '알고리즘 태그'에 넣기에는 맞지 않다고 생각됩니다.
그리고 다른 '조화수의 시간 복잡도를 갖는 답을 요구하는 문제들'에서도 사용된다고 하셨는데, 문제 풀이에 쓰이지 않으면 그 문제들에서도 다 빼야 맞지 않나 생각됩니다.

(1~n)까지의 합은 1부터 n까지의 누적 합이니 구간 합이라고 볼 수 있기는 합니다.
하지만 '누적 합'이 알고리즘으로서 쓰이는 것은 '시작점부터의 누적 합'을 단순히 저장하는 것이 아닌 '중간의 연속되는 구간의 합'을 쉽게 구하기 위한 것이라고 이해했고, '단계별로 풀어보기'에서도 그것을 의도했습니다.
그러니 단순히 '(1~n) 합'을 구하고 관리하는 것은 알고리즘으로서 작용하는 것이 아닌, '메모이제이션' 기법을 적용한 것 뿐이라고 봐야 한다고 생각했습니다.

skuru   1년 전

저는 태그가 문제와 관련된 모든 개념을 적는 곳이라고 생각했습니다. 왜냐하면 애드 혹, 해 구성하기, 구현 등의 알고리즘이 아닌 태그가 있기 때문입니다.

에라토스테네스의 체를 기여하게 되면 소수 판정이 항상 같이 기여되도록 설정되어 있습니다. 조화수는 solved.ac 디스코드에서 어떤 분이 건의하여 에라토스테네스의 체 아이디어만 이용하고 소수 판정과는 관계없는 문제에 사용하기 위해 만들어진 태그입니다. 해당 태그가 추가되기 전 문제가 소수 판정과 관련이 없는데도 불구하고 솔브드 유저들 다수가 "에라토스테네스의 체"를 기여했고, 이를 미루어 보아 대부분 유저들이 조화수의 개념을 사용해서 풀이했다고 할 수 있겠습니다. 시간 복잡도를 계산하는 것도 문제 풀이의 일부입니다. 그래서 조화수 태그가 필요하다고 생각합니다. 엄밀히 말하면 제 생각은 아니고, solved.ac 유저분들 생각입니다.

그리고 사실 꼭 구간 합을 구해야만 누적 합 태그가 붙는 것은 아닙니다. 예를 들어 Banks문제가 여기에 해당하겠습니다. 이 문제는 구간 합을 구하는 것이 아니라 누적 합만을 이용합니다.

adfsfsf   1년 전

애드 혹, 해 구성하기, 구현 등이 알고리즘이 아닌 것처럼 보이셨다는 게 오히려 신기하네요.
해당하는 개념들이 있는 문제들을 몇몇 풀어보았는데 제가 기억하고 있는 한, 그 문제들은 해당 개념들을 알고리즘으로서 사용했습니다.

이 문제의 경우 '약수의 합'을 계산하는 과정에서 '소수 판정'이 필수적이라고 생각했습니다.
임의의 자연수에 대해 '약수의 합'을 구하려면 1을 제외하고는 '소수', '소수의 제곱수', '합성수'의 3종류로 나누고, 각 분류에 따른 규칙을 활용해야 되기 때문입니다.
만약 적어주신 것이 다른 문제에 대해 그런 일이 있었다는 뜻이라면, 그 문제가 무엇인지 궁금하네요.

제시해주신 Banks 문제는 'Magic Move'를 은행 Ki에 사용하면 Ki-1과 Ki+1의 값이 바뀐다는 점에서 3개의 칸에 대한 구간 합을 사용할 수 있다고 생각합니다.

skuru   1년 전

이것은 이 문제의 제 풀이 코드인데요, 정수 i에 대한 i의 배수들의 f(x)값에 i를 더해주는 방식으로 구현했습니다. 이렇게 하면 에라토스테네스의 체와 같은 방식으로 구현할 수 있고, 소수 판별의 개념 없이 풀 수 있습니다. 대다수의 사람들이 이렇게 풀어서 조화수 기여를 하게 된 것 같아요.

Banks문제는 제가 풀이를 조금 찾아보았는데, 잘못된 예시였던 것 같습니다. 잊어주세요..

adfsfsf   1년 전

저는 '약수의 합'을 구하는 게 중심이라 생각해서 소수 판정이 필수라고 생각했습니다.
'약수를 구하기 위한 방법'으로 잘 알려진 방법이 '소인수분해'를 통한 '약수 판별'이니까요.

그런 방법이 있었다는 게 신기하네요.
에라토스테네스의 체 형식에 사용되는 루프의 횟수는 훨씬 많지만 연산의 수가 더 적어져서 결과적으로는 더 짧아지는군요.

그래도 '누적 합'에 대한 것은 좀 더 검토가 필요한 게 맞는 것 같네요.
작성하셨던 코드를 봐도 '메모이제이션'을 사용한 것이지 '누적 합'을 사용한 것은 아니니까요.

skuru   1년 전

누적 합은 조금 애매하다고는 생각하는데, 개인적으로는 그대로 두어야 한다고 생각합니다. 누적 합은 구간 합을 구할 때 뿐만 아니라 그냥 누적 합을 만들기만 해도 누적 합이라 부르더라고요. 예를 들어 계수 정렬을 할 때 어떤 수 보다 작은 수의 개수를 모두 세기 위해서 누적 합을 사용합니다.

adfsfsf   1년 전

앞서 처음 글에서 제가 적었듯, 누적 합과 누적 합 알고리즘은 다릅니다. 적어주신 예시는 누적 합을 쓰긴 했지만 누적 합 알고리즘을 쓴 것은 아닙니다.

skuru   1년 전

저는 아래 질문에 대한 답변이 불가능하기 때문에 일종의 사람들의 투표인 기여를 그대로 두어야 한다고 생각하는 입장이에요.

누적 합의 정의는 무엇이고 누적 합 알고리즘의 정의는 무엇인가요? 그 정의는 누가 정했나요? 솔브드 태그 기여는 어느 출처의 정의를 따라야 한다고 명시되어 있나요?

zenith82114   1년 전

solved.ac 기준으로 "누적 합"에 대응되어 있는 영어 명칭은 "prefix sum"으로, S[i] += S[i - 1] 꼴의 O(n) 루프를 돌려 전처리하는 행위 자체를 의미합니다. a <= i <= b에 대한 S[a] + ... + S[b]를 빠르게 얻는 것 이외에도 누적합의 사용처는 많습니다(일례로, DP 점화식에서 a_n = S_n - S_n-1으로 치환하여 잘 알려진 최적화 형태를 이끌어내는 유형들이 존재합니다). 이 문제의 경우 누적합 계산 이후 다음 스텝이 딱히 보이지 않아 어색할 수는 있으나 누적합이 붙는 건 말도 안 된다고 말할 상황이냐 하면 그것도 아닌 것 같습니다.

모든 걸 떠나서, 문제마다 붙는 알고리즘 태그는 중앙집권적으로 부여되는 것이 아닌 solved.ac 사용자들의 투표에 의해 정해지며, 그 알고리즘을 제시한 투표가 일정 비율 이상 되어야 실제 등록이 되고 문제 페이지에 노출되는 것으로 알고 있습니다. 그분들을 한 분 한 분 찾아다니시면서 설득하실 계획이 아니시라면, 그 정도 되는 인원수가 제시한 이유가 뭘지 더 고민해보시거나 의견의 다양성을 존중해주시는 것이 옳다고 봅니다.

leeingyun96   1년 전

제가 님의 의견이 틀렸다고 생각하는 것과는 별개로, 이런 말은 좀 그렇습니다만 윗분 말처럼 정말 적극적으로 무언가를 할 생각이 아니시라면 신경을 덜 쓰는 게 본인에게 편하실 겁니다. https://www.acmicpc.net/proble... 저는 이 문제가 항상 마음에 걸리고 골드 5는커녕 실버 5라고 생각하는데요 그렇다고 뭘 적극적으로 할 생각은 없어서 가슴 속에 묻어두고 있습니다. 가끔 이렇게 솔브닥으로 화두가 떠오르면 말할 뿐. 모두가 소극적인 마음이라면 결국 솔브닥의 정확도는 떨어지겠지만 어쩔 수 없는 일이죠.

동일한 논리로 많은 사람들이 나무위키를 X무위키, 나무위키 꺼라 이러면서 비하하지만 그곳의 틀린 내용들을 딱히 고칠 생각은 없어보입니다. 어찌 보면 그 사람들이 현명한 거죠

adfsfsf   1년 전

태그 임의변경은 어렵지만 최소한 '메모' 정도는 임의 추가가 가능한 것으로 압니다. 이 문제 말고도 불분명하게 '누적 합' 태그가 붙은 게 적지 않은 것 같은데, 공통적인 메모라도 적어주신다거나 해주시면 그것으로도 충분히 진입장벽을 낮출 수 있을 것 같습니다.

adfsfsf   1년 전

'누적 합'이 '단계별로 풀어보기'의 '누적 합 알고리즘'이 아닌 '누적 합의 계산'을 사용한 경우에도 추가된다는 의미의 메모면 충분하다고 생각합니다.

혹은 '누적 합의 계산'을 사용하는 문제라는 의미에서 추가된 문제라고 적어주든가요.

adfsfsf   1년 전

이 문제와 같은 경우는 문제 외부 요소에 대한 해설을 해야만 하는 상황입니다. 그러지 않고는 '알고리즘으로 쓰이지 않은' 누적 합이 알고리즘 목록에 있다는 것을 납득시킬 방법이 없습니다.

adfsfsf   1년 전

@zenith82114 님, 어떤 의도에서 적으신 건지는 알겠지만 solved.ac의 투표만 가지고 '다양성'을 언급하시는 건 오만이라고 말씀드리고 싶네요.

BOJ를 사용하는 대부분의 일반 사용자는 '문제 풀이'에만 관심이 있고, '알고리즘 분류'를 '답안을 작성하기 위해 사용할 알고리즘'으로 봅니다. 그리고 이런 유저들 대부분은 solved.ac를 단순히 '기록 확인 사이트'로만 알지, 거기서 출제자들 간의 교류나 알고리즘 분류 투표가 있다는 것에 대해서는 관심이 아예 없습니다. 오히려 그런 출제자들이나 투표 참여자들은 전체 사용자에 비하면 극소수나 다름 없습니다.

'알고리즘 분류'에 대한 투표가 일반 사용자들의 입장에서 납득이 가도록 이뤄졌어야 하는 것이지, 일반 사용자가 무조건 납득하고 넘어가야하는 암묵적 규칙이 아닙니다. 의견을 안 낸다고 모두가 동의하는 것도 아닙니다. 오히려 이렇게 의견을 내는 사람의 입장도 제대로 듣고 이해하려고 해주시는 게 다양성을 존중하시는 겁니다.

zenith82114   1년 전

민주정부는 투표장에 안 간 국민도 국민이니까 챙겨야겠지만 그게 여기도 통할까요? 출제자 간 소통과 피드백이 있는지도 모르고 관심도 없고 참여도 안 하는 인구의 학습 수준과 의견까지 어떤 마법 같은 경로로 전달이 되어서 반영되기를 바라는 것이야말로 오만이 아닌가 싶습니다. 디스코드 초대 링크를 돈 받고 파나요? 게시판에 이런 글이 올라올 때마다 "극다수"를 대변하는 N장짜리 투표용지 묶음이라고 생각하고 형성된 여론에 지각변동을 일으켜야 하나요?

adfsfsf   1년 전

그런 의도가 아니라 의견을 아예 내지 말라는 듯이 적지 마시라는 뜻입니다. 당신이 적은 글은 오히려 '일반 사용자는 하층민답게 아무 이의도 제기하지말고 투표자들이 제시한대로 납득해라' 라는 거잖습니까. 일반 사용자라고 무시하지 마시고 최소한 읽어는 보고, 무시할 거면 무시하지 그렇게 싹을 뽑으려들지 말라는 겁니다.

gnzpstly2000   1년 전

10986번 나머지 합

혹시 선생님은 이 문제는 "N개의 수에 대해 '인덱스가 0인 값부터 인덱스가 i인 값까지의 합'인 N개의 합을 구하고, 이를 활용한 '구간 합'을 이용했다"고 생각하시나요?

맞추신 코드 보니까 제가 볼때는 prefix sum만으로 해결하셨던데 어떻게 생각하시는지 궁금합니다.

adfsfsf   1년 전

@gnzpstly2000님, 그 문제의 제 코드는 누적 합 알고리즘을 썼습니다.

14~15번 줄에 nums 배열에 '나머지'의 누적 합을 저장했습니다 - 이 부분은 '누적 합 값'을 저장한 것이죠.

이후, 19~20번 줄은 '구간 합의 나머지를 빠르게 계산'한 것입니다.

원래의 '누적 합' 알고리즘은 '두 누적 합의 차이'를 통해 '구간 합'을 구합니다. 그 문제에서는 원래라면 구간 합을 구한 후, 다시 '나머지'를 계산해야 됩니다. 하지만 문제 특성 상 그렇게 하기에는 시간 초과가 계속 발생했습니다. 이에 구간 합을 구하는 과정을 생략하고, 모듈러의 원리에 따라 '나머지가 같은 두 누적 합을 갖는 칸' 사이의 구간 합은 항상 나머지가 0임을 이용한 것 뿐입니다.

정리하자면

- 누적 합의 나머지들을 구한 뒤

- 누적 합 간의 차이에 대한 나머지가 0인 구간의 수를 구해야 하므로

- 누적 합의 값이 같은 것의 쌍을 구하는 것으로 구간 합을 구하는 과정을 축약했습니다.

gnzpstly2000   1년 전

그러면 

prefix sum을 저장하고구간 합을 구하고 나머지를 계산할려고 하니까, 시간초과가 발생하여

구간 합을 구하는 과정을 생략하고~ 부터 실제로 구간 합을 구하지는 않으셨고,

누적 합의 나머지가 같은 그룹에서 2가지를 고름으로써 이 둘을 뺴면 m으로 나누어 떨어지니까,  "누적 합의 값이 같은 것의 정수쌍의 개수"만을 구하셨는데

결국은 해결에 사용한 알고리즘 자체가 '어디에도 구간 합을 구하지는 않고 있는데' 그러면 선생님은 이것도 '누적 합' 알고리즘이라고 생각하시는건가요?

저는 이 '17425 약수의 합' i = 1부터 n까지에 대해서, i의 배수인 j = i,2i,3i,...는 i를 약수로 가지므로 j위치에 i를 더해주고, 이전 i-1에 구해놓은 약수들의 합을 i에 누적하는 방식으로


prefix sum과 조화수를 이용한 시간복잡도만으로 해결했는데

 

저도 구간 합을 구하지는 않고 있는데 이거는, '구간 합을 구하려는 의도 자체가 없으므로' 말씀하시는 '누적 합 알고리즘'은 안되는건가요?

adfsfsf   1년 전

'나머지가 같은 두 누적 합의 쌍'은 '나머지가 0이 되는 구간 합'과 동치이며, 그러한 '구간 합'을 구하려는 의도의 결과물입니다. 그러한 의도 없이 바로 '나머지가 같은 두 누적 합의 쌍'으로 접근하셨다면 문제를 이해하신 게 맞는지 의심됩니다.

어쨌든, 구간 합을 구하는 부분과 구간 합의 나머지를 구하는 부분을 합친 게 '같은 값의 쌍을 찾기'가 된 것이므로 그 부분이 구간 합을 구하는 코드이기도 한 것입니다. '어디에도 구간 합을 구하지는 않고 있는데'라고 적으신 것 자체가 잘못 이해하신 것입니다.

zenith82114   1년 전

@adfsfsf

생각을 좀 해보니, solved.ac을 이용하면서 알고리즘 태그가 유저 투표 기반이라는 사실을 모를 수 있다는 생각을 미처 못 하고 있었습니다. 유저 투표의 결과임을 인지하고도 특정 태그를 제거하자고 주장하시는 줄 알고 제 첫 댓글처럼 반응했던 것인데 이제 이해가 됩니다. 결과적으로 문전박대하는 듯한 어투가 된 점 사과드립니다. 당연히 원글부터 전부 읽고 남긴 댓글입니다.

adfsfsf   1년 전

이 글을 적은 17425번 문제, 약수의 합은 앞서도 여러 번 언급했듯 풀이 과정에서도, 결과에서도 '구간 합'을 아예 사용하지 않으므로 '누적 합'이 어울리지 않는다고 적었습니다.

wlaud   1년 전

이번 solved.ac 시즌에 태그 설명 페이지가 나온다는 것 같은데 누적 합 태그의 정의가 명확해졌으면 좋겠네요.

별개로 이 문제는 C언어에서 O(n^0.5) 소인수분해로도 풀린다는 것 같습니다...

gnzpstly2000   1년 전

논점을 흐리면서 제 의견에 비판만 하시니 이게 뭐라 말씀드려야 할지......

-----------------------------------------------------------------------------

말씀드리고 싶었던건 '알고리즘 분류'가 '답안을 작성하기 위해 사용할 알고리즘'들은 맞긴 한데 모든 알고리즘들은 사용하지 않습니다.

solve.ac에서 정한 누적합(prefix sum) 태그가 'prefix sum을 이용해서 구간합을 구하는걸 명시하는게 아닌것 같다'라고 말씀드리고 싶었습니다.

당장 제가 제시한 '나머지 합' 문제도 저는 구간합을 구하지 않고 prefix sum과 모듈로 연산을 응용해서 해결하고 있다라고 생각하고 있습니다(선생님은 이에 동의하고 있지 않으시지만)

또한 알고리즘 태그가 사용되는 모든 알고리즘을 명시하고 있는 것이 아닙니다. 사람마다 문제에 대한 솔루션이 다양하기 때문에, 각각이 사용했다고 생각하는 알고리즘 태그를 기여하고

이 중에서 많은 기여를 받은 태그가 표시됩니다. 

당장 이 문제에 누적합 태그에 기여하신분만 대충 세보니 50명 정도가 되고, 누적합을 기여하지 않으신 분들도 50명정도 되는것 같습니다.

아마 누적합에 기여하신 분들 모두가 저처럼 prefix sum을 활용하셨고 구간합은 구하지 않으셨다고 생각합니다.

그리고 이 분들이 모두 이 태그에 적절하다고 생각하고 있고, 이 태그가 적절하다고 생각하시는 분들 일부는 위 댓글에 반론들을 제기하였습니다.

적절하지 않다고 생각하시는 분 중에 '누적합을 통한 구간합 구하기'로 명확히 명시해야한다고 생각하시는 분도 계셨는데, 여기에도 저는 동의합니다.

왜냐하면 저도 마찬가지로, 누적 합 태그만 보면 prefix sum을 구하고 구간합을 구해야겠지?라고 먼저 생각하기 때문입니다.

이처럼 prefix sum을 응용하여 할 수 있는 것이 많은데 구간합을 구하는 알고리즘만을 누적합 알고리즘이라고 생각하시는 것 같아서 댓글 달고 싶었습니다.

이 문제에서 당장 필수라고 언급하신 소수 판정을 쓰지 않고 해결하는 알고리즘도 존재하고, 

에라토스테네스의 체를 활용하지 않고 해결하는 알고리즘도 존재하며, 조화수의 개념을 이용하여 알고리즘에 적용하는 다양한 솔루션이 존재하는데 

"사용하지 않으니까 지워달라"라고 배척하시는 것 같아서, 태그에 동의하는 사람의 입장으로서 말씀드리고 싶었습니다.

저는 "나는 A라는 알고리즘으로 해결했는데, B라는 알고리즘 태그가 달려있네? 그러면 난이도 기여하신 분들의 코멘트를 보고 B라는 알고리즘 태그에 기여하신 분의 코멘트를 읽어보고, 


코드를 살펴보며, 이렇게 해결했구나.. 라고 생각하는게 더 맞는것이 아닌가?라고 생각합니다. 

실제로 solve.ac를 연동해서 사용하고 계시기 때문에 "난이도 기여"의 코멘트들을 보실수 있잖아요?

거기까지 보고도 이해가 안된다면 게시판에 이 방식이 왜 누적합 알고리즘이에요?라고 질문하면 제대로 된 답변을 받을 수 있을 것 같은데, 

갑자기 무작정 이 개념을 사용하지 않았으니까 지워달라라고 하니 저의 생각을 말씀드렸습니다.

추가로 그래도 여전히 이해를 못하시겠다면 디코에 들어가는 것이 거부감 드니까 solved.ac 운영자님께 한번 메일로 직접 제안드려보는건 어떠실지 제안드려봅니다.

알고리즘 분류는 백준이랑 상관 없기도 하고 게시판에 남기기만 한다고 해서 보지 않으실 가능성이 있기 때문입니다.

실제로 '조화수'는 최근에 생긴 태그 같습니다. 이처럼 태그가 생기고 수정되기도 해서 '누적합을 통한 구간합 계산'이라는 명확한 태그로 수정될 가능성도 충분히 있습니다.

adfsfsf   1년 전

일단 저는 '모든 알고리즘을 한 번에 사용'해야 한다고 적지 않았습니다. 당연히 풀이에 따라 일부 알고리즘만 쓸 수 있고, 그래서 알고리즘 분류가 둘 이상 있을 때 그 두 가지 알고리즘으로 서로 다른 코드가 가능하다는 것도 인지하고 있었습니다.

하지만 아무리 검색해봐도 '조화수'나 '누적 합 알고리즘'이 이 문제에 적용 가능하다는 근거를 찾을 수 없었기에 이런 글을 작성하게 된 것입니다.

'누적 합'에 대해서도, 계속 동일하게 적고 있지만, 단순히 '구간 합을 적용하는 문제가 아니라서' 이의를 제기한 게 아니고, '누적 합'과 '누적 합 알고리즘' 간에는 확실한 차이가 있고 및 항목 명이 '알고리즘 분류'이기 때문에 '누적 합'이라고 되어 있으면 '누적 합 알고리즘'을 지칭한다고 볼 수밖에 없습니다. 그렇지 않다고 한다면 '단계별로 풀어보기'에 단순히 '누적 합'을 쓰기만 하는 문제들을 넣어줬어야 한다는 의미이고요.

저는 제 풀이 경험 하나만으로 여기의 글을 쓴 게 아닙니다. 제가 처음부터 제시한 '근거들'을 제대로 보시지도 않고 '자기 생각만 주장하는 꼴통'으로 몰아가시는 것 같아서 불쾌하네요.

게다가 '백준'과 관계 없다고 하셨는데, 저는 solved.ac가 생기기 전부터 백준을 써왔고, 당시에도 알고리즘 분류 항목이 있었기에 그것에 대한 역할이 이관되었다는 것을 어제 다른 분들의 글로 처음 알았습니다. 그래서 처음에 임의 변경이 가능하다고 생각해서 그렇게 글을 적었던 것이고요.

그렇게 오래 썼으면서도 모르냐고 하신다면, 제가 '주사위 좌표 사건' 때문에 4년 정도 안 쓰다가 복귀해서 그렇습니다.그 문제도 '문제에서 X축 값을 먼저 쓰든, Y축 값을 먼저 쓰든 출제자 마음인데 왜 지적하냐'는 의견에 묵살당했습니다. 그것은 '문제에서는 알 수 없는 정보'인데 '정답을 위해서는 필요한 정보'였습니다. 예제에서조차 항상 입력이 '대각선으로 대칭'이어서 자신이 평소 풀던 문제의 종류에 따라 틀리는 이유를 전혀 알 수 없었습니다. 해당 문제의 경우, 이에 대한 불만이 적지 않았습니다.

이 문제의 '누적 합' 태그는 불만을 적은 사람이 보이지는 않았지만 마찬가지의 문제입니다. 정답을 위해서는 '누적 합 알고리즘'이 안 쓰였고 '누적 합'이라는 개념만 쓰였다는 정보가 필요합니다. 하지만 문제만 보고는 '누적 합 알고리즘'을 쓴 것으로 오해할 수 있습니다. '단계별로 풀어보기'로 '누적 합' 태그를 배우고 그 태그의 문제들을 풀던 사람들이 첫 페이지의 절반도 못 가서 이 문제를 만나는데, 그 모든 사람들이 바로 '누적 합 알고리즘을 안 써도 누적 합 태그가 달릴 수 있구나' 하고 납득하는 게 정상이라는 생각이야말로 개인의 지레짐작입니다.

이 문제 제기를 다시 '개인의 비난', '혼자만의 의견' 같은 것으로 치부하지 마십시오. 그런 태도를 계속 취한다면 결국 여기도 스택오버플로우처럼 정체될 뿐입니다. 솔직히 코딩 테스트 준비도 이제 AI로 대체 가능한 수준입니다. 저는 그저 BOJ가 계속 있고, 더 많은 초보자, 신참자 등이 '문제 풀이에 대한 진입 장벽'없이 과감히 도전할 수 있었으면 해서 적었을 뿐입니다.

adfsfsf   1년 전

다시 보니까 제가 그 후에도 중간중간 오긴 했었네요. 하지만 '문제를 푸는 것'에만 신경써서 다른 공지 같은 걸 못 봇긴 했습니다.

'주사위 좌표 사건'은 링크의 글에서 확인 가능하십니다.

주사위가 놓이는 방향이 제대로 되어 있지 않았던 문제였네요.

그래서 주사위를 어느 방향으로 놓는지에 따라 답이 달라졌었는데 이에 대해 X축과 Y축의 순서에 따라 해석이 달라짐을 알렸으나 결과적으로 '어차피 이 글을 썼으니 다들 이 글 보고 알아서 할 겁니다' 하면서 문제는 그냥 두는 것으로 넘어가버렸습니다.

저는 '문제의 설명 부족'으로 인해 틀리는 것까지도 '게시글에서 그 원인을 찾아야 한다'는 것은 불합리하다고 생각합니다. 문제가 잘못 된 것은 문제에서 설명을 해줘야 하는 것이지, 게시글에서 '사실 이 문제에는 어떠한 오류가 있으니 참고하세요' 하는 글을 직접 찾아야 한다는 것은 너무 무책임합니다. 특히, 링크의 글에 대한 문제의 경우 당시에도 그렇고 게시글이 적지 않습니다. 게시글이 적지 않은 문제들은 오류를 설명하는 글이 있더라도 찾기 힘듭니다.

skuru   1년 전

사실 알고리즘 태그는 원래부터 좀 애매한 부분이 있다고 생각합니다. 특히 언어의 특성 때문에 더 그렇다고 생각합니다. 예를 들자면 다항식의 곱셈을 구현하는 문제에 대다수의 사람들이 DP 태그를 기여했습니다. 어디까지가 DP인지 정의하기가 좀 어렵습니다. 점화식만 쓰면 다 DP일까요? 애초에 내가 말하는 DP와 다른 사람이 말하는 DP가 같은 DP긴 할까요?

아마 다른 분들은 adfsfsf님이 태그가 투표에 의해 붙는다는 것을 아는 상태에서 "다른 사람들이 생각하는 누적 합은 모두 틀렸다"라고 말하는 것으로 오해해서 그런 반응을 하게 된 것 아닐까 싶습니다.

그래서 제가 했던 말은 "다른 사람들이 생각하는 누적 합을 틀렸다고 하긴 어렵다"는 뜻이었는데, "네 생각이 틀렸다"라는 뜻으로 오해하셨을 수 있다는 생각이 드네요.

이제 알고리즘 태그가 solved.ac에 의해 붙는다는 것을 아셨으니까, solved.ac 디스코드를 통해 건의하는 방식이나 윗분이 말씀하신 대로 이메일로 건의하는 것이 어떨까 싶습니다.

zenith82114   1년 전

다른 건 다 이해가 됐는데 궁금한 점이 하나 있습니다. solved.ac 이전에는 백준에서 알고리즘 분류, 단계별 등의 기능들이 이런이런 역할을 하면 좋겠다, 어떠어떻게 관리하자는 내용이 명문화되어 있었거나 사용자들이 공유하던 이상적인 모습이 있었나요? 아니면 당시 또는 현재의 "소극적"인 (투표 및 토론에 참여하지 않는) 사용자들을 많이 만나보셨거나 그들의 백준 사용 경험에 대해 설문이나 통계 자료가 있나요? "제 풀이 경험 하나만으로 여기의 글을 쓴 게 아니다" "혼자만의 의견으로 치부하지 마라"고 얘기하셔서 질문드립니다.

adfsfsf   1년 전

마지막으로 한 번만 다시 적겠습니다.

현재 BOJ에는 '사이트에서 제시하는 누적 합 태그의 의미'은 '단계별로 풀어보기'에서 제시한 '누적 합 알고리즘'이라고 보게끔 설계되어 있습니다.

'단계별로 풀어보기'는 BOJ에서 알고리즘 태그에 대해 제시하는 가이드라인의 역할을 하므로 이 의미와 다르다면 오해할 수밖에 없습니다. 이것이 제가 '혼자만의 의견'이 아니라고 한 것입니다. 사이트에서 제시한 가이드라인이니까요.

그러한 문제점을 해결해야지, 여러분들께서 여기에 적으신 것처럼 '많은 사람들이 다른 의미로도 쓰니 받아들여라' 하시는 건 납득이 불가능합니다.

또한, 주사위 문제의 경우 '주사위의 방향'에 대한 건 당시에는 언급되지 않았습니다. 윗면이 1이라고만 나와있었는데 그 때의 토론 이후인지, 훨씬 이후인지는 몰라도 나중에 추가된 것입니다. 그 방향이 없어서 XY 논쟁이 있던 것입니다.

skuru   1년 전

아하, 그럼 결국 단계별로 풀어보기에서 제시하는 누적 합과 여기 문제에서 쓰이는 누적 합의 의미가 다른 것 같으니 둘 중 하나에 문제가 있다는 말씀이시군요. 무슨 말씀이신지 이해가 갑니다.

adfsfsf   1년 전

제가 뭔가 기억에 오류가 있나보네요. 그 부분은 제가 잘못 생각한 게 맞는 듯합니다. 하지만 관련 논쟁을 했던 것도, 논점만 제가 잘못 기억한 것이지 좌표와 과련된 문제가 있던 것도 모두 사실입니다. 이제 이 글에서는 더 이상 다른 댓글을 적지는 않겠습니다.

zenith82114   1년 전

사이트가 제공하는 컨텐츠를 모든 사용자가 똑같은 의미부여를 하고 똑같은 목적으로 사용하라는 법은 없으니 "~하게끔 설계되어 있다" "~ 가이드라인이다" 형식의 주장은 설득력이 낮습니다. 이 점 때문에 설문이나 통계를 가지고 계신지 여쭤본 것이고요. 연장선상에서, "지우는 것이 혼란을 방지할 수 있다고 생각합니다" 같은 부분들은 해당 태그의 의미가 혼란스럽다고 느낀 사용자가 본인 외에도 상당수 있음을 전제하는 것처럼 읽힐 수 있습니다. 사용자 경험에 끼치는 피해를 주 근거로 삼고 계시니 읽는 입장에서 자연스럽게 그 규모가 궁금해지지요. 개인의 의견임이 첫 글에 더 잘 드러났다면 저는 이 글에 아무 이슈가 없었을 것 같습니다.

adfsfsf   1년 전

진짜 마지막으로 한 번만 더 적습니다.

사이트가 '누적 합'에 대해 서로 다른 두 의미를 혼용하고 있다는 건 모두 동의하신 것으로 이해하였습니다.
즉, 사이트가 '누적 합'의 정의에 대해 하나로 통일하지 않았으니 이에 대한 처리가 필요하다는 원래 주장은 '몇 명의 의견을 대표한 의견인가'와 아무런 관계가 없습니다.
사이트 자체에 대한 문제이므로 사용자 경험에 피해를 끼칠 수 있다는 것도 당연한 결론입니다.

저는 사이트에서 특정 개념에 대해 서로 다른 두 의미를 쓰고 있다는 '사실' 때문에 생길 수 있는 문제를 방지하자는 주장을 한 것 뿐입니다.
자꾸 '다른 통계가 있냐', '다른 사람들의 의견을 듣고 적는거냐' 같은 얘기를 하시는데, 그것과 관계 없이 논리적으로 문제 없는 주장입니다.
자꾸 권위/사람 수만을 요구하는 오류를 범하지 말아주세요.
앞서서의 '투표자들의 의견을 무시한다'라는 발언이 잘못 되었음을 인정하신 분답지 않습니다.

skuru   1년 전

저는 “그렇게 생각할 수 있다”고 생각합니다. 저는 살면서 누적 합 알고리즘과 누적 합을 구분하는 사람을 본 적 없습니다. 저는 이 사이트에서 두 서로 다른 두 의미를 사용하고 있다고 생각하지 않습니다. 작성자분이 다른 의미로 받아들이고 있다고 생각하고 있고, 그럴 수 있다고는 생각하는데 다른 사람들도 그런지는 잘 모르겠습니다.

zenith82114   1년 전

동의하는 사람이 얼마나 많은지는 논리적으로 옳고 그름과는 무관할지라도 그 중대성 혹은 우선순위에는 현실적으로 영향을 주게 됩니다. 이 사안이 가지는 임팩트를 제가 모르는 다른 경로를 통해 인지하신 바가 있는지가 궁금했을 뿐입니다. 특정 포인트에 불만을 느끼는 사용자가 수십만 중에서 한 명이면 서비스 제공자 입장에서 뭔가 행동에 착수할 생각이 안 들 테니까요.

딱히 없으시면 제 댓글도 이걸로 끝입니다.

adfsfsf   1년 전

이의 제기 / 요청을 작성하는 것에 사이트 관리자의 중요성이 왜 고려 대상인지 모르겠습니다. 그것은 관리자가 '처리 여부'를 판단하기 위한 기준일 뿐입니다. 작성자는 작성자의 입장에서 중요하다고 생각하면 자유롭게 적을 권리가 있습니다.
자꾸 이의 작성자에게 관리자/답변자의 입장을 강요하시지 마시고 '그 이의 내용의 것은 왜 그렇게 사용되고 있는가', '해결책은 뭐가 있는가'를 함께 고민해주시는 게 맞습니다.

그리고, 사이트에서 서로 다른 의미로 쓰고 있다는 근거입니다.
https://book.acmicpc.net/algor...
하위 항목으로 '누적 합'이 있고 그 누적 합은 앞서 다른 분들께서 적으신 '시작 지점부터 해당 지점까지의 누적된 합'의 의미지만 '알고리즘 분류로서의 누적 합'은 해당 페이지에서 설명하는 개념 전체인 '구간 합을 빠르게 구하기 위한 방법'입니다.

zenith82114   1년 전

의견 작성하지 마시라고 한 적 없습니다. 의견의 타당성은 저도 이제 동의를 하는 상태이며, 그 다음 스텝으로서 "중요도"가 궁금했던 것입니다. "있다", "없다"만 들었으면 만족했는데, 이번 댓글에도 그런 정보는 들어있지 않군요. 대답은 "없다"로 알고 물러나겠습니다.

adfsfsf   1년 전

저는 스텝 여부를 몰랐기 때문에 작성하지 말라는 글로밖에 보이지 않았습니다. 그저 '중요치 않은 글인데 왜 썼냐'고 질책하는 것으로 보였습니다.

저는 누가 스텝인지 같은 것도 전혀 모릅니다. 그저 문제를 풀고, 불합리하다 싶은 것들이 보일 때마다 적는 사람입니다. 그런데 '개인의 의견 여부' 같은 '권위/통계'의 존재 여부를 물어보고는 '별 거 아닌 글이었네'라는 뉘앙스로 적으시니 그렇게 적었습니다.

당신이 스텝이시라는 것을 모든 사람이 금방 인지할 수 있다는 생각도 위험하다고 생각합니다. 보아하니 닉네임 색이 다르면 스텝이셨던 건가 본데 저는 지금껏 그저 문제를 많이 푼 고인물 정도로만 생각했었거든요. 앞서 제가 적었듯 '이 글 및 하위 댓글들을 통해서야 solved.ac에 알고리즘 목록 투표 등의 기능들이 있다'는 것을 알았던 것처럼, 문제 풀이에만 관심 있다면 모를 수 있는 사항입니다.

어쨌든, 이후에도 저는 문제에서 불합리함을 느끼면 글을 작성하긴 할 겁니다. 물론 이번에 알게 되었듯 대부분의 경우 임의 수정이 어렵다고 하신만큼 요청/요구가 아닌 자유 글로 쓰겠지만요.

adfsfsf   1년 전

색의 의미는 그런 거였군요.

그러고보니 중요도가 있냐 없냐에 대해 제가 안 적었다고 하셨는데 저는 계속 있다고 명확히 작성했습니다.

'사이트에서 2가지 의미로 쓰고 있으며, 이는 명백히 혼란을 일으킬 수 있는 요인이다' 라는 주장이 '중요도는 없다'라고 적은 것으로 보셨다는 것이군요...

관련 문제들에 메모로 '개념/알고리즘' 여부를 적어주거나 '단계별로 풀어보기'에 '개념으로만 쓰인 예제'를 추가해주는 2가지 방안 중 하나를 한다면 해결 가능한 문제입니다.

zenith82114   1년 전

저 두 단어는 표기법을 잘못 쓰는 경우가 실제로 흔하기 때문에 저렇게 잘못 읽힐 여지가 애초에 없게끔 신경 쓰는데 이번에는 캐치를 못했습니다. 타당한 의견이라는 건 확인했고, 그 다음 단계로 그렇다면 지금 상태를 개선하면 정량적으로 얼만큼의 임팩트를 줄지 궁금했다는 의미였습니다.

adfsfsf   1년 전

알겠습니다. 이제는 확실히 정리된 것 같네요. 진짜 마지막으로, 끝!

댓글을 작성하려면 로그인해야 합니다.