자료알고/알고리즘 검색 결과

해당 글 87건
Longest Substring Without Repeating Characters 문제를 풀면서 슬라이딩 윈도우를 정복해 봅시다.

이번 시간에는 Longest Substring Without Repeating Characters 문제를 풀어보면서, 어떻게 시간 복잡도를 분석하는지 보도록 하겠습니다. 이 문제는 길이가 5만 이하인 문자열에서, 문자가 반복되지 않는 가장 긴 부분 문자열을 찾는 문제입니다. 문자열에 들어갈 수 있는 문자는 알파벳, 숫자, symbol, 그리고 space 문자입니다. 보통, 이렇게 주기 보다는 CodePoint는 아스키 코드 범위 내에 있다. 혹은 유니코드 범위 내에 있다. 이런 전제를 까는 게 더 좋기는 한데 넘어가 봅시다. 이모지 같은 것들 때문에 태클이 들어올 여지가 있습니다. 저 또한 문제 제작했을 때 간과했던 부분이기도 합니다. 문자열에 들어갈 수 있는 문자 집합이 작을 때에는 어떨까요? 놀랍게도..
자료알고/알고리즘 2021. 8. 27. 20:47
정보를 잘 저장해서 사전순 다익스트라 문제를 풀어봅시다.

얼마전에 추가된 tony님 문제를 풀었습니다. 필수 유형들과 어려운 유형들이 몇 개 있는데요. 알아가면 좋을 법한 트릭을 하나씩 소개해 드리겠습니다. 먼저 산책 시리즈입니다. large나 small이나 별 다른 건 없으니, 풀어보도록 합시다. 문제를 읽어보면, 제일 중요한 것은 딱 하나임을 알 수 있어요. S에서 E로 갈 때 최단 거리가 여러개 있다면 사전 순으로 가장 앞선 것을 택해라. k번째는 훨씬 어려워서, 사전순으로 가장 앞선 것을 택하라고 했을 겁니다. 그러면 어떤 정보가 필요할까요? 즉, 모든 i에 대해서, e까지의 최단 거리를 구해야 함을 알 수 있어요. 이런 그래프가 있고, s가 1, e가 4라고 해 봅시다. 처음에 우리는 1에서 4까지 가는 최단 경로 중에 사전순으로 앞선 경로를 구해야 ..
자료알고/알고리즘 2021. 8. 11. 16:00
백준 시철이가 사랑한 수식을 브루트 포스로 검수한 썰

어느덧 500번째 글입니다. 그냥 정보글은 시시하니, 대회 검수 썰을 풀어보도록 하겠습니다. SUAPC를 검수하면서 신경을 썼던 것 중 하나는, 대회에 출제된 20940번 문제였습니다. 대회에 출제된 문제 중에 난이도가 높은 그룹에 속할 것이라고 예상했고, 실제로 그렇게 되었습니다. 이 문제를 검수할 때 세웠던 원칙 중 하나는 브루트 포스로 검증을 해 볼만한 사이즈가 되면, 검증을 해 보자는 것이였습니다. 100만이면 모르겠지만, 50만이면 해 볼 만 했습니다. 잘 돌리면 1시간 정도에 해결을 할 수 있었기 때문입니다. 이 문제의 초기 조건은 N은 [1, 50만], K는 10^9+7이였습니다. 브루트 포스로 돌릴 만 합니다. 그런데, 이걸 그냥 브루트 포스로 돌리기에는? N이 대충 50만. 50만의 제곱..
자료알고/알고리즘 2021. 5. 21. 04:02
기하 문제를 다룰 때 잘 써먹게 되는 radian degree 변환을 알아봅시다.

가끔 기하 문제를 다루다 보면, 각도를 알아야 하는 경우가 있습니다. 혹은 주어진 각도를 가지고 무엇인가를 계산하거나. 그걸 하기 위해서는 라디안과 degree를 알아야 해요. 간단하게 알아보도록 하겠습니다. 먼저, python이나 java에서 제공되는 삼각 함수들에 대해 알아봅시다. cos을 예로 들어보겠습니다. 설명을 보시면, Params가 an angle, in radians로 되어 있습니다. 파이썬의 cos도 마찬가지입니다. measured in radians가 들어가 있습니다. 60을 Math.cos의 인자로 넣어봅시다. 그러면, -0.95241298041이 나오는데요. 우리가 알고 있는 cos60도는 0.5인데, 이것과 다른 수치가 나와 버립니다. 이는 Math.cos에 들어가는 것이 degr..
자료알고/알고리즘 2021. 5. 16. 02:15
왜 위상 정렬을 이용하면 그래프 사이클이 있는지 판단할 수 있을까요?

그래프에 사이클이 있는지 없는지 판단하는 방법 중 하나는 위상 정렬을 이용하는 것입니다. 어떻게 이용한다는 것일까요? 방향성이 있는 그래프에서, indegree가 0인 게 하나도 없다면 사이클이 있다고 판단합니다. 물론, indegree가 0인 노드가 있는데 사이클이 있는 경우도 있습니다만, 이건 글의 말미에 잠깐 다루겠습니다. 먼저, 아래와 같이 조건을 제한해 보겠습니다. 방향성이 있는 그래프에서 아래 조건이 성립합니다. 이 경우, indegree 값이 0인 노드가 존재하지 않는 그래프에 대해서 판단하는 것 보다는 조금이나마 더 쉽습니다. 사이클이란, i에서 i로 가는 경로를 의미합니다. 제한된 조건을 만족하는 노드 갯수가 n인 그래프를 생각해 봅시다. 일단 indegree 값이 1이므로, 나가는 것이..
자료알고/알고리즘 2021. 5. 3. 06:45