백준 검색 결과

해당 글 24건
java 박싱 언박싱과 오버헤드에 대한 이야기

백준 1325번은 c,c++로 풀면 쉽게 풀리는 dfs, bfs 문제 중 하나입니다. 그런데 Java로 풀면 시간이 빡빡한데요. 그 이유 중 하나는 박싱, 언박싱에 의한 객체 생성 때문입니다. 이에 대해서 아직 익숙하지 않으시다면, 이 포스트를 보고 오시는 것도 좋습니다. 통과를 하시고 나서, java로 통과한 코드 중에서 1등과 2등 코드의 차이를 보면 대충 3초 가량이 나는 것을 볼 수 있습니다. 이 두 코드를 보시면, 하나는 primitive type 배열을 썼고, 다른 하나는 그렇지 않았음을 볼 수 있는데요. 3초 차이라니. O(nm) 복잡도에서, 아슬아슬하게 통과할 복잡도에서, 3초면 상당히 큽니다. 그 원인 중 하나가 필요 없는 객체 생성이라 했으니, trace를 해 보겠습니다. jdk 8 기..
코딩/Java 2020. 12. 6. 15:23
백준 1060번 구간 : 후보해를 추린다.

이번 시간에는 백준 1060번 문제를 풀면서, 후보해를 어떻게 추리는지 보도록 하겠습니다. 문득 떠오르는 시스텟 페일 간단한 알고리즘을 물어보는 코딩테스트에도 이 글에서 간접적으로 설명한 것들은 나올 법 하니, 알아두면 좋을 듯 싶습니다. 사실 코테 접은 지 1년 넘어서 잘 모른다는 것은 함정입니다. 문제는 아래와 같습니다. 어떤 집합 S에는 양의 정수 L개가 있고, f(x)를 아래 조건을 만족하는 구간의 갯수로 정의합니다. 0보다 큰 정수 x, y가 있다고 한다면, f(x) < f(y)이거나, f(x) = f(y)이고 x
자료알고/알고리즘 2020. 12. 3. 01:21
백준 소수인팰린드롬 : 팰린드롬인지 먼저 검사한다.

안녕하세요. 조경완입니다. 백준에서 문제들을 풀다 보면, 소수인팰린드롬 문제도 보셨으리라 생각합니다. 어렵지 않은 문제이지만, Loop를 칠 때, 어떻게 치면 좋은지 생각해 볼 수 있는 문제인 듯 싶어서 가지고 오게 되었습니다. 문제는 아래와 같습니다. 최악의 경우에는 a가 5, b가 1억이니 만만치 않은 문제인 듯 싶습니다. 그런데, 314명이 풀어냈습니다. 1억까지를 에라스토스테네스의 체로 거른다고 해도 힘들고, 그렇다고 팰린드롬을 로그 복잡도로 판별하고 루트 복잡도로 소수임을 판별하자니. 그것도 힘듭니다. 어떻게 하면 좋을까요? 아이디어는 의외로 단순합니다. 일례로 99823419가 소수인지 판단하는 것은 쉽지 않습니다. 그런데, 팰린드롬인지는 어떻게 판정하면 되나요? 그냥 뒤에서 부터 본 문자랑 ..
자료알고/알고리즘 2020. 11. 12. 02:52
백준 11003 최소값 찾기 : 큐와 덱를 응용해 봅시다.

요새 코테 철이 되었습니다. 저도 간간히 구현력을 잃어버리지 않기 위해서 조금씩 복기만 하고 있습니다. 백준 11003번 문제는 최솟값을 구하는 문제입니다. 특정 구간 [e-k, e]에서의 최솟값을요. 단, 0보다 작은 위치의 구간은 무시하고 구해야 합니다. 별로 어렵지 않아 보이는데, 문제는 n이 500만입니다. 입력 받느라 시간이 많이 가는 건 흐음. O(n)으로 줄일 수 있습니다. 다들 아시는 기법을 소개하도록 하겠습니다. 관찰을 해야 할 것은 2가지 상황입니다. 어떠한 데이터가 추가되는 상황하고, 제거되는 상황. i번째에 있는 데이터가 제거되면, 더 이상 추가되지 않는다는 것을 관찰하는 것 또한 포인트입니다. 현재, 이런 식으로 데이터가 들어갔다고 해 보겠습니다. 그리고 저는 7번째 위치에 있는 ..
자료알고/알고리즘 2020. 9. 11. 02:37
java BigDecimal을 이용해서 실수를 다뤄 봅시다.

백준에서 a^b꼴의 문제를 본 적이 있을 겁니다. 문제는 여기에서 풀어보실 수 있습니다. 물론, b는 0보다 크거나 같고 100보다는 작거나 같은 정수이고, a는 소수점 밑에 자리수가 9개까지 나올 수 있습니다. 사실, 저는 이것을 .을 기준으로 일일히 파싱해서 풀었습니다. 즉, .을 기준으로 나누면 j/m꼴이 됩니다. 그러니, (j/m)^b을 계산하는 문제로 바뀌고, m은 10^q꼴이니, j^b의 결과값에 따라서 적절히 잘 파싱하면 됩니다. 그런데, 그리 한다면, j는 최대 11자리 ~ 12자리의 정수로 바뀔 거고, b는 최대 100이니, 1100자. 결국 이 문제를 제대로 풀려면 큰 수 곱셈을 잘 구현해야 한다는 이야기가 되겠습니다. 이펙티브 자바가 있다면 정확한 답이 필요하다면 float와 doub..
구현 2020. 8. 23. 20:50