기록방

👉 문제링크 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 🔸 문제 분석 🔸 N개의 수로 이루어진 수열을 버블 소트로 정렬했을 때, swap이 총 몇 번 발생하는지 출력한다. 🔸 문제 풀이 🔸 N이 50만까지 가므로 O(nlogn)의 알고리즘을 사용해야 한다. 여기서는 병합 정렬(Merge Sort)을 사용한다. 버블 소트는 1칸씩 이동할 수 있으므로, 정렬 후 바뀐 인덱스의 크기를 모두 더하면 된다. 병합 정렬에서 기존 인덱스보다 앞 인덱스로 옮길 때, 그 크기를 누적해서 출력한다...

👉 문제링크 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 🔸 문제 분석 🔸 N x M 모눈종이에 공기와 치즈가 0, 1 로 주어진다. 외부 공기와 2개 이상 맞닿은 치즈는 녹는다. 치즈가 모두 녹는데 걸리는 시간을 구한다. 🔸 문제 풀이 🔸 치즈 내부의 공기와 외부 공기를 분리해서 생각한다. 가장자리 면은 치즈를 두지 않는다고 문제에서 제한했으므로, (0,0)부터 그래프 탐색으로 인접한 0을 2로 바꾼다. 풀이에선 DFS를 사용했다. 공기와 맞닿은 치즈를 녹여 없앤다. 치즈가 녹은 자리는 공기..

👉 문제링크 🔸 문제 분석 🔸 이진 검색 트리의 전위 순회 결과를 토대로 후위 순회 결과를 출력한다. 🔸 문제 풀이 🔸 전위 순회 결과를 EOF(End Of File : null)가 나올 때까지 입력받는다. 첫 번째 결과는 Root 로 사용한다. 이후 결과는 작으면 왼쪽 자식 노드, 크면 오른쪽 자식 노드로 구분해 재귀 메서드를 호출하고 저장한다. 전위 순회 결과로 만들어진 이진 검색 트리를 후위 순회 방식으로 재탐색하여 결과를 출력한다. 전위 순회와 비슷하지만, 탐색 순서만 변경하면 된다. 🔸 코드 🔸 import java.io.*; public class Main { private static class Node { private final int root; private Node left; priv..

👉 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔸 문제 분석 🔸 비내림차순 수열의 부분 수열 중 합이 k가 되는 가장 짧은 부분 수열의 시작과 끝 인덱스를 반환한다. 같은 길이가 여러개 나오는 경우 먼저 나온 부분 수열을 사용한다. 🔸 문제 풀이 🔸 인덱스를 이동하며 부분 수열의 합을 계산하는 문제이므로, 투포인터로 풀이한다. 두 인덱스 left와 right를 지정하고, k보다 작으면 right + 1, k보다 크다면 left + 1로 이동한다. 인덱스가 변할 때 부분 수열의 합도 변경하며 계산한다. 부분 수열의 합이 k와 같아진다면, 길이가..

👉 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔸 문제 분석 🔸 x축에 평행한 미사일들의 시작과 끝 인덱스가 주어진다. 요격 하기 위해서 미사일들의 범위에 해당하는 곳을 선택해야하며 끝 인덱스에 걸칠 수는 없다. 요격에 필요한 미사일의 최소 수를 구한다. 🔸 문제 풀이 🔸 최소한의 요격 미사일 개수로 최대한 많은 수의 폭격 미사일을 요격해야 하므로 그리디 문제로 볼 수 있다. 포격 미사일의 범위가 겹치는 인덱스를 빠르게 알기 위해 끝 인덱스로 오름차순 정렬한다. 문제에서의 제한 사항으로 실수 좌표도 가능하며 끝 인덱스에 겹치면 안된다. 이전 ..