본문 바로가기

분류 전체보기

 (42)
[BOJ 17626] Four Squares - Java 풀이 해설 자연수 N이 주어지고, N을 구성할 수 있는 제곱수들의 수를 구하는 문제이다. 모든 자연수는 최대 자연수 4개의 제곱수의 합으로 표현할 수 있다고 라그랑주에 의해 증명이 되었다. 나의 경우 문제의 자연수를 제곱수가 2이상인 자연수로 착각해서 오래걸렸다. 풀이 과정은 다음과 같다. 배열에 1부터 N까지의 값을 저장한다. (i-j^2)+1 값을 사용해 값을 구해나간다. i는 1부터 N까지 순회하는 자연수를 의미한다. 1번의 의미를 1*1의 값의 개수라고 생각해보자. 그리고 배열을 돌면서 (i-j^2)+1를 적용시킨다. 이것을 다음과 같은 코드로 적용시킬 수 있다. for (int i = 1; i
[백준 11727] 2×n 타일링 2 풀이 해설 n이 1일 때, 2x1타일 하나가 들어갈 수 있고, n이 2일 때 (1x2, 1x2), (2x1, 2x1), (2x2) 3가지 경우의 수로 타일을 채울 수 있다. 그리고 n이 3일 때를 보면, 2x1타일을 왼쪽이 위치시켰을 경우 n이 2일 때 경우의 수만큼 채우고, n이 1일 때 경우의 수인 2x1타일이 2번 채워지는 것을 볼 수 있다. n이 4일 경우에도 마찬가지이다. 이것을 이용해 점화식을 짜본다면, n = n-1 + (n-2) * 2가 나온다. 시간복잡도 N만큼 순회하므로, O(N)이다. 코드 package _2xn타일링2_11727; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR..
[프로그래머스] 기지국 설치 풀이 해설 이 문제는 전파가 닿지 않는 기지국의 범위 안에 모든 아파트에 전파를 전달하기 위해선, 몇개의 기지국이 설치되어야 하는가에 대한 값을 찾는 문제이다. 값을 찾기 위해 필요한 것은 다음과 같다. 전파가 닿지 않는 아파트의 범위 해당 범위들에 필요한 기지국의 수를 구하는 방법 전파가 닿지 않는 아파트의 범위 문제에선 stations 배열로 이미 설치된 기지국의 위치가 주어진다. 따라서 해당 위치를 기준으로 기지국의 전파 범위인 w를 빼거나 더해 범위를 구할 수 있다. 1(첫번째 아파트)부터 station - w까지 기지국이 설치되지 않았다고 가정한다면, 첫번째 범위는 station - w - 1이라고 볼 수 있다. 이제 해당 범위의 필요한 기지국의 수를 구하면 된다. 이후엔 기준을 station ..
[백준 1504] 특정한 최단 경로 특이사항 반드시 거쳐야 하는 정점 2개가 존재 풀이 그래프에 대한 최단경로 값을 구하는 문제이다. 다익스트라 알고리즘을 통해 풀이할 수 있고, 특이사항에 대한 처리를 해주면 된다. 거쳐야 하는 정점 int result1 = 0, result2 = 0; result1 += dijkstra(1, v1); result1 += dijkstra(v1, v2); result1 += dijkstra(v2, N); result2 += dijkstra(1, v2); result2 += dijkstra(v2, v1); result2 += dijkstra(v1, N); if (result1 >= INF && result2 >= INF) { System.out.println(-1); } else { System.out.pri..
[백준 1676] 팩토리얼 0의 개수 특이사항 팩토리얼은 n의 값이 커질수록 기하급수적으로 수가 커진다. 이렇게 수가 커진다면, 컴퓨터가 저장할 수 있는 변수의 크기를 넘어버리기 때문에, 답을 도출하기 힘들다. 풀이 n의 크기에 따라 소인수분해를 통해 2, 5의 수를 구한다. 2와 5를 곱하면 10이 되기 때문에, 10의 배수가 된다. 10의 배수는 또한, 2 * 5로 볼 수 있다. 즉, 2와 5의 개수를 구하고 2 * 5를 통해 0이 몇개를 포함하고 있는지 구할 수 있다. 하지만 2의 배수는 항상 5의 배수보다 많기 때문에, 5의 배수의 개수만으로 10의 배수의 개수를 추론할 수 있다. (5의 배수 개수 = 10의 배수 개수) 25와, 125를 나누어 더해준 이유는 25=5^2이고, 125=5^3이기 때문이다. 5로만 나누게 된다면 위와 ..
사람의 마음을 움직이는 것 유튜브의 TED채널에 있는 영상인 How great leaders inspire action을 보고 글을 써본다. 해당 영상에서는 골든 써클에 대해서 말하고 있다. 영상에서 Simon Sinek은, 골든 써클을 사용해 세계의 훌륭하고 영감을 주는 리더 또는 단체들이 어떻게 사람들의 마음을 잡고 움직이게 만드는지 설명하고 있다. 좋은 내용을 담고 있으니, 보는 것을 추천한다. 영상에서 써클 안에서의 Why, How, What 등이 무슨 의미가 있는지 설명을 하지만, 가장 중요하다고 느낀 것은 사람들은 신념을 구입한다는 것이다. 기업을 예로 들었을 때, 기업의 서비스가 무엇이고 이 서비스는 어떤 장점이 있고 혁신이 있고 ... 등은 사람들의 행동을 이끌어내지 못한다. 이것은 구매를 하게 만들지 못한다는 것과..
Servlet은 무엇이며 어떻게 동작하는가? 웹서버 구축을 위해서 Java를 사용한다면 알아야하는 Servlet이라는 클래스에 대해 알아보자. 서블릿의 사용법보다 서블릿이 무엇이며 웹에서 어떤 환경 활용되고 있는지, 어떤 원리로 동작하고 있는지에 대해 중점적으로 알아보려 한다. 자바 서블릿이 웹 페이지를 동적으로 생성하게 해주는 클래스라고 하는데 어떻게 도와주는 것일까? 이것을 이해하기 위해선 웹이 어떻게 통신하는지부터 이해해야 한다. HTTP 웹은 HTTP라는 비연결성 프로토콜을 이용해 통신을 한다. 메세지 방식에는 request와 response가 있는데, 서버측에 요청(request)을 하면 서버는 요청에 맞는 데이터를 응답(response)한다. 보통 요청을 보내고 응답을 받는 쪽을 클라이언트라 말하고, 요청을 받고 응답을 보내는 쪽을 서버..
[백준 1629] 곱셈 문제 1629번: 곱셈 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 해결 시간초과 간단하게 for문으로 A를 B만큼 곱한다음 C로 나누어 값을 구할 수 있다. 하지만 이 문제의 입력값은 최대 2,147,483,647이고, 시간제한은 0.5초이다. 널널하게 2억번의 연산당 1초로 잡아도 10초 이상의 시간이 걸리게 되는 것을 알 수 있다. 따라서 B만큼 곱하는 방법은 사용할 수 없다. 오버플로우 최대 입력값이 2,147,483,647가 들어온다고 명시되어 있다. 이 값은 꽤 큰 값이기 때문에 큰 값이 들어온다면 연산시 오버플로우가 발생할 것이다. 지수 계산 이 문제는 오버..

티스토리툴바