잡다한 IT 지식

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/1024 [문제 설명] 1인 등차를 가진 배열의 합이 N이고 길이가 N이상인 것을 찾으시오 [접근 방법] 등차수열식으로 첫항을 유도하기 a는 첫항, d는 등차, n은 수열의 순서라고 할 때 An = a+(n-1)d Sn(1번부터 n번까지 수열의 총합) = (첫항+끝항)/2*전체개수 = ((2a+(n-1)d)/2)*n == N 현재 우리에게 주어진 조건은 N과 L a에 대한 식으로 만들자 (2a+n-1)*n = 2N => (2a+n-1) = 2N/n => 2a = 2..

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/10815 [문제 설명] 카드가 있으면 1을 출력, 없으면 0을 출력. [접근 방법] 1.딱 봤을 땐 O(NM) 문제. 연산횟수 50만*50만 => 좋지 않은 선택 2.이분탐색 O(NlogN) 문제. 연산횟수 50만*log50만 => 할만해보임 3.해싱을 이용하면 O(N) + O(M). 연산횟수 50만+50만 => 최고 [이분탐색] import java.io.BufferedReader; import java.io.IOException; import java.io.I..

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/7562 [문제 설명] 체스판의 시작 좌표와 도착 좌표가 주어졌을 때, 도착 좌표까지 몇번만의 이동할 수 있나? [접근 방법] BFS로 풀었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; p..

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/4375 [문제 설명] 1,11,111,1111,11111 주어진 숫자를 배수해서 만들 수 있는 1로 이루어진 숫자는 몇번째 숫자인지 구하시오. 예: 입력이 3일 때 3에 37을 곱한 111이 1로 이루어진 숫자다. 즉, 1로 이루어진 세번째 숫자. 입력이 7일 때 111111은 7의 배수다. 즉, 7로 이루어진 6번째 숫자. [접근 방법] 문제를 딱 봤을 때, 엄청 쉽네 생각하고 풀었다가 오버플로우나 시간 초과나서 망하기 좋은 문제. 백퍼센트 각각의 값에 관계가 ..