JAVA 8 터집니닷!! JAVA 11로 하십쇼!!아 자꾸 터지길래 하다 못해서 구글링 코드 그대로 복붙해도 메모리 터짐..질문게시판 안가려다가 가보니까 다들 JAVA 11로 대피하라고 써있더라 (진즉 볼걸;;;)아무튼 이분 탐색에 조금씩 익숙해져가는게 느껴졌던 문제라 좋았다구현 방식은 올바르게 기획했으나, 구현에서 빵꾸나서 실패했던 문제좀 더 파보자!! 아 오늘은 풀이법이 두 개다 하도 메모리 터져서 다른 방식으로 하나 더 구현했음 (그래봐야 이분탐색으로만 했음..)첫번째 버전이 더 깔끔해서 내 취향근데 속도도 첫번째가 좀 더 빠르긴했음문제 분석/*[백준]9024, 두 수의 합[문제파악]- 여러 개의 서로 다른 정수 S = {a1, a2, …, an} 와 또 다른 정수 K 가 주어졌을 때, S 에 속하..

이분탐색... ㅂㄷㅂㄷ얘도 PQ처럼 한 2주 잡고 매일 매일 도전해야할 것 같다어려워 어려워그래도 오늘은 lower bound 개념을 이해하고... 이분 탐색을 경계를 찾거나(index), 특정 값을 찾는 등에서, 크게 2가지에서 장점이 있음을 알았package Record_2025;/*[백준]2428, 표절[문제파악]- 세계적인 석유 재벌이 1등 상품으로 페라리를 걸고 프로그래밍 대회를 개최했다.- 이 대회의 참석자는 총 N명이고 각각 솔루션 파일 1개를 제출했다.- 이 솔루션 파일을 F1, F2, ..., Fn이라고 한다.- 채점 결과를 발표하기 전에, 남의 것을 배낀 사람이 있는지 찾아내려고 한다.- 이 대회의 주최측은 두 파일을 비교해서 너무 비슷한지 아닌지 판별하는 프로그램이 있다.- 하지만, ..

풀수록 나는 이분 탐색을 잘 모르는듯하다난이도를 낮춰가며 풀어도 어렵네 ㅠ당분간은 이분탐색만 풀어야겠다 이분탐색인지 판별하는 방법 1) 정답이 특정한 수의 범위 내에서 최솟값 or 최댓값을 찾는 문제라면?! 2) 결정문제 (YES/NO)로 바꿀 수 있다면?!package Record_2025;/*[백준]2792, 보석 상자[문제파악]- 보석 공장에서 보석 상자를 유치원에 기증했다.- 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다.- 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다.- 이때, 보석을 받지 못하는 학생이 있어도 된다.- 하지만, 학생은 항상 같은 색상의 보석만 가져간다.- 한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투를 한다.- 원장 선생님은 이런 질..

이분탐색을 어디서 써야하는지 감을 못잡던 문제얘는 이해하는데도 좀 애를 먹었다 현재 높이에서 몇개의 석순, 종유석에 부딪히는지 구할 때 for문을 쓰게 될 것이다이 때 현재 높이에서 부딪히는 것들을 계산할 때 이분탐색을 쓰게 된다석순 따로, 종유석 따로 계산한다 석순에서 이분탐색을 통해 최댓값을 조여가며 h 높이와 같거나 그보다 큰 것의 위치를 찾는다([1, 3, 5, 7, 8, 9, 10]에서 비행높이가 h가 3이면, 2번째인 3이 나올 때까지 right를 조여가는 것) 그러면 이제 전체 배열의 길이 7에서 2를 빼면 총 5개에 부딪힌단 소리다그럼 이제 이렇게 석순을 구했으면, 종유석도 똑같이 구하고 둘이 더해주면 현 비행높이에서 부셔야하는 것들의 갯수가 나온다그게 이 문제의 이분탐색 구현 방법임.....

투포인터 접근법은 맞았던, 그치만 좀 헤맸던 이진 탐색 문제나 이진탐색 겁나 못푸네;;;당분간 얘만 풀어야겠네..package Record_2025;/*[백준]2467, 용액[문제파악]- KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다.- 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.- 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.- 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다.- 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.-..

약한 이분 탐색을 풀기위해 요즘 계속 풀고 있다근데 이 문제는 너무 어렵게만 생각했던 문제...집 사이의 거리를 이분탐색으로 정해주되, 각 집끼리 거리가 필요한만큼 벌어졌는지 체크는 그냥 for문 돌리면 됐다가끔은 어려운 문제가 내가 고심했던 어려운 방법보다 더 쉬운 방법으로 풀리는듯package Record_2025;/*[백준]2110, 공유기 설치[문제파악]- 도현이의 집 N개가 수직선 위에 있다.- 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.- 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다.- 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 ..

DP가 그렇게 헷갈리던 문제DP는 규칙 못찾아서 식 못세우면 그냥 어디부터 건드려야할지...어렵다 ㅠ막상 보면 쉬운데 그 쉬운걸 못하고 있네DP도 진짜 많이 풀어봐야할 문제 카테고리 중 하나package Record_2025;/*[백준]9251, LCS[문제파악]- LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.- 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.[입력]- 첫째 줄과 둘째 줄에 두 문자열이 주어진다.- 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.[출력]- 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 ..

너무 어렵게 생각해서 못 푼 문제PQ에 있는걸 꼭 전부 다 실시간으로 업데이트하려고 하지말고, 그냥 저장소처럼 하나씩 기록해두는 용도로 쓰는 것까지도 염두에 둬보자 ㅠ그리고 제발 좀 int로 해결되는지도 체크하는 습관을 들이라고~/*[백준]17612, 쇼핑몰[문제파악]- 대형 쇼핑몰에서 쇼핑을 마친 N명의 고객들이 계산을 하고 쇼핑몰을 떠나고자 계산대 앞에 줄을 서 있다.- 각 고객은 커다란 짐수레(cart)에 물건을 담아 계산대로 간다.- 쇼핑몰에는 아래 그림과 같이 K개의 계산대가 병렬로 배치되어 있다.- 쇼핑몰 안내원들은 계산대에 온 사람들을 가장 빨리 계산을 마칠 수 있는 계산대로 안내를 한다.- 안내원은 각 계산대에서 기다리고 있는 사람들이 계산을 하는데 얼마나 걸리는지 이미 알고 있다.- 안내..

아니 너무 어려운거 아니냐고요 ㅠPQ는 왤케 다채로운 문제가 많은걸까 (근데 모든 알고리즘이 그렇겠지..)얘는 진짜 다시 풀어봐라 꼭꼭꼭!package Record_2025;/*[백준]2461, 대표 선수[문제파악]- KOI 중학교에는 N개의 학급이 있으며, 각 학급의 학생 수는 모두 M명으로 구성된다. 이 중학교에서는 체육대회에 새로운 종목의 경기를 추가하였다.- 이 경기에 대해 모든 학생들은 저마다의 능력을 나타내는 능력치를 가지고 있으며, 이 능력치는 모든 학생이 서로 다르다.- 이 경기는 한반에서 한 명의 대표선수를 선발하여 치른다.- 경기의 형평성을 위하여, 각각의 반에서 대표로 선발된 모든 학생들의 능력치 중 최댓값과 최솟값의 차이가 최소가 되도록 선수를 선발하려고 한다.- 예를 들어, N=3..

아 PQ 문제는 곧잘 익숙해지지가 않는다(그나마 다행인건 PQ를 다루는 것에는 익숙해지고 있다)더 많이 풀어봐야 할듯하다/*[백준]1826, 연료채우기[문제파악]- 성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다.- 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다.- 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다.- 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다.- 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화 하려 한다.- 그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 있다고 한다..

PQ를 기록용 자료구조로 쓸 수도 있구나..를 깨달아버린 문제..그냥 맨날 뭐 다 정렬에만 쓰고, 클래스 만들어서 디밀어넣고 했는데근데 생각해보면 그냥 얘도 자료구조의 하나일 뿐인데 왜 isVisited마냥 단순 기록하는데 못 썼을까당연한 말인데 당연하지 못했던 지난 날의 내 풀이법들 ㅠ개선하자~~package Record_2025;/*[백준]11000, 강의실 배정[문제파악]- 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.- 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.- 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다..

쉽..네...? 했다가 탈탈 털린 문제PQ를 쓰는 방법도 여러가지였고, 자료형의 함정을 파둔 것을 눈치 못채고 있다가 뚜들겨 맞았음진짜 다양한 문제, 특히 어려운 문제도 여럿 접해봐야 하는걸 여실히 느꼈다봐본적 없는 풀이법과 생각에 '와 이런게 있어' 하는 지점이 너무 많기 때문...열심히 풀어봅시당package Record_2025;/*[백준]1202, 보석도둑[문제파악]- 세계적인 도둑 상덕이는 보석점을 털기로 결심했다.- 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다.- 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다.- 가방에는 최대 한 개의 보석만 넣을 수 있다.- 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는..

위상정렬을 처음 마주했다이게 뭔데!!!!!배워도 배워도 늘 새로운게 나오다니... 짜릿하네요나중에 꼭 다시 풀어보자package Record_2025;/*[백준]1766, 문제집[문제파악]- 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다.- 문제는 난이도 순서로 출제되어 있다.- 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다.- 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다.- 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다.- 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다.- N개의 문제는 모두 풀어야 한다.- ..

이거는.. 너무 어려웠다...뭐라는거야 진짜 ㅠ 일단 온종일 붙잡고 최대한 이해하려고 노력함..근데 진짜 더는 머리가 안 돌아감추후에 다시 풀어보자.. /*[백준]13325, 이진 트리[문제파악]- 각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다.- 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다.- 루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다.- 이 문제에서는, 어떤 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 같도록 하고, 또한 에지 가중치들의 총합을 최소화 하려고 한다.- 예를 들어, 그림 1(a)에 있는 높이 2 인 포화이진트리를 살펴보자.- 에지 옆에 있는..

와! 답보지 않고 잘 풀어냈다!! (드디어!!)이 문제는 아래 순서로 푸는게 팁이었음 (다른 사람들도 이렇게 풀더라 신기...)1) 공기로부터 탐색 시작 (BFS, DFS)2) 치즈를 만나면 따로 저장해둠3) 저장해둔 치즈에서 사방탐색을 시도4) 2면 이상 공기와 접촉 시, 녹임5) 다시 반복 유의할 점은 2면 이상 공기와 접촉했는지 체크할 때, 치즈에게 둘러쌓여 내부로 판정되는 공기는 공기가 아니라는 점!!!이것 때문에 4%에서 계속 터졌다...아래가 반례니 넣어보시면 알듯더보기반례 (내부 공기는 별도로 체크되고 있는지)9 90 0 0 0 0 0 0 0 00 0 0 0 1 0 0 0 00 1 1 0 1 0 1 0 00 1 1 1 1 1 1 0 00 0 1 0 1 1 0 1 00 1 0 1 1 0 1 0..

트리의 구조와 원리에 대해 이해하기 좋은데, 내겐 어렵고 오래 걸렸던 문제라 기록하고자 한다트리에 취약했던 나라서 이 문제는 특히 더 오래 걸렸음한줄씩 뜯고 씹고 맛보고 겨우 이해했다디버깅 안하고 이해해서 진행하려니 여간 쉽지 않음...트리 더 열심히 해야지 뭐 ㅠpackage Record_2025;/*[백준]2263, 트리의 순회[문제파악]- n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다.- 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.[입력]- 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다.- 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다...

반례에 반례에 반례의 꼬꼬물이었던 문제내가 미처 생각하지 못해 터진게 너무 많았고 그로인해 삽질을 너무 많이 했음...진짜 미리 설계랑 고민 좀 하고 코딩하자 ㅠpackage Record_2025;/*[백준]1068, 트리[문제파악]- 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.- 트리가 주어졌을 때, 노드 하나를 지울 것이다.- 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오.- 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.- 예를 들어, 다음과 같은 트리가 있다고 하자.- 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드)- 이때, 1번을 지우면, 다음과 같이 변한다.- 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.- 이제 리프 노드..

전에 나에게 쓰린 맛을 보여줬던 Trie...그 때 당시 사전식 입출력 문제였고, Trie를 몰라도 TreeMap으로 풀 순 있었다다만 테케 최적화를 실패해 히든 테케에서 시험에서 떨어졌었던 ㅠ 그래서 Trie 보자마자 득달같이 달려들어서 도전했는데 어렵다...이걸 그냥 '아 이론이 이런거구나' 말고 진짜 내가 구현하려니까 뭐 걍 손발 다 꼬임...정리해두고 한번에 소화할 수 있는 문제는 아닌 것 같으니 꾸준히 봐보자 ㅠpackage Record_2025;/*[백준]14725, 개미굴[문제파악]- 우리의 천재 공학자 윤수는 이 개미들이 왜 행복한지 궁금해졌다.- 행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다.- 로봇 개미는 센서가 있어 개미굴..

트리구조 배우기에 좋았던 문제와 못 풀겠어!!는 아닌데, 트리 구조에 미숙하다보니 여러 힌트를 참고할 수 밖에 없었다현재는 하나의 노드를 기준으로 DFS (재귀)를 활용하여 서브 트리의 규모를 계속해서 새롭게 count 하고 있다 (메모리 초과)그렇기 때문에 DP를 적용하면 더욱 최적화할 수 있다 package Record_2025;/*[백준]15681, 트리와 쿼리[문제파악]- 간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자.- 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.- 만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자.[입력]- 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다..

기초가 정말 중요했던 문제안다고 생각했던 것들도 기억 안나고 헷갈리는 것들 투성이었다 ㅠ자료 구조 공부도 더 해야할듯하다 이번에 다시금 깨우친 것들을 정리해보자면(1) 기본적으로 Map을 For문 돌리는 방법(2) TreeSet은 무적이 아니라는 것 (정렬은 해주지만 삽입과 탐색시 배열보다 더 오래걸린다는 단점)(3) Collections.max 라는 함수가 있다는 것...(4) Map.Entry에서 Entry가 정확히 무엇인지    - Map.Entry에서 Entry는 항목 또는 항목의 쌍을 의미    - 즉, Map.Entry는 Map의 하나의 key-value 쌍을 나타내는 객체이다빠르게 푼 사람들은 그냥 문제조건에 따라 배열을 -4000 ~ 4000으로 해결했더라...배워도 배워도 끝이 없군..!..