밤이 블로그

BOJ#2887 행성 터널 * 문제https://www.acmicpc.net/problem/2887 * 풀이 MST, 최소 스패닝 트리 문제입니다.최소 스패닝 트리의 특성상 (문제에도 명시되어 있듯이) 행성이 N개 이므로, 간선은 N-1개가 됩니다. 이 문제를 풀 때 어려웠던 점은 간선 정보가 직접적으로 주어지지 않고직접 간선 정보를 만들어야 한다는 점입니다. 주의할 점으로는N이 최대 100,000 이므로 모든 간선을 입력하려면 100,000 * 100,000이 됩니다. (시간 초과) 따라서 모든 간선을 추가할 수 없으므로, 아래 방법대로 최소 간선만 추가해줍니다. 간선 비용은 문제에 주어진대로 min(x좌표 차이, y좌표 차이, z좌표 차이) 이므로1. x좌표를 기준으로 정렬 -> i-1 노드와 i 노..

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#1010 다리 놓기 * 문제https://www.acmicpc.net/problem/1010 * 풀이풀이 #1. 조합이 문제는 단순히 M개의 사이트 중에서 N개를 고르는 경우의 수를 구하는 문제입니다. 조합 : mCnmCn = m! / {(m-n)! * n!} 풀이 #2. 동적계획법dp[N][M] : 사이트가 각각 N개, M개일 때, 주어진 조건에 맞게 다리를 건설할 수 있는 경우의 수dp[N][M] = dp[N-1][M-1] + dp[N-1][M-2] + ... + dp[N-1][N-1] * 나의 코드https://github.com/stack07142/BOJ/blob/d8bb015604a276ecd8643e16c9ae052c2c36a2fa/BOJ%231010_BuildBridge/src/Mai..

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비트를 사용하면..

자료구조 - Heap * Heap이란?1. Complete binary tree이면서 : 최대 2개의 자식 노드를 가지면서, 마지막 레벨을 제외하고는 다채워진, 자식이 추가될 때 왼쪽부터 추가되는 트리 2. Heap Property를 만족하는 것 1) max heap property : 부모는 자식보다 크거나 같다. 2) min heap property : 부모는 자식보다 작거나 같다. 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 ..

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..

BOJ#10814 나이순 정렬 * 문제https://www.acmicpc.net/problem/10814 * 풀이PriorityQueue를 이용해보았습니다.나이순으로 정렬하고나이가 같은 경우 입력 순서대로 출력되는 것을 보장하지 않으므로 order 변수를 하나 추가해서 해결하였습니다. (다른 풀이)정렬할 필요 없이 ArrayList의 배열을 선언하고 나이 idx에 맞게 이름을 추가해주면 됩니다. * 나의 코드https://github.com/stack07142/BOJ/blob/062e7ce8f6877dc0ca458b108ed6b2cc8c2b4fbe/BOJ%2310814_SortByAge/src/Main.java import java.io.*; import java.util.PriorityQueue; im..

BOJ#1541 잃어버린 괄호 * 문제https://www.acmicpc.net/problem/1541 * 풀이문제 풀이 과정 55-50+40-10-30-20+40 int minSum = 0; 1. 입력받은 String을 "-"를 기준으로 분리합니다. {55, 50+40, 10, 30, 20+40} 2. 첫번째 원소는 그냥 더해주고 (문제 조건에 따라 첫번째 숫자는 양수이다)minSum = 55; 3. 나머지 각각의 원소에 대하여 합을 구한 뒤 minSum에서 빼줍니다. {55, 50+40, 10, 30, 20+40}{55, 90, 10, 30, 60} minSum = 55 - 90 - 10 - 30 - 60; * 나의 코드https://github.com/stack07142/BOJ/blob/697a29..

BOJ#14502 연구소 * 문제https://www.acmicpc.net/problem/14502 * 풀이2017년 상반기 삼성 SW 역량평가 기출문제 입니다. 벽을 항상 3개 설치해서 안전영역의 최대값을 구해야 하는 문제입니다.즉, 완전 탐색이 필요합니다. (모든 경우를 다 해봐야 최대값을 구할 수 있음) 저는 아래와 같이 풀어보았습니다. 1. 조합을 돌려서 Map에서 빈칸 3개를 선택한 후 벽으로 바꿔줍니다. 최대 8*8 맵에서 빈칸 3개를 선택할 때 경우의 수 = (64-2)C3(바이러스가 최소 2개 있으므로) 2. 해당 Map에서 바이러스를 퍼뜨립니다. 3. (맵의 크기 - 바이러스의 수 - 벽의 수) 의 최대값을 갱신합니다. 4. 1~3 반복 * 나의 코드 https://github.com/s..