본문 바로가기

Algorithm65

[LeetCode] Minimize the Maximum Difference of Pairs 자바 문제 (이분탐색) Minimize the Maximum Difference of Pairs - LeetCode Can you solve this real interview question? Minimize the Maximum Difference of Pairs - You are given a 0-indexed integer array nums and an integer p. Find p pairs of indices of nums such that the maximum difference amongst all the pairs is minimized. Also, leetcode.com 문제 풀이 문제 해석 자체도 어려워서 많이 헤매었다. 구하고자 하는 문제를 정리해보자면 1. p개의 쌍 추출 ← 이때 .. 2023. 9. 8.
[프로그래머스] 행렬 테두리 회전하기 자바 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 처음에는 행렬이 1부터 순서대로 시작하니까 굳이 행렬을 계속 갱신하지 않고 풀이할 수 있지 않을까 생각했는데 그냥 직접 행렬을 rotation해주는게 답인 것 같아서 로테이션 함수를 따로 만들어주었다. ✔️ rotation함수 1. 행렬의 각 꼭짓점 부분을 t1, t2, t3, t4 변수를 이용하여 처음에 보관 2. temp변수를 이용하여 기존의 행렬값 보관 3. before변수를 이용해 temp값을 한 번 더 보관하여 다음 수를 갱신할 수 있도록 함 4. 이 때 flag변수로 반복문의 첫번째.. 2022. 10. 5.
[백준] 1725번 히스토그램 자바 문제 (스택) 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 문제 풀이 문제 풀이에 대한 논리가 많이 어려웠다. 세그먼트 트리를 이용해서도 많이 푸는 방식인 것 같은데 나는 세그먼트 트리에 대해서 잘 몰라서 만만한(?) 스택으로 풀기로 했다. 다른 블로그 글들에 그림 포함해서 설명이 잘 나와있어서 알고리즘은 내가 보기 편한대로 다시 정리해보자면, 우선 히스토그램 순서대로 반복문을 실행하면서 높이가 증가하다가 감소하는 부분을 유의해야 한다. 왜냐하면 높이가 감소하는 순간 바로 그 .. 2022. 6. 29.
[백준] 2110번 공유기 설치 자바 문제 (이분 탐색) 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 풀이 이분 탐색 알고리즘이다. 이분 탐색 문제를 몇 개 풀면서 느낀 건데 약간 정답의 범위가 정수의 형태로 적당히(?) 정해지는 경우 사용하는 것 같다. 그리고 이분 탐색을 사용할 때, 이분 탐색을 코드를 작성하는 것보다 해당 값에 대해 성립하는지 확인하는 코드짜기가 더 어렵다. 이번 공유기 설치 문제도 이분 탐색으로 정답을 추려가면서 이 정답에 성립하는지를 처리하는 로직이 까다로웠다... 2022. 6. 22.
[백준] 2805번 나무 자르기 자바 문제 (이진 탐색) 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 풀이 이진 탐색 알고리즘은 알고 있었지만 이 문제를 통해 이와 비슷한 새로운 알고리즘을 알게되었다. ✔️이진 탐색 : 데이터가 정렬되어 있는 배열에서 특정값을 찾아내는 알고리즘 1) 중간에 있는 임의의 값을 선택하여 찾고자 하는 수 X와 비교한다 1-1) X가 임의값보다 작으면, 임의값 기준 왼쪽 데이터들을 대상으로 다시 탐색 1-2) X가 임의값보다 크면, 임의값 기준 오른쪽 데이터들을 대상으로 .. 2022. 6. 19.
[백준] 1202번 보석 도둑 자바 문제 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 풀이 처음에는 보석을 기준으로 ArrayList와 PriorityQueue를 이용해서 가장 비싼 것부터 제거해나갔는데 시간초과였다. 구글링을 해보니 보석을 기준으로 하는게 아니라 가방을 기준으로 해야 했고, 또 우선순위큐 하나로 구현이 가능했다. ✔️알고리즘 1. 보석을 무게가 가벼운 순으로 정렬을 한다 (오름차순) 2. 가방을 가벼운 순으로 정렬을 한다 (오름차순) 3. 모든 가방에 대하여.. 2022. 6. 17.

티스토리툴바