본문 바로가기

알고리즘/백준118

[백준/자바]11004 K번째 수 구하기 [백준/자바]11004 K번째 수 구하기 📌 문제 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. ⚔ 입력 첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다. 둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109) 📣 출력 A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다. 💎 문제분석하기 이 문제는 퀵정렬로 풀고자 하기에 먼저 퀵정렬에 대한 이해가 필요했다. 따라서 먼저 퀵정렬을 이해하고 이 문제를 풀이하였다. 퀵정렬은 기준값(Pivot)을 정한 뒤 해당 값을 기준으로 작은 값, 큰값을 분류하여 반복함으로써 정렬을 하는 알고리즘이다. 먼저 한 p.. 2022. 11. 7.
[백준/자바] 11399 ATM 인출 시간 계산하기 [백준/자바] 11399 ATM 인출 시간 계산하기 📌 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려.. 2022. 11. 7.
[백준/파이썬] 1377 버블 소트 [백준/파이썬] 1377 버블 소트 📌 문제 버블 소트 알고리즘을 다음과 같이 C++로 작성했다. bool changed = false; for (int i=1; i 2022. 11. 7.
[백준/자바] 2750 수 정렬하기 [백준/자바] 2750 수 정렬하기 📌 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. ⚔ 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 📣 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 💎 문제분석하기 sort() 함수를 이용하면 바로 정렬되는 문제이지만, 버블 정렬을 직접 구현하는 문제 풀이를 해본다. 방식은 간단하다. 하나 하나씩 비교하면 된다. 📜 슈도코드 작성하기 💡 코드 구현하기 import java.util.Scanner; public class Main { public stati.. 2022. 11. 6.
[백준/파이썬] 11286 절댓값 힙 구현하기 [백준/파이썬] 11286 절댓값 힙 구현하기 📌 문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 1. 배열에 정수 x (x ≠ 0)를 넣는다. 2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. ⚔ 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -2.. 2022. 11. 6.

티스토리툴바