잡다한 IT 지식

본 알고리즘 풀이는 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번째 숫자. [접근 방법] 문제를 딱 봤을 때, 엄청 쉽네 생각하고 풀었다가 오버플로우나 시간 초과나서 망하기 좋은 문제. 백퍼센트 각각의 값에 관계가 ..

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/2644 [문제 설명] 촌수 구하기 [접근 방법] BFS로 걸리는 거리가 촌수다. [내 답안 수정하기] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedRea..

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/18111 [문제 설명] N*M 크기의 맵이 있을 때, 높이를 나라시한다고 했을 때, 최소시간을 구하시오. 최소시간이 여러 개면 가장 높은 높이를 리턴하시오. [접근 방법] 현재 땅의 높이 중 최소 높이부터 최대 높이까지 모든 경우를 만들어보고, 그 중에 시간이 가장 작고, 높이가 가장 높은 것을 리턴한다. 3 4 99 0 0 0 0 0 0 0 0 0 0 0 1 위의 테스트 케이스라면 최소 높이가 0 최대 높이가 1이므로, 0부터 1까지 모든 경우의 수를 구한다. ..

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/14620 [문제 설명] 땅에 꽃을 3개 부화시킬려고한다. 가장 돈이 적게 들게 땅을 사는 방법은? [접근 방법] 완전탐색 문제다. 꽃은 왼쪽 오른쪽 위 아래 크기이기 때문에, 1~땅의 크기-1까지 놓을 수 있다. 땅의 크기가 6이상 10이하이므로 면적은 최소 36에서 100이 된다. 시간복잡도는 꽃을 심을 때마다 면적을 전부 검색하며, 꽃의 개수는 3개이므로 O(면적^3) 땅의 크기를 N으로 줬을 때, 면적은 N^2이니 O(면적^3)은 O(N^6)이 된다. 언뜻 ..