알고리즘 - Baekjoon

[백준] 15663번 : N과 M(9) Silver2(실버2) - JAVA[자바]

[Silver II] N과 M (9) - 15663 문제 링크 성능 요약 메모리: 31336 KB, 시간: 364 ms 분류 백트래킹 제출 일자 2023년 10월 24일 10:49:21 문제 설명 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해..

[백준] 1781번 : 컵라면 Gold2(골드2) - JAVA[자바]

[Gold II] 컵라면 - 1781 문제 링크 성능 요약 메모리: 76172 KB, 시간: 868 ms 분류 자료 구조, 그리디 알고리즘, 우선순위 큐 제출 일자 2023년 10월 23일 12:40:35 문제 설명 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다. 문제 번호 1 2 3 4 5 6 7 데드라인 1 1 3 3 2 2 6 컵라면 수 6 7 2 1 4 5 1 위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다. 문제는 동호가 받을 ..

[백준] 1655번 : 가운데를 말해요 Gold 2(골드 2) - JAVA[자바]

[Gold II] 가운데를 말해요 - 1655 문제 링크 성능 요약 메모리: 34432 KB, 시간: 528 ms 분류 자료 구조, 우선순위 큐 제출 일자 2023년 10월 23일 10:50:07 문제 설명 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램..

[백준] 13975번 : 파일 합치기3 Gold4(골드 4) - JAVA[자바]

[Gold IV] 파일 합치기 3 - 13975 문제 링크 성능 요약 메모리: 268972 KB, 시간: 3144 ms 분류 자료 구조, 그리디 알고리즘, 우선순위 큐 제출 일자 2023년 10월 23일 09:42:22 문제 설명 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가..

[백준] 1715번 : 카드 정렬하기 Gold 4(골드5) - JAVA[자바]

[Gold IV] 카드 정렬하기 - 1715 문제 링크 성능 요약 메모리: 25836 KB, 시간: 364 ms 분류 자료 구조, 그리디 알고리즘, 우선순위 큐 제출 일자 2023년 10월 23일 09:23:09 문제 설명 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합..

[백준] 2075번 : N번째 큰 수 Silver2(실버2) - JAVA[자바]

[Silver II] N번째 큰 수 - 2075 문제 링크 성능 요약 메모리: 276968 KB, 시간: 896 ms 분류 자료 구조, 우선순위 큐, 정렬 제출 일자 2023년 10월 23일 00:42:33 문제 설명 N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자. 12 7 9 15 5 13 8 11 19 6 21 10 26 31 16 48 14 28 35 25 52 20 32 41 49 이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다. 입력 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가..

[백준] 11279번 : 최대 힙 Silver 2(실버 2) - JAVA[자바]

[Silver II] 최대 힙 - 11279 문제 링크 성능 요약 메모리: 28168 KB, 시간: 364 ms 분류 자료 구조, 우선순위 큐 제출 일자 2023년 10월 23일 00:35:56 문제 설명 널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 ..

[백준] 1927번 : 최소 힙 Silver 2[실버 2] - JAVA[자바]

[Silver II] 최소 힙 - 1927 문제 링크 성능 요약 메모리: 27112 KB, 시간: 364 ms 분류 자료 구조, 우선순위 큐 제출 일자 2023년 10월 23일 00:31:08 문제 설명 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은..