PS/기타 PS 사이트6 [자바] 정올 1214 - 히스토그램 (java) 목차문제 : jongol1214 풀이 일단 단순화 시켜서 생각해보기 위해 좌측부터 우측으로 점차 증가하는 형태와 점차 감소하는 형태를 나눠서 생각해보자. 1. 우선 높이(h)가 같거나 증가하는 경우이다.이전과 비교해서 값이 같거나 증가하고 있다면, 아직까지는 넓이를 계산하는 것이 의미가 없다. n개를 모두 입력받았거나, 이후 감소하는 구간을 만나기 전까지는 넓이를 계산하지 않고 있다가 맨 마지막 지점에서만 계산해주면 된다. 직관적으로 맨 마지막 지점을 포함한 상태에서 다음과 같이 이전 높이들을 확인하면 될 것임을 예상할 수 있다. 즉, 높이가 동일하거나 증가하는 경우 맨 마지막 지점에서 이전 지점 모두 중 의미가 있는 넓이는 모두 계산할 수 있다. 2. 다음은 높이(h)가 감소하는 경우이다.이번엔 .. 2026. 5. 14. [자바] 정올 1013 - Fivestar (java) 목차문제 : jongol1013 풀이 백준이 문닫은김에 오랜만에 생각나서 알고리즘 문제를 풀어보게 되었다.확실히 머리론 대충 알겠는데 구현력이 떨어진게 맞는 것 같다. 아무래도 현업에서 재귀나 복잡한 for문 같은걸 쓸일이 없기도 하고, 요즘 워낙 LLM님이 구현을 잘해주셔서. 오랜만에 풀다보니 상당히 답답했다 ㅋㅋ 1. 일단 한 행만 있다고 생각해보자. (N=1)A. *****.....B. ..**..C. .******..D. ..... 이 경우 간단하다. 그냥 연속된 '*'을 세다가 5개 미만이면 불가능한 경우이다. A는 1개로 가능하고, B는 -1이고, C는 2개로 가능하고, D는 0개로 가능하다(-1 아님. 0개로 가능한거다.). 만약 이 문제가 여기서 끝났다면 브론즈티어였을 것 같다... 2026. 5. 7. [Koistudy] 1396 - 눈 내리는 밤 (L) (C++ cpp) 문제 : koistudy-1396 풀이 현재 n개의 영역의 눈 높이를 arr[i] 로 나타낸다고 해보자. arr[x]는 x 영역의 눈 높이이다. 그리고 F[i] = arr[i] - arr[i-1] 이라고 정의해보자. 그렇다면 arr에 대한 [A, B] 구간을 W만큼 업데이트하는건 F[]로 따졌을 때 다음과 같다. F[A] += W F[B+1] -= W 왜냐하면 F[X] = F[X] - F[X-1] 이므로 F[A]와 F[B+1]을 제외하고는 변화가 없기 때문이다. 즉, 기존 range update가 point update로 변경된다. 다음으로 arr[x]의 값을 알기 위한 쿼리는 F[1] + F[2] + ... + F[X] 로 나타낼 수 있다. 왜냐하면예를들어 X가 5일 경우 F[1] + F[2] + F[.. 2023. 2. 10. 코드업 4040 자바 - 펜션 (CodeUp 4040 java) 문제 : CodeUp4040 어차피 중간에 하루라도 지낼 수 없다면 조건이 만족되지 않는다. 따라서 s부터 시작해서 매번 가장 길게 지낼 수 있는 방에서 지내면 된다. 그러다가 지낼 수 없는 날이 되면 -1, t 이상이 됬다면 변경 횟수를 출력하면 된다. 증명은 간단한데, 매번 가장 길게 지낼 수 있는 방이 아닌 다른 곳에 묵었을 때 더 이득이 되는 경우가 있다면 위의 추론이 틀린 것이다. 하지만 더 짧은 기간 지낼 수 있는 방을 고르더라도 동일한 변경횟수까진 나와서 더 낮은 변경 횟수가 될 수 없음은 직관적으로 알 수 있다. 따라서 그리디하게 선택하면 된다. 그럼 해당하는 날에 어느 방이 가장 길게 묶을 수 있는 방인지 어떻게 알 수 있을까? 이건 날을 거꾸로 진행하면서 몇 일을 지낼 수 있는지 pre.. 2022. 4. 18. LeetCode 25 - Reverse Nodes in k-Group - Hard (Java) 리스트 구현을 직접 해봤다면 어렵지 않게 풀 수 있는 문제이다. 다만 O(N)에 풀 수 있는 아이디어는 어쩌면 생각하기 어려울 수도 있을 것 같다. 원본 리스트를 순회하며 reverse 할 항목들을 tmp배열에 넣어둔 뒤, k개 만큼 채워졌다면 역순으로 결과 리스트에 넣는다.(코드에서 idx==k 일 경우) 그리고 마지막에 나누어떨어지지 않는 항목들에 대해서는 리스트의 끝을 만날 경우 tmp에 있는 남은 항목들을 역순이 아니라 원래순서대로 출력해주면 된다.(코드에서 head==null일 경우) 이전에 풀었던 5번 Medium이 더 어려웠던 것 같은데.. 리트코드 난이도 책정 방식이 좀 이상한 것 같다. 코드 : github /** * Definition for singly-linked list. * pu.. 2021. 12. 18. LeetCode 5 - Longest Palindromic Substring - Medium (Java) LeetCode도 자주 들어봤는데 한번도 해본적은 없어서 한번 풀어봤다. 일단 시간 제한이 안써있으면서 TLE(시간초과)는 뜨는게 상당히 거슬린다. 시간제한 알려주든가! 프로그래머스도 그게 좀 불만인경우가 많은데.. 그리고 남의 코드를 못본다는 점이 상당히 아쉬워서 메인 OJ(Online Judge)로는 별론 것 같다. 그래도 유명한 사이트니 간간히 생각날 때 하나씩 풀어보게 될 것 같다. 처음 해보는 사이트라 여기저기 눌러보다보니 DP 태그가 붙어있는걸 봤다. 이미 태그를 봐버린 이상 태그대로 푸는건 자존심 상하기도 하고 어차피 Brute Force(이하 BF)로도 가능할 것 같아서 BF(하지만 Back Tracking을 좀 끼얹은)로 풀어봤다. 1. 단순히 모든 경우를 보도록 짜게되면 다음과 같이 짜.. 2021. 11. 30. 이전 1 다음
