백준
-
BOJ 2565번 전깃줄 문제 자바(java) 풀이 랭크 : 실버1 백준 2565번 전깃줄 문제 정리 교차하는 전깃줄을 없애서 전깃줄이 교차하지 않도록 하려고 한다. 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄 최소 개수 구하기 전깃줄의 개수는 최대 100개 이다. 문제 풀이 전깃줄의 상태를 왼쪽 기준 오름차순으로 나열하면 아래와 같습니다. A 전봇대: 1 2 3 4 6 7 9 10 B 전봇대: 8 2 9 1 4 6 7 10 어떻게 하면 제일 조금 자를 수 있을까 생각해보면 B 전봇대의 1,2,3번째 전깃줄을 자르면 3개로 제일 작게 자르는 경우가 됩니다. 왜나하면 왼쪽수는 이미 증가 상태이기 때문에 오른쪽도 오름차순 이면 전깃줄이 엉키지 않습니다. 즉 최장 증가 수열(Lon..
[BOJ] 백준 2565번 전깃줄 자바(java) 코드 :: LIS(Longest Increasing Sequence) 찾기BOJ 2565번 전깃줄 문제 자바(java) 풀이 랭크 : 실버1 백준 2565번 전깃줄 문제 정리 교차하는 전깃줄을 없애서 전깃줄이 교차하지 않도록 하려고 한다. 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄 최소 개수 구하기 전깃줄의 개수는 최대 100개 이다. 문제 풀이 전깃줄의 상태를 왼쪽 기준 오름차순으로 나열하면 아래와 같습니다. A 전봇대: 1 2 3 4 6 7 9 10 B 전봇대: 8 2 9 1 4 6 7 10 어떻게 하면 제일 조금 자를 수 있을까 생각해보면 B 전봇대의 1,2,3번째 전깃줄을 자르면 3개로 제일 작게 자르는 경우가 됩니다. 왜나하면 왼쪽수는 이미 증가 상태이기 때문에 오른쪽도 오름차순 이면 전깃줄이 엉키지 않습니다. 즉 최장 증가 수열(Lon..
2020.03.24 -
BOJ 5430번 AC 문제 자바(java) 풀이 랭크 : 실버2 백준 5430번 AC 문제 정리 AC에는 정수 배열을 위한 두 가지 함수가 있다. R(뒤집기) : 배열에 있는 숫자 순서를 뒤집는다. D(버리기) : 첫 번째 숫자를 버린다. RDD 처럼 함수를 바로 이어서 사용할 수 있다. 한 번 뒤집은 다음 두개의 숫자를 버린다. 함수 실행 후, 최종 결과를 구하여라 문제 풀이 수를 실제로 뒤집고 반복한다면 시간초과가 나게 될것입니다. 그러므로 deque를 이용하여 앞 뒤에서 숫자를 지워줍니다. 파싱하는 것이 중요합니다. 숫자는 한자리수가 아니라 최대 100,000임을 인지해야 합니다. 이것 때문에 런타임 에러를 많이 봤습니다..ㅠㅠ 배열에 주어진 수가 하나도 없을때 함수에 D가 포함되어 있다면 에러를..
[BOJ] 백준 5430번 AC 자바(java) 풀이BOJ 5430번 AC 문제 자바(java) 풀이 랭크 : 실버2 백준 5430번 AC 문제 정리 AC에는 정수 배열을 위한 두 가지 함수가 있다. R(뒤집기) : 배열에 있는 숫자 순서를 뒤집는다. D(버리기) : 첫 번째 숫자를 버린다. RDD 처럼 함수를 바로 이어서 사용할 수 있다. 한 번 뒤집은 다음 두개의 숫자를 버린다. 함수 실행 후, 최종 결과를 구하여라 문제 풀이 수를 실제로 뒤집고 반복한다면 시간초과가 나게 될것입니다. 그러므로 deque를 이용하여 앞 뒤에서 숫자를 지워줍니다. 파싱하는 것이 중요합니다. 숫자는 한자리수가 아니라 최대 100,000임을 인지해야 합니다. 이것 때문에 런타임 에러를 많이 봤습니다..ㅠㅠ 배열에 주어진 수가 하나도 없을때 함수에 D가 포함되어 있다면 에러를..
2020.03.23 -
BOJ 1874번 스택 수열 문제 자바(java) 풀이 랭크 : 실버3 풀이시간: 50분 메모리: 29832 KB 시간: 316 ms 백준 1874번 스택 수열 문제 정리 1부터 n까지의 수를 스택에 넣었다가 뽑으면서 주어진 수열을 만들어야 한다. 만들 수 있다면 push와 pop 연산 순서를 출력하고 만들 수 없다면 "NO"를 출력해라. 문제 풀이 처음에 문제 이해가 잘 안되서 헤맸었습니다. 예제 1번은 다음과 같이 동작합니다. 1. 1을 넣는다. (1) 2. 2를 넣는다. (1 2) 3. 3을 넣는다. (1 2 3) 4. 4를 넣는다. (1 2 3 4) 5. 수열의 첫번째 수 4가 stack의 맨 위의 수가 같으므로 pop한다. (1 2 3) 6. 다음 수 3이 stack의 맨 위의 수와 같으므로 p..
[BOJ] 백준 1874번 스택 수열 자바(java) 풀이BOJ 1874번 스택 수열 문제 자바(java) 풀이 랭크 : 실버3 풀이시간: 50분 메모리: 29832 KB 시간: 316 ms 백준 1874번 스택 수열 문제 정리 1부터 n까지의 수를 스택에 넣었다가 뽑으면서 주어진 수열을 만들어야 한다. 만들 수 있다면 push와 pop 연산 순서를 출력하고 만들 수 없다면 "NO"를 출력해라. 문제 풀이 처음에 문제 이해가 잘 안되서 헤맸었습니다. 예제 1번은 다음과 같이 동작합니다. 1. 1을 넣는다. (1) 2. 2를 넣는다. (1 2) 3. 3을 넣는다. (1 2 3) 4. 4를 넣는다. (1 2 3 4) 5. 수열의 첫번째 수 4가 stack의 맨 위의 수가 같으므로 pop한다. (1 2 3) 6. 다음 수 3이 stack의 맨 위의 수와 같으므로 p..
2020.03.20 -
BOJ 2517번 달리기 문제 자바(java) 풀이 랭크 : 플레티넘5 백준 2517번 달리기 문제 정리 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 앞지르는 것은 불가능하다. 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있다면 남은 거리 동안 앞지르는 것이 가능하다. 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다. 각 선수의 평소 실력이 주어진다.(클 수록 실력 上) 선수의 평소 실력이 앞에서 부터 주어질때 각 선수의 최선의 등수를 계산하여라. 문제 풀이 자신보다 앞에 있는 사람중 실력이 더 낮은 사람들의 수를 구하면 됩니다. 다음 두 가지 방법으로 풀 수 있습니다. merge sort 풀이 선수들의 실력과 index를 Num 객체아 담아 저장합니다. merg..
[BOJ] 백준 2517번 달리기 자바(java) 풀이 (merge sort 풀이, segment tree 풀이)BOJ 2517번 달리기 문제 자바(java) 풀이 랭크 : 플레티넘5 백준 2517번 달리기 문제 정리 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 앞지르는 것은 불가능하다. 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있다면 남은 거리 동안 앞지르는 것이 가능하다. 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다. 각 선수의 평소 실력이 주어진다.(클 수록 실력 上) 선수의 평소 실력이 앞에서 부터 주어질때 각 선수의 최선의 등수를 계산하여라. 문제 풀이 자신보다 앞에 있는 사람중 실력이 더 낮은 사람들의 수를 구하면 됩니다. 다음 두 가지 방법으로 풀 수 있습니다. merge sort 풀이 선수들의 실력과 index를 Num 객체아 담아 저장합니다. merg..
2020.03.19 -
BOJ 1158번 요세푸스 문제1 자바(java) 풀이 랭크 : 실버5 풀이시간: 5분 백준 1158번 요세푸스 문제1 문제 정리 1~N번까지 N명의 사람이 원 모양으로 앉아있다. k가 주어질때 k번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원에서 2번을 반복한다. N명의 사람이 모두 제거될 때까지 계속된다. 사람들이 제거 되는 순서를 출력해라. 문제 풀이 이 문제는 요세푸스 문제0번과 똑같이 제출해도 통과할 수 있습니다. 즉 naive하게 문제에서 주어진대로 구현하면 통과할 수 있습니다. 하지만 이 문제는 queue를 이용하여 작성해보았습니다. queue에서 뺄 필요 없이 ArrayList를 이용하면 뺏다 넣었다 하지 않기 때문에 더 빠르게 가능합니다. 1~N까지 queue에 모두..
[BOJ] 백준 1158번 요세푸스 문제 자바(java) 풀이(큐, 리스트)BOJ 1158번 요세푸스 문제1 자바(java) 풀이 랭크 : 실버5 풀이시간: 5분 백준 1158번 요세푸스 문제1 문제 정리 1~N번까지 N명의 사람이 원 모양으로 앉아있다. k가 주어질때 k번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원에서 2번을 반복한다. N명의 사람이 모두 제거될 때까지 계속된다. 사람들이 제거 되는 순서를 출력해라. 문제 풀이 이 문제는 요세푸스 문제0번과 똑같이 제출해도 통과할 수 있습니다. 즉 naive하게 문제에서 주어진대로 구현하면 통과할 수 있습니다. 하지만 이 문제는 queue를 이용하여 작성해보았습니다. queue에서 뺄 필요 없이 ArrayList를 이용하면 뺏다 넣었다 하지 않기 때문에 더 빠르게 가능합니다. 1~N까지 queue에 모두..
2020.03.16 -
BOJ 10815번 숫자 카드 문제 자바(java) 풀이 랭크 : 실버4 풀이시간: 15분 메모리: 159520 KB 시간: 1772 ms 백준 10815번 숫자 카드 문제 정리 숫자 카드에는 정수 하나가 적혀있다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 카드를 상근이가 가지고 있는지 아닌지 구하여라. N은 최대 500,000이고 숫자 카드에 적혀 있는 숫자는 최소 -천만, 최대 +천만 이다. M의 최대는 N과 같고 구해야할 숫자도 숫자 카드에 적혀있는 숫자 범위와 같다. 문제 풀이 m개에 대해서 n번 탐색하게 되면 최대 2천5백억번을 탐색해야 합니다. 즉 단순하 탐색으로는 찾을 수 없습니다. 딱 생각난 풀이는 이진탐색이었습니다. 이진탐색을 구현하여 찾아야 ..
[BOJ] 10815번 숫자카드 자바(java) 풀이 (이진탐색)BOJ 10815번 숫자 카드 문제 자바(java) 풀이 랭크 : 실버4 풀이시간: 15분 메모리: 159520 KB 시간: 1772 ms 백준 10815번 숫자 카드 문제 정리 숫자 카드에는 정수 하나가 적혀있다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 카드를 상근이가 가지고 있는지 아닌지 구하여라. N은 최대 500,000이고 숫자 카드에 적혀 있는 숫자는 최소 -천만, 최대 +천만 이다. M의 최대는 N과 같고 구해야할 숫자도 숫자 카드에 적혀있는 숫자 범위와 같다. 문제 풀이 m개에 대해서 n번 탐색하게 되면 최대 2천5백억번을 탐색해야 합니다. 즉 단순하 탐색으로는 찾을 수 없습니다. 딱 생각난 풀이는 이진탐색이었습니다. 이진탐색을 구현하여 찾아야 ..
2020.03.16