java
[백준] 11399번 : ATM - JAVA [자바]
[백준] 11399번 : ATM - JAVA [자바]
2020.10.07www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 이 또한 활동 선택 문제(Activity Selection Problem) 문제로 볼 수 있다. 조금만 이해하면 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 앞서 포스팅 했던 문제인 회의실배정과 유사한 문제다. 문제를 잘 이해해야 하는 것이 '종료 시간'이 아니라 '대기 시간의 총합'을 구하는 문제라는 점. 즉, 어떻게 배치하던 총 걸리는 같더라도, 한 사람이 대기하는 시간은 달라질 수 있다. 상식적으로 대기시간을 줄이려면 앞 사..
자바 [JAVA] - List Interface (리스트 인터페이스)
자바 [JAVA] - List Interface (리스트 인터페이스)
2020.10.07자료구조 관련 목록 링크 펼치기 더보기 0. 자바 컬렉션 프레임워크 (Java Collections Framework) 1. 리스트 인터페이스 (List Interface) - [현재 페이지] 2. 어레이리스트 (ArrayList) 3. 단일 연결리스트 (Singly LinkedList) 4. 이중 연결리스트 (Doubly LinkedList) 5. 스택 인터페이스 (Stack Interface) 6. 스택 (Stack) 7. 큐 인터페이스 (Queue Interface) 8. 배열 큐 (Array Queue) 9. 연결리스트 큐 (LinkedList Queue) 10. 배열 덱 (Array Deque) 11. 연결리스트 덱 (LinkedList Deque) 12. 힙 (Heap) 13. 우선순위 큐 (..
[백준] 1931번 : 회의실배정 - JAVA [자바]
[백준] 1931번 : 회의실배정 - JAVA [자바]
2020.10.05www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 그리디 알고리즘의 대표적인 문제 중 하나다. 알고리즘 [접근 방법] 위와 같이 시간표를 최대한 많이 배정하거나 선택하는 문제를 '활동 선택 문제(Activity Selection problem)'라고 한다. 간단하게 설명하자면, 한 사람이 하나의 활동에 대해서만 작업할 수 있을 때 최대한 많은 활동을 할 수 있는 수를 선택하는 문제다. 위에서는 각 회의가 겹치지 않게 최대한 많은 회의를 배정하는 것으로 나와있다. 이러한 문제들의 특징은 '한 사람이 하나의 활동에 대해서만 작업할 수 있다'라는 점이다. 즉, 하나의 활동을 완..
Bogo sort (보고 정렬) 알고리즘
Bogo sort (보고 정렬) 알고리즘
2020.09.29유튜브를 보다가 우연히 필자의 눈에 들어온 영상 하나가 있었다. 정렬을 비교해주는 영상이었는데, Bogo sort 부분 영상에서 음.. 이거 정렬되고 있는거 맞아? 싶었다. 더보기 youtu.be/DaPJkYo2quc 찾아보니 정렬방법이 매우 충격적(?)이라 여러분들에게 같이 이 충격적인 정렬방법을 공유하고자 한다. (정렬 알고리즘이라고 해서 그리 어려운 내용은 아니고 장난스러운 내용에 가까우니 부담없이 봐도 된다.) 정렬 메커니즘은 아주 쉽다. '운' 무슨 말인가 싶을 것이다. 좀 쉽게 예로들어보자면 이미 뒤섞여 있는 카드뭉치가 있다고 가정하자. 그 것을 여러분은 무작위로 셔플하여 정렬을 한다. ??? 정렬이 되긴 합니까? 라고 한다면 되긴 된다만 언제 될지는 보장 못한다고밖에 말을 해줄 수가 없다. ..
[백준] 11047번 : 동전 0 - JAVA [자바]
[백준] 11047번 : 동전 0 - JAVA [자바]
2020.09.25www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 그리디 알고리즘의 첫 문제다. 사실 그리디 알고리즘이 무엇인지는 몰라도 쉽게 풀 수 있는 문제지만, 일단 그리디 알고리즘에 대해 알고가도록 하자. 알고리즘 [접근 방법] 1. 그리디 알고리즘 (Greedy Algorithm) 먼저 그리디 알고리즘이 뭔지 알아보자. 그리디 알고리즘이란, 말 그대로 greedy, 즉 탐욕 알고리즘이다. 왜 탐욕 ..
[백준] 12865번 : 평범한 배낭 - JAVA [자바]
[백준] 12865번 : 평범한 배낭 - JAVA [자바]
2020.09.17www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 알고리즘 [접근 방법] 이 문제는 배낭 문제(knapsack)로 매우 유명한 문제다. 문제 설명처럼 배낭에 넣을 수 있는 최댓값이 정해지고 해당 한도 물건을 넣어 가치의 합이 최대가 되도록 고르는 방법을 찾는 것이다. 즉, 조합 최적화 문제다. 배낭문제, 일명 냅색 알고리즘은 크게 두 가지 문제로 분류 될 수 있는데, 짐을 쪼갤 수 있는 경..
[백준] 1912번 : 연속합 - JAVA [자바]
[백준] 1912번 : 연속합 - JAVA [자바]
2020.09.10www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 이 문제는 너무 쉬운 문제라.. 메모이제이션하면서 구간만 잘 찾아내면 끝인 문제다. 알고리즘 [접근 방법] 꽤나 쉬운 문제임에도 정답 비율이 꽤나 낮은 문제다. 아마 '연속 되는 수를 선택'해야 한다는 조건을 놓치거나 음수를 빼버리는 경우? 이렇게 접근해서 틀린 분들이 많지 않을까 싶다. 문제 예제들을 그대로 적용해보면 이렇다. 첫 번째 예제는 아래와 같다. (배열로 표현함) 여기서 연속된 수를 선택하여 뽑아내면 다..
[백준] 9251번 : LCS - JAVA [자바]
[백준] 9251번 : LCS - JAVA [자바]
2020.09.08www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS의 대표적인 문제다. 알고리즘 [접근 방법] 우리가 그동안 LIS, LDS, 바이토닉 부분수열까지 풀어봤다. 이 번에는 LCS인데, LCS의 정의 자체는 매우 간단하다. 위키피디아에서 보면 매우 잘 정리되어있으니 읽어보시는 것도 좋을 것 같다. ko.wikipedia.org/wiki/최장_공통_부분_수열 최장 공통 부분 수열 - 위키백과, 우리 모두의 백과..
[백준] 2565번 : 전깃줄 - JAVA [자바]
[백준] 2565번 : 전깃줄 - JAVA [자바]
2020.09.04www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 역발상을 하면 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 문제 접근 방식부터 알아보자. 먼저 문제에서는 서로 교차되지 않도록 하기 위해 철거되어야 할 전선의 최소 개수를 구하는 것이다. 하지만 그렇게 구하기에는 교차 여부를 확인해야 하기에 불편하다. 그렇다면 역으로 생각해보자. 철거되어야 할 전선의 최소 개수라 하면, 거꾸로 전체 전선의 개수에서 최대한 겹치지 않게 설치 가능한 개수를 구하여 빼면, 즉 (..
[백준] 11054번 : 가장 긴 바이토닉 부분 수열 - JAVA [자바]
[백준] 11054번 : 가장 긴 바이토닉 부분 수열 - JAVA [자바]
2020.09.04www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 이전 문제인 가장 긴 증가하는 부분 수열을 풀어보셨다면 매우 쉽게 풀 수 있는 문제다. 이 문제를 풀기 전에 앞서 아래 포스팅을 보고 오는 걸 추천드린다. st-lab.tistory.com/137 [백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바] www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하..