밤이 블로그

BOJ#14438 수열과 쿼리 17 * 문제https://www.acmicpc.net/problem/14438 * 풀이Segment Tree - RMQ설명 : http://stack07142.tistory.com/216 * 나의 코드 (Java, Kotlin)https://github.com/stack07142/BOJ/blob/cd23ff130cc6e28b7f30aea5c4bc8932dad8688b/BOJ%2314438_SequenceQuery17/src/Main.java (Java)import java.io.*; import java.util.StringTokenizer; /** * 선데이코딩 베타라운드1 - E. 수열의 최소값 * BOJ#14439 수열과 쿼리 17 * https://www.acmic..

BOJ#3665 최종 순위 * 문제https://www.acmicpc.net/problem/3665 * 풀이위상 정렬 문제입니다. - 위상 정렬 설명 : http://terms.naver.com/entry.nhn?docId=3579618&cid=59086&categoryId=59093 첫 예제를 통해 어떻게 문제를 풀지 생각해보겠습니다. 5 4 3 2 1 1. 간선과 indegree를 아래와 같이 추가합니다. 간선의 경우 인접리스트보다는 인접행렬로 구현하는게 더 효율적일 것 같습니다. 5->4, 5->3, 5->2, 5->14->3, 4->2, 4->13->2, 3->12->1 [0, 4, 3, 2, 1, 0] int[][] graph = new int[n + 1][n + 1];// n^2 으로 인접행렬..

BOJ#2042 구간 합 구하기 * 문제https://www.acmicpc.net/problem/2042 * 풀이 http://stack07142.tistory.com/216 * 나의 코드 https://github.com/stack07142/BOJ/blob/48ba119dd11b7779be8b2d1e05a64b723e334d54/BOJ%232042_RangeSumQuery/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * BOJ#2042 구간의 합 구하기 * https://www.acmicpc.net/problem/2042 */ public class Main { static final int QUERY_CHANGE = 1;..

BOJ#2805 나무 자르기 * 문제https://www.acmicpc.net/problem/2805 * 풀이이분 탐색 * 나의 코드 https://github.com/stack07142/BOJ/blob/694dfa1bdca47f2449d56ad95c47ba5fc7a371f6/BOJ%232805_EKO/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#2805 EKO 나무 자르기 * https://www.acmicpc.net/problem/2805 */ public class Main {..

BOJ#4307 개미 * 문제https://www.acmicpc.net/problem/4307 * 풀이 쉬운 문제입니다.(개미의 속도가 모두 같기 때문에) 저는 막대의 중간에서 가장 가까운점, 가장 멀리 있는 점을 구해서 최대/최소 시간을 구했습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/a4b77ff3f9b58feceb146cac9d85601a166cb545/BOJ%234307_Ant/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * BOJ#4307 개미 * https://www.acmicpc.net/problem/4307 */ public class Main { public st..

BOJ#1152 단어의 개수 * 문제https://www.acmicpc.net/problem/1152 * 풀이1. 문자열을 입력받습니다. 앞, 뒤 공백이 있을 수 있으므로 trim 함수를 이용하여 공백을 제거합니다.2. 문자열을 정규표현식을 이용하여 분리합니다. (정규표현식 : \\{Blank}+ : 공백이 하나 이상)3. 분리한 문자열의 개수를 출력합니다. * 나의 코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * BOJ#1152 단어의 개수 * https://www.acmicpc.net/problem/1152 */ public class Main { public stati..

BOJ#2167 2차원 배열의 합 * 문제https://www.acmicpc.net/problem/2167 * 풀이단순하게 for loop 2개로 (i, j) ~ (x, y) 원소들을 더해도 되지만계산량을 줄이기 위해서 아래와 같이 구현해보았습니다. 1. 입력을 받으면서 dp[row][col]를 계산해 놓는다.dp[row][col] : (row, 1) 부터 (row, col)까지의 합 2. K개의 쿼리를 입력 받는다. (i, j), (x, y) 3. 행 단위로 합을 구하고 sum 변수에 합산한다. for ( row = i ... x) { sum += dp[row][y] - dp[row][j - 1];} * 나의 코드https://github.com/stack07142/BOJ/blob/6ac31273349..

BOJ#11729 하노이 탑 이동 순서 * 문제https://www.acmicpc.net/problem/11729 * 풀이 처음에는 bfs + 비트마스크를 이용하여 풀었습니다.하노이탑의 각 상태를 비트마스크를 이용하여 long 정수 하나로 구현하고, bfs 탐색을 해가면서 목표 정점을 찾는 방식(각 원판은 3개의 장대 중 하나에 존재할 수 있으므로 원판의 위치는 2비트로 표현할 수 있습니다.) 그러나 정점의 최대 개수가 3^20이고, 각 정점마다 3^2 loop를 통해 탐색을 하므로총 시간복잡도 3^22로 시간초과 발생합니다. , - 분할 정복법 : 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하고, 그 결과들을 합병하면서 본 문제를 해결하는 방식- 단점 : 보통 재귀 방식으로 구현되는데, 재..

BOJ#1525 퍼즐 * 문제https://www.acmicpc.net/problem/1525 * 풀이종만북을 참고하여 풀었습니다.To-Do : bfs, 양방향탐색, dfs 방법으로 각각 풀어보기 저는 이번에 bfs와 비트마스크를 이용해보았습니다. 맵은 하나의 정점으로 볼 수 있습니다. (총 정점의 수는 9! : 1부터 9까지 순서대로 나열하는 경우의 수와 같다) 그리고 상하좌우 4방향으로 이동할 수 있으니, 한 정점에서 최대 4개의 정점과 연결될 수 있습니다.즉, 주어진 정점에서 시작하여 4방향 탐색을 해나가면서 목표를 찾으면 되겠습니다. 문제는 어떻게 중복 방문을 체크하고 처리할 것인지 생각해봐야 합니다.저는 비트마스크를 이용해보았습니다. 각 값은 0부터 8사이의 값이므로, 각 값은 4비트를 사용하면..

BOJ#9084 동전 * 문제https://www.acmicpc.net/problem/9084 * 풀이참고한 블로그 : http://wootool.tistory.com/177http://blog.naver.com/PostView.nhn?blogId=occidere&logNo=220793012348http://heygyun.tistory.com/46 동적계획법의 개념(복잡한 문제를 여러 하위 문제로 나누어 푼다)을 잘 생각해봅시다.dp[i] : 주어진 동전을 가지고 금액 i를 만드는 경우의 수 예를 들어 목표 금액이 30원이고, 동전이 5원, 10원짜리가 있을 때 일단은 5원짜리만 있다고 가정했을 때 dp[30] : 5원짜리로 30원을 만드는 경우의 수이제 10원짜리 동전을 추가해보자. dp[30] : 3..