본문 바로가기

분류 전체보기138

BOJ 1202 - 보석 도둑(Java) https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 완전 탐색으로 풀 경우 보석의 개수 N(1 ~ 300,000), 가방의 개수 M(0 ~ 100,000,000)으로 O(N*M)의 시간 복잡도를 가짐, 안될 거라 생각하고 풀어봤지만 역시나 시간초과 발생 * 시간 복잡도를 줄여야하며 우선순위 큐를 이용하여 품 우선 순위 큐를 이용한 풀이 - 가방에 대해서는 for문을 이용하여 탐색 -.. 2021. 12. 31.
쿠버네티스 소개 쿠버네티스가 등장하기 전까지의 가상화 기술 VM(Virtual Machine) 서비스 운영을 위해서는 서버 자원을 효율적으로 사용하는 것이 중요 ex) 게임의 접속 대기열 트래픽을 예상하기도 어려우며, 미리 여유러운 자원을 준비하는 것도 비용적으로 쉽지 않은 문제 이를 해결하기 위해 VMware, Virtual Box와 같은 VM이 출현하여 서버 운영의 자동화가 가능해짐 Docker(Container) VM 가상화는 OS가 필요하다는 문제가 발생, 하나의 서비스를 위해 더 무거운 OS를 띄워야하기 때문 이러한 문제를 Docker(컨테이너 가상화 기술)로 해결가능 컨테이너 가상화 기술은 서비스간 자원 격리로 OS를 띄울 필요가 없음, OS 기동 시간이 없기 때문에 자동화가 빠르고 자원 효울이 높음 쿠버네티.. 2021. 12. 28.
BOJ 1715 - 카드 정렬하기(Java) https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 이전의 합이 누적되는 형태 - (a + b) + (a + b + c) + (a + b + c + d) + ...... - 각 합의 작은 값이 누적되는 횟수를 크게, 큰 값이 누적되는 횟수를 작게 해야함 불가능한 방법 입력 요소의 정렬 만으로는 해결 불가능 - ex) 60, 50, 70, 80 - 요소 정렬 : 50, 60, 70, 80 - 누적 합 -> (50 + 60) + (.. 2021. 12. 27.
BOJ 4256 - 트리(Java) https://www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 풀이 전위 순회 : 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드 중위 순회 : 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드 * 전위 순회의 0번째 노드는 현재 노드, 중위 순회 요소에서 현재 노드를 기준으로 왼/오른쪽 노드로 나뉨 위의 2가지 순회로 트리 구조 및 후위 순회 파악 가능 now= 0을 루트로 [0 ~ N]의 범위에 대해 탐색 1. preOrder[now] = 현재 노드 2.. 2021. 12. 23.
BOJ 23291 - 어항 정리(Java) https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 물고기 수의 최대/최소인 어항의 차이가 K이하일 때 까지 반복 1. 물고기가 최소인 어항에 물고기 추가 - 어항에 물고기 수가 최소인 어항들에 물고기 수를 1씩 추가 2. 어항 쌓기 - 시계 방향 90도로 어항을 말아서 쌓음 - 처음에는 가장 왼쪽의 1개 항만 이동, 이후부터는 쌓여져있는 모든 어항을 이동 3. 물고기 수 조절 - 상하좌우 인접 어항을 확인, 현재 어항이 인접한 어항의 물고기.. 2021. 12. 22.
BOJ 2638 - 치즈(Java) https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 매 시간마다 외부 공기와 2변 이상 접촉하면 해당 위치의 치즈가 녹음 외부 공기 판별 가장자리에는 치즈가 없다. -> 모든 가장자리는 외부 공기 (0, 0)의 위치로 부터 시작 해서 치즈를 만나지 않는 위치로 dfs 탐색을 이용하여 외부 공기 판별 가능 private static void checkExternalAir(int i, int j) { visit[i][j] = true.. 2021. 12. 20.
ALGOSPOT - Synchronizing Clocks(JAVA) https://www.algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 www.algospot.com 풀이 스위치를 누르는 모든 경우의 수를 탐색(브루트 포스) 3, 6, 9, 12를 1, 2, 3, 0으로 변환 for (int j = 0; j < LEN; j++) { int temp = Integer.parseInt(st.nextToken()); watches[j] = (temp / 3) % 4; } 같.. 2021. 12. 16.
Programmers - 문자열 압축(Java) https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 풀이 같은 값이 연속해서 나타나는 경우 반복되는 갯수를 표기하며 줄여서 표기 ex) aaa -> 3a * 단, 정해진 길이가 반복되는 경우만 압축가능 ex) aabbb -> 2a3b(X) -> 2a2bb(O) * 완전 탐색으로 가장 작은 길이의 결과를 구하되, 탐색의 범위를 줄이는 것이 필요 주어지는 문자열의 길이를 이용하여 최대 압축 길이를 구함, 이 .. 2021. 12. 16.
BOJ 16234 - 인구 이동(Java) https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 인구이동이 더 이상 불가능 할때 까지 계속해서 이동 반복 이동되는 구역을 visit[][]로 확인, 다시 탐색하지 않도록 예외 처리 - 인구 이동이 가능한지 확인 - 인구 이동이 가능하다면 해당 구역 전체 인구 이동 - bfs를 이용하여 인근 구역 탐색 -> L < abs( map[y][x]-map[ny][nx] ) < R이라면 이동 가능 - 인구이동 구역 설정까지 bfs 탐색.. 2021. 12. 14.

티스토리툴바