본문 바로가기

전체 글1049

백준 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.
백준 17245 자바 - 히스토그램 (BOJ 17245 JAVA) 문제 : boj17245 일단 단순화 시켜서 생각해보기 위해 좌측부터 우측으로 점차 증가하는 형태와 점차 감소하는 형태를 나눠서 생각해봤다. 1. 우선 높이(h)가 같거나 증가하는 경우이다. 이전과 비교해서 값이 같거나 증가하고 있다면, 아직까지는 넓이를 계산하는 것이 의미가 없다. n개를 모두 입력받았거나, 이후 감소하는 구간을 만나기 전까지는 넓이를 계산하지 않고 있다가 맨 마지막 지점에서만 계산해주면 된다. 직관적으로 맨 마지막 지점을 포함한 상태에서 다음과 같이 이전 높이들을 확인하면 될 것임을 예상할 수 있다. 즉, 높이가 동일하거나 증가하는 경우 맨 마지막 지점에서 이전 지점 모두 중 의미가 있는 넓이는 모두 계산할 수 있다. 2. 다음은 높이(h)가 감소하는 경우이다. 이번엔 좌측에서 우측으.. 2022. 1. 13.
백준 4386 자바 - 별자리 만들기 (BOJ 4386 JAVA) 문제 : boj4386 1. 모든 별을 이어야하고, 최소 비용을 구해야 한다. 따라서 N개의 정점(별)에 대해 이은 간선이 N-1개(모든 정점을 포함하려면 최소 N-1개의 간선이 필요하고, 최소비용을 위해서는 거기서 하나라도 간선이 추가되선 안되므로) 이어야만 모든 별을 이으면서 최소 비용이 가능하다. 따라서 Spanning Tree를 구성해야 하고, 최소 비용이어야 하므로 MST (Minimum Spanning Tree)를 구하는 문제임을 알 수 있다. 후보군이 될 간선은 N개에 대해 다른 N-1개 모두로의 간선이므로 간선은 총 N*(N-1)개 존재할 수 있다. 이 중 N-1개를 골라 MST를 만들었을 때의 최소 비용이 답이다. 2. 대표적인 MST 알고리즘에는 Prim과 Kruscal이 있다. 이 문.. 2022. 1. 12.
백준 14248 자바 - 점프 점프 (BOJ 14248 JAVA) 문제 : boj14248 문제 자체의 정의에 따라 i번째 정점에서 i-Ai, i+Ai 로의 간선이 생긴다. 이에 대해 단순히 방문 가능한 위치만 찾으면 되므로 dfs 혹은 bfs로 더이상 진행 불가할때까지 진행해보면서 방문한 곳의 개수를 세면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { boolean[] v; int cnt = 0, n; int[] arr; private void dfs(int s) { if (sn||v[s]) return; v[s] = true; cnt++; dfs(s+arr[s]); dfs(.. 2022. 1. 11.
백준 11060 자바 - 점프 점프 (BOJ 11060 JAVA) 문제 : boj11060 N이 1000까지이고, Ai가 최대 100이라 대충 돌려도 O(NA = 100000) 이라 널널한 문제이다. 가장 좌측지점부터 시작해서 dp 개념을 살짝 섞은 브루트포스로 풀면 된다. 각 입력값에서 갈 수 있는 모든 곳을 가보면서 최소로 갈 수 있는 수치로 갱신해가면 된다. dp[x]는 x위치까지 갈 수 있는 최소 점프 횟수가 된다. 점화식은 Ai에서 i=x에서 시작해 우측으로 이동한 경우이고 현재 y (x+1 2022. 1. 10.
백준 2331 자바 - 반복수열 (BOJ 2331 JAVA) 문제 : boj2331 무작정(brute force) 계속 D[n]을 구해나가면서 이전에 이미 나왔던 결과가 다시 나오는지 확인만 하면 된다. 이 때, 중복된 값은 해싱을 통해 찾으면 빠르게 찾을 수 있다. 추가로 중복값이 나왔을 때 해당값의 위치가 몇번째였는지를 알아야 남게되는 수들의 개수를 출력할 수 있다. 따라서 HashMap을 사용해서 이미 나왔던 수와 해당 수가 몇번째에 나왔는지를 기록해두면 이후 중복된 값이 계산되었을 때 바로 남은 수의 개수를 알 수 있다. (중복값이 나온 위치 이전의 모든 값들이 남은 수들이 된다.) 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Hash.. 2022. 1. 9.
백준 9847 자바 - 4SUM (BOJ 9847 JAVA) 문제 : boj9847 1. Brute Force로 가능한가? 4개의 수의 합이 0이 되는 경우를 찾아야 한다. 제일 간단하게 생각해보면 모든 쌍을 보면 된다. 이 경우 O(500^4) 이므로 유효한 시간 내에 찾을 수 없다. 2. 문제를 단순화 해보자 그럼 우선 문제를 단순화해서 생각해보자. 세트가 2개만 존재한다고 생각해보자(각 세트에 들어간 수는 N개). 그럼 각 세트에서 하나씩 골라서 2개의 수의 합은 어떻게 찾을 수 있을까? 모든 경우를 보는 O(N^2)보다 더 빠른 방법이 있을까? 두 세트가 X와 Y라고 한다면, X의 수를 정렬한 후 Y의 모든 수를 순회하면서 X에 대해 이분탐색으로 합이 0이 되는 경우를 찾을 수 있을 것이다. 그럼 O(NlogN[정렬] + N[순회]*logN[이분탐색]) 정.. 2022. 1. 8.
백준 20949 자바 - 효정과 새 모니터 (BOJ 20949 JAVA) 문제 : boj20949 원하는 방식으로 정렬하는 방법만 알면 쉽게 풀 수 있는 문제이다. 이 문제의 경우 쿼리로 따지면 ORDER BY [W^2+H^2 값] DESC, IDX ASC 인 셈이다. 이 때 W^2+H^2은 W와 H가 모두 최대 3만이므로 두 합은 최대 18억으로, int형으로 표현 가능한 수치이다. 당연하게도 문제에서 square root가 있다고 루트 씌우고 계산하면 소수점 오차때문에 틀릴 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; class Monitor implements Co.. 2022. 1. 6.

티스토리툴바