본문 바로가기

분류 전체보기1046

백준 1806 자바 - 부분합 (BOJ 1806 JAVA) 문제 : boj1806 1. 틀린 방법 ※ 제가 틀린 방법에 대해 써둔 것으로, 해설만 보고 싶다면 2번부터 보시면 됩니다. 덱에 모든 값들을 담으면서 그 합을 따로 계산한다. 그럼 일단 그 합은 최대치로 나올 수 있는 합이 될 것이다. 그 합이 S보다 작다면 0을 출력하고, 그렇지 않다면 합이 S보다 작아질 때 까지 덱의 시작부분과 끝부분을 각각 peek 해봐서 둘 중 작은 값을 덱에서 빼버린다. 이렇게 하면 그리디하게 답을 구할수 있을줄 알았다. 예를들어 S가 5일 때 다음과 같이 수행한다. 이렇게 짠 코드는 다음과 같다. ※ 틀린 코드임 ... int n = nextInt(); int s = nextInt(); int sum = 0; Deque dq = new ArrayDeque(); for (in.. 2022. 1. 23.
백준 1450 자바 - 냅색문제 (BOJ 1450 JAVA) 문제 : boj1450 1. 문제 접근 딱히 냅색과 관련없어 보이는 문제이다. N이 작아 쉽게 풀 수 있을 줄 알았다. 근데 당연하게도 모든 경우를 보면 O(2^30) 이므로 통과할 수 없다. 그렇다고 냅색처럼 DP로 풀자니 1~10^9 까지 확인해야 할 것 같으니 역시 통과할 수 없다. bit DP쪽으로도 딱히 떠오르지 않았다. 그래서 이 문제에서 적용한 방식처럼 반반을 나눠서 생각해보기로 했다. 1.1 최대 30개의 데이터를 대충 반반으로 15개씩 나눈다(사실 한쪽을 25개, 한쪽을 5개로 해도 상관없다.). 이걸 A와 B라 하겠다. 1.2 A에 대해 나올 수 있는 모든 무게 합의 경우의 수 확인하고 어딘가에 저장한다. 이 경우 최대 15번에 대해 해당 수를 포함하거나 포함하지 않거나의 2가지 경우이.. 2022. 1. 22.
백준 2252 자바 - 줄 세우기 (BOJ 2252 JAVA) 문제 : boj2252 1. 그래프로 생각해보자. 이런식으로 A에서 B로 향한다던지, A와 B가 연관되었다든지 하면 일단 그래프로 생각해보는게 이해하기 편하다. 이 문제에서는 'A가 학생 B의 앞에 서야 한다'에 대해 A에서 B로의 간선을 긋는 방향 그래프로 생각해보자. 그럼 다음과 같은 경우를 보자. 5 3 1 2 2 3 4 5 위의 경우를 그래프로 나타내보면 다음과 같다. 위와 같은 경우는 간단하다. 이 문제의 경우 1->2->3을 먼저 가던지, 4->5를 먼저 가던지, 심지어 1->4->2->3->5 이렇게 가던지 상관없다. 서로 섞여있더라도 아무튼 모든 경우에서 A가 B보다 먼저 나오기만 하면 된다. 그렇다면 M개의 A, B를 입력받으면서, A에 나타났으면서 B에는 등장하지 않은 1과 4어디에서든.. 2022. 1. 21.
백준 2467 자바 - 용액 (BOJ 2467 JAVA) 문제 : boj2467 1. 당연히 모든 쌍을 확인해보면 O(N^2)이 걸릴 것이므로 통과가 불가하다. 이 문제는 투 포인터 알고리즘으로 풀 수 있는 기본형 문제이다. 또는 안풀어보긴 했으나 이분탐색으로도 문제없이 풀 수 있을 것 같다(N개를 TreeSet에 넣어둔 후 N개의 값을 순회하며 해당 값에 -1을 곱한 값에 대해 TreeSet에서 ceilling과 floor를 확인해 그 중 작은 수를 택하면 될 듯함). 2. 이미 정렬되어 들어온 데이터 이므로 정렬과정 필요 없이 첫번째 값을 s로 가르키고, 맨 뒤의 값을 e로 가르켜보자. 이제 s와 e가 가르키는 값을 합쳐가며 이 중 0과 가장 가까운 값을 찾으면 된다. s와 e를 변경하는 규칙은 다음과 같다. arr[s]+arr[e] == 0 -> 바로 출.. 2022. 1. 20.
백준 13547 자바 - 수열과 쿼리 5 (BOJ 13547 JAVA) 문제 : boj13547 문제에 비해 필요한 아이디어 및 구현과정은 상당히 복잡한 문제이므로 간단한 부분부터 차례대로 생각해보자. 1. 우선은 단건의 쿼리를 해결할 방법을 생각해보자. [Ai, Aj]에 존재하는 서로다른 수의 개수를 알 수 있어야 한다. 여러 방법이 있겠으나, 각 값을 표현할 메모리가 충분하다면 값의 최대 크기에 해당하는 배열을 만들어 해당 수가 나왔는지 체크하는 방법이 가장 효율적이다. 이 문제에서는 N개의 값 각각의 최대값은 1,000,000이므로 100만개짜리 boolean 배열만 있으면 된다. 100만개짜리 배열 arr이 있고, cnt라는 변수를 뒀다고 해보자. 각 쿼리에서 i와 j를 입력받았을 때 Ai부터 Aj까지 순회하며 배열에 체크한다. 이미 체크되어 있던게 아니라면 cnt를.. 2022. 1. 19.
백준 9753 자바 - 짝 곱 (BOJ 9753 JAVA) 문제 : boj9753 100000일 때 100001이 답이란걸 문제 예시에서 보여줬으므로 사실 100000이하의 소수 곱에 대해서만 신경쓰면 된다. 그리고 어차피 가장 작은 소수가 2 이므로 50000까지만 보면 된다. 따라서 5만 이하의 모든 소수를 우선 에라토스테네서의 체로 구한다. 그리고 소수의 곱을 모든 쌍을 보면서 모두 구한다. 이 때 10만이 넘어간다면 제외해도 된다. 구한 값은 어차피 10만까지만 알면 되므로 배열에 넣어도 되고, 내 경우엔 더 큰 수를 빨리 구해보려고 TreeSet에 넣었다. 이후 하나씩 입력받으면서 TreeSet의 ceiling을 출력하면 된다. '2'의 과정을 배열에 했다면 입력받은 값 이상을 순회하며 가장 작은 소수를 출력하면 된다. 코드 : github import.. 2022. 1. 18.
백준 10373 자바 - Buffcraft (BOJ 10373 JAVA) 문제 : boj10373 1. 문제 정의 상당히 문제가 불친절하다. 예제라도 의미 있을 예제를 들어주면 좋을텐데 ㅡㅡ; 상당히 별로인 문제이다. 1.1 'The following line must contain n different numbers', 'The last line of the output must contain m different numbers' 에 따라 출력을 해줘야 하는데, 그럼 following line이 0이라 출력할 게 없으면 줄을 띄워야 되나 말아야 하나라는 문제점이 있다(second, third line이라고 하던지.. 저렇게 하면 사실 following line이 last line이 되기도 하므로 애매하다.). 원래 문제대로라면 줄을 띄워야 맞지만(해당 대회 문제 채점 데이터.. 2022. 1. 17.
백준 8807 자바 - Przedziały (BOJ 8807 JAVA) 문제 : boj8807 1. 다음과 같은 입력을 생각해보자. 1 5 1 2 2 2 3 5 7 8 10 10 이 문제의 경우 만약 모든 범위를 한 선에 겹쳐그릴 수 있다면 쉽게 답을 구할 수 있을 것이다. 그럼 어떻게 각 범위를 합칠 수 있을지 생각해보면 된다. 우선 가장 간단한 방식으로, 모든 범위에 해당하는 배열을 만들고 입력을 받으며 범위를 채운 후, 마지막에 모든 범위에 대해 확인해서 개수를 세는걸 생각할 수 있다. 다만 이 문제의 경우 이렇게되면 모든 범위가 -10억~+10억이 되므로 모든 범위 확인만해도 대략 20초정도 걸린다. 2. 다른 방법을 생각해보자. 사실 각 A,B에 대해 범위를 순회만 해도 최대 20억번 해야하므로 시간초과가 확실하다. 따라서 아예 다른 방식으로 생각해봐야 한다. OR.. 2022. 1. 16.
백준 3518 자바 - 공백왕 빈-칸 (BOJ 3518 JAVA) 문제 : boj3518 문제는 참 직관적이고 간단한 구현문제인데, 생각보다 꾸현이 까다롭긴 하다. 나온 설명대로 문자열 파싱만 잘 하면 되서 딱히 알고리즘적으로 설명할 건 없다. 주의점은 좀 있다. 첫째로 다음과 같은 경우를 보자. abc def zzz ggg 이미 문제에서 제시된 방식되로 잘 배치되어 있지만, '사전순으로 가장 앞서는 것'을 출력해야 하므로 공백을 1칸으로 줄여야 한다. abc def zzz ggg 두번째로 각 출력문의 마지막에 추가 공백이 있으면 안된다. 딱 출력해야 되는 문장에서 추가 공백 없이 그것만 출력해야 된다. 그 이외에는 백준에서 '출력 형식이 잘못되었습니다'이 뜬다. 코드 : github import java.io.BufferedReader; import java.io.I.. 2022. 1. 15.
JS ES6~ES12 에서 추가된 주요 문법들 (모던 리액트 이해에 필요한 ECMA Script ES6~ES12 문법들) 현재 리액트를 공부중이다. 그런데 너무 생소한 문법들이 많았다. 처음엔 리액트만의 문법이겠거니 생각했는데, 찾아보니 자바스크립트에서 ES6 이상에서 추가된 문법들이 대부분이었다. 그래서 모던 리액트 문법을 이해하는데 필요한 ES6~ES12에서 추가된 문법들과, 딱히 리액트와 관련 없더라도 유용해보이는 ES6~ES12 문법을 정리해봤다. 특히 ES6에 새로운 문법들이 많다. Contents [ ES6 (ES2015) ] 1. const, let 1.1 var ES6이전에 사용하던 var는 함수 스코프 변수이다. 그래서 일반적인 다른 언어들과는 동작 방식 자체가 다르다. 보통 함수내에 변수를 선언하고, if나 for, while 등을 사용한다면 일반적으로 별도의 스코프 영역을 가질거라 예상하지만 var로 사.. 2022. 1. 15.

티스토리툴바