https://softeer.ai/practice/6288 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 1. 서론 언뜻 보면 막막한데 그냥 그리디? 수학? 구현? 문제이다. 그러니까 크게 어려울 것 없는 문제이다.그런데 생각보다 정답률이 낮아서 놀랐다. (근데 그럴만한 이유가 있더라는...) 2. 문제 풀이 보석들을 배낭에 최대한으로 넣어가야 한다. 그러기 위해서 배낭에 최대한으로 넣을 수 있는 무게 w, 보석의 개수 n이 주어진다.그 후 n개의 보석에 대해서 각각 보석의 무게와 개당 가격이 주어진다.처음에 잘 이해가 안 갔는데 예를 들어 90, 1 이라고 하면 1개당 1이며, 70, 2라고 하면 1개당 값이 2인 것이다. 그리고 90, 70이 한 덩이가 아니라 각 1개라고 봐도..

https://www.acmicpc.net/problem/14575  1. 서론 이분탐색 문제이다. 그런데 이제 푸는 법을 모르겠는... 범위가 n개 주어지는데 그 범위 안에 만족하는 값 x가 다 같은 값이 아니라 그냥 x이하면 되는 걸 처리하는 게 생각이 안 나서 결국 혼자 해결하지 못해 버렸다... ㅜㅜ 2. 문제 풀이 사람수 n, 사람에게 줘야하는 술의 수의 합 t가 있다.그리고 그 사람 별로 소화 가능한 술의 범위가 있다. 문제의 조건은 이거다. 1) 이 범위를 모두 만족시켜야 함.2) 그 값은 모두 같은 값이 아님, 사람마다 다르게 줄 수 있음 범위 안에서 각자 사람들에게 각자 다른 양의 술을 주지만, 그 합은 t여야 하고, 그 값을 초과하지 않는 값 중에서 최솟값을 구하는 문제이다. 처음에는 ..

이 포스팅에는 제가 이분탐색 문제를 풀면서 깨달은 바를 적어보겠습니다.(고수분들은 보지 않으셔도 좋습니다. 하수가 적은 것이기 때문에...)  보통 이분탐색은 탐색해야 하는 범위가 너무 큰 경우, 시간을 줄이기 위해서 사용하게 됩니다.주로 작은 수부터 큰 수로 정렬을 한 뒤에 특정 숫자보다 크면 범위를 작은 숫자가 있는 범위로 옮기고, 작으면 큰 숫자가 있는 범위로 옮겨서 탐색을 하게 됩니다. 그렇기 때문에 어느 새인가부터 습관적으로 배열을 정렬해서 사용하기 시작했습니다.물론 정렬을 사용해서 푸는 것이 틀린 것은 아닙니다.하지만 어떤 경우에는 정렬을 하지 않는 것이 시간복잡도가 줄어드는 경우가 있습니다. https://www.acmicpc.net/problem/16401 백준의 과자 나눠주기(16401)..

https://www.acmicpc.net/problem/2470 1. 서론 https://coding-log.tistory.com/267 [JAVA] 백준 2470 두 용액https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어coding-log.tistory.com 이 문제는 예전에 투 포인터로 푼 적이 있는 문제이다. 하지만 이분 탐색을 공부하기 위해서 이분 탐색으로 풀어봤다.예시를 보면 대강 맞는 것 같은데 1%에 틀려서 다른 풀이들도 보고 GPT한테 코드 좀 고쳐달라고 했는데 어쨌든 혼자서 풀지 못한 문제이..

https://www.acmicpc.net/problem/19951 1. 서론 이 문제는 누적합 유형의 문제이다. 그런데 문제는 일반적으로 누적해서 합을 구한 후 그를 응용하는 일반적인 누적합 문제가 아니다.나는 GPT에게 이 문제를 어떻게 누적합으로 푸는 거냐고 물어봤고 GPT는 '차분배열'을 이용하면 된다고 했다.아마... 혼자서는 못 풀었을 듯. 이렇게 하나 배웠으니 뿌듯합니다.   2. 문제 풀이 n개의 칸이 있고, 특정 구간을 뜻하는 a, b가 m번 주어진다. n개의 칸에서 a~b 구간만 k만큼 값을 더해준 값을 구하는 것이 문제다.문제는 이 n, m의 범위가 100,000 이라는 것이다. 즉, 그냥 단순히 반복문을 이용해 구간만큼 값을 돌려준다면 시간초과가 나게 되는 문제인 것이다. 처음에는 ..

1) n진수를 10진수로 //n진수인 숫자 x, 참고로 String형이다Integer.parseInt(x, n) 이렇게 코드를 작성하면 n진수인 숫자(String) x를 10진수로 변환해 준다. 그럼 이를 다시 n진수로 변환해 보자.     2) 10진수를 n진수로 //숫자 x를 n진수로 변환Integer.toString(x, n) 10진수인 숫자(Int) x를 n진수로 변환한다.이때 toString이기 때문에 문자형으로 변환된다.만약 정수형이길 바란다면 또 형변환 때리면 가능.  parseInt와 toString 만으로 변환이 가능하다는 게 혁명적이라서 로그를 남긴다 ~.~