본문 바로가기

PS831

[자바] 백준 14465 - 소가 길을 건너간 이유 5 (java) 문제 : boj14465 필요 알고리즘 개념 슬라이딩 윈도우, 누적합 알고리즘, 투 포인터 중 하나 세가지 방식 모두 구현이 가능하다. 당연히 다른 방법도 있을 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1부터 N까지 나타낼 수 있는 배열을 만들고, 고장난 신호등은 1, 정상인건 0이라고 하자. 이 경우 연속된 모든 K개의 구간의 합이 곧 해당 구간의 고장난 신호등의 갯수 = 수리해야 하는 신호등의 갯수가 된다.. 2022. 9. 18.
[자바] 프로그래머스 - 크레인 인형뽑기 게임 (Lv1, Java) 문제 : Programmers-크레인 인형뽑기 게임 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 시뮬레이션 문제에서 제시된 대로 구현만 해주면 된다. 스택 배열 자체로 구해도 문제 없으나, 로직 구성상 스택을 활용하면 더 깔끔하게 구현 가능하다 배열 자체에서 진행해도 되지만, 실수를 확실히 줄일 수 있고 더 맞는 자료구조가 있다면 그걸 쓰는게 맞다고 본다. 이 문제의 경우 각 열에 대해 스택 자료구조를 사용하고, 바구니도 스택을 사용할 시 코드 설계가 매우 깔끔해지고 실수의 여지도 많이 줄어든다. 그러니 스택을 사용해서 한번 구현해보자. 예를들어 코드상의 stk[]과 basket은 다음과 같은 스택 구조를 나.. 2022. 9. 17.
[자바] 백준 16404 - 주식회사 승범이네 (java) 문제 : boj16404 필요 알고리즘 개념 lazy propagation을 적용한 세그먼트 트리 혹은 펜윅 트리 세그먼트 트리 + lazy propagation 혹은 range update가 가능한 펜윅 트리를 알고 있어야 풀 수 있다. 오일러 경로 테크닉 트리를 펴서 구간을 만드는 오일러 경로 테크닉이 필요하다. 어려운 개념도 아니고, 기존에 모르는 상태로도 얼마든지 생각해낼 수 있는 부분이라 반드시 알고있어야하는 부분은 아니다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀.. 2022. 9. 17.
[자바] 백준 7469 - K번째 수 (java) 문제 : boj7469 필요 알고리즘 개념 정해 : 머지 소트 트리 + 세그먼트 트리 정해는 세그먼트 트리를 응용한 머지 소트 트리로 보인다. 내 경우 : 펜윅 트리 머지 소트 트리를 펜윅 트리로 적용시켜서도 풀 수 있다. 매개 변수 탐색 (parametric search) 이분 탐색의 응용 방법인 매개 변수 탐색이 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 일반적으로는 대부분 세그먼트 트리에 각 노드를.. 2022. 9. 17.
[자바] 백준 11377 - 열혈강호 3 (java) 문제 : boj11377 필요 알고리즘 개념 이분매칭 네트워크 플로우에서 이분 그래프일 시 사용 가능한 이분매칭 알고리즘을 통해 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 N명의 직원이 M개의 일을 선택하는 것만 생각하자. 그럼 기본적인 형태의 이분매칭 알고리즘을 적용해서 풀 수 있다. 여기서 문제가 되는건 N명 중 K명은 일을 최대 2개할 수 있다는 점인데, 사실 약간의 아이디어만 추가하면 똑같다. .. 2022. 9. 17.
[자바] 백준 3197 - 백조의 호수 (java) 문제 : boj3197 필요 알고리즘 개념 너비 우선 탐색 (bfs) 만날 수 있는 시간을 구해야 하므로 너비 우선 탐색으로 탐색하는 것이 적합하다. 분리 집합 (disjoint set) 분리 집합 알고리즘 (유니온 파인드)를 사용해 두 백조가 서로 만날 수 있는 구한다면 매번 백조가 만날 수 있는지 dfs 등을 통해 확인하지 않아도 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 혹시 BFS에 대해 잘 모른다면 이 글.. 2022. 9. 17.
[자바] 백준 14572 - 스터디 그룹 (java) 문제 : boj14572 필요 알고리즘 개념 그리디 풀이를 보면 왜 그리디인지 알 수 있다! 투 포인터 (두 포인터) 이 문제의 경우 그리디 규칙을 적용시킬 때 투 포인터로 적용하는게 편하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 효율성 E를 구할 때 필요한 요소들을 하나씩 살펴보자. 1. 그룹 내의 학생들이 아는 모든 알고리즘의 수 -> 학생 수가 늘어나면 항상 동일하거나 늘어난다. 2. 그룹 내의 모든 학생들이 .. 2022. 9. 17.
[자바] 백준 16978 - 수열과 쿼리 22 (java) 문제 : boj16978 필요 알고리즘 개념 오프라인 쿼리 온라인 쿼리로 풀려면 어려운 문제지만, 오프라인 쿼리 아이디어가 떠올랐다면 훨씬 쉬워진다. 세그먼트 트리 또는 펜윅 트리 point update range query 문제로 세그먼트 혹은 펜윅 트리를 사용해 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 point update와 range query가 존재하는 문제인데, 잘 생각해보면 update와 qu.. 2022. 9. 17.
[자바] 백준 2873 - 롤러코스터 (java) 문제 : boj2873 필요 알고리즘 개념 구성적, 그리디 정규화된 방식 없이 이 문제만을 위한 규칙이 필요한 구성적 문제이다. 또한 그리디를 적용해 해당 규칙을 정할 수 있긴하다(?). 구현 보통 플래급에서 '구현'이 태그로 있다는건 구현이 엄청 어렵다는 뜻이다 ㅋㅋ ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 사실 규칙자체는 여러 케이스에 대해 마구 그려보면서 머리로 생각해보면 어렵지 않게 규칙을 찾을 수 있다. 문제는.. 2022. 9. 17.
[자바] 백준 3683 - 고양이와 개 (java) 문제 : boj3683 필요 알고리즘 개념 이분 매칭 이분 매칭으로 풀 수 있긴 한데, 아이디어 떠올리기가 좀 많이 어려운 편인거같다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 아이디어 생각하기도 어려웠고, 이분 매칭으로 처리하려고 해도 모델링이 상당히 어려운 문제였다 ㅠ. 이분 매칭에서 좌측에 고양이를 좋아하는 사람, 우측에 개를 좋아하는 사람을 둔다. 그리고 좌측에서 우측으로 고양이를 좋아하는 사람이 싫어하는 개를 .. 2022. 9. 17.

티스토리툴바