분류 전체보기
-
신기술 관련정보처리기사 2023. 4. 18. 23:32
베이퍼웨어(Vaporware) 실제로 존재하지 않거나 출시되지 않은 제품, 소프트웨어 하드웨어 일반적으로 기업이나 개인이 제품을 발표한 후, 실제로는 출시되지 않거나 개발이 중단된 경우 사용 HACMP(High Availablity Cluster Multiprocessing) 각 시스템 간 공유 디스크 중심으로 클러스터링으로 엮어 다수의 시스템을 동시에 연결 조직, 기업 간 기간 업무 서버 등의 안정성을 높이기 위해 사용 여러 가지 방식으로 구현 2개의 서버를 연결하는 것으로 2개의 시스템이 각각 업무를 수행하도록 구현하는 방식이 일반적 트러스트존(Trust zone) 프로세서 안에 독립적인 보안 구역을 따로 두어 중요한 정보를 보호하는 하드웨어 기반 보안 기술 ARM CPU에서 지원, 기존 운영체제가 ..
-
Q. 15681 자바 : 트리와 쿼리코딩테스트/백준_Java 2023. 4. 17. 16:48
Q. 15681 자바 : 트리와 쿼리 문제 : boj.kr/15681 골드 5 난이도의 문제이다. 트리와 간선이 주어진다. 이후 Q개의 정점이 주어지고 각 정점을 루트로 하는 서브트리의 정점의 수를 구하는 문제이다. 아래와 같은 풀이로 풀었다. 0. 간선이 주어지므로 ArrayList를 사용해 트리 구조를 만든다. 1. 루트 노드가 주어지므로, dfs 탐색을 이용해 탐색한다. 2. 서브트리의 정점의 수를 구하기 위해 탐색 이후 종료 전에 자식을 루트로 하는 서브트리의 정점의 수를 저장한다.(메모제이션 방식) 3. 이후 Q개의 정점에 대해 각 정점을 루트로 하는 서브트리의 정점의 수를 2번에서 저장한 값을 이용해 결과를 출력한다. 시간 복잡도는 정점의 수 N 이 최대 10,000이고 탐색하는 정점 Q도 최..
-
Q. 3584 자바 : 가장 가까운 공통 조상코딩테스트/백준_Java 2023. 4. 16. 09:53
Q. 3584 자바 : 가장 가까운 공통 조상 문제 : boj.kr/3584 골드 4 난이도의 문제이다. 트리의 정점의 수와 간선이 주어진다. 이후 두 정점이 주어지면 공통조상 정점을 출력하는 문제이다. 주의해야 할 점은 루트 노드는 1번 정점이 아니라는 점 이다. 아래와 같은 풀이로 풀었다. 1. Tree class를 만든다. 트리 클래스는 인덱스, 깊이, 자식, 부모의 정보를 가진다. (루트 노드가 1번 정점이 아니므로 1번 정점의 부모가 null일 때 까지 정점을 이동시키고 dfs를 통해 깊이를 저장했다.) 2. 두 정점이 주어졌을 때 공통 조상을 찾기 위해 깊이를 동일하게 맞춘다. 3. 이후 한 칸씩 부모로 올라가며 공통 조상이 나올 때 까지 반복한다. (풀고나서 다른 풀이를 찾아보니 좀 비효율적..
-
Q. 20364 자바 : 부동산 다툼코딩테스트/백준_Java 2023. 4. 15. 09:01
Q. 20364 자바 : 부동산 다툼 문제 : boj.kr/20364 실버 1 난이도의 문제이다. 트리의 정점의 수 n이 주어지고, 오리들의 수 q가 주어진다. 이후 오리들이 원하는 정점이 주어지는데, 만약 탐색 도중 다른 오리가 있다면 거기서 탐색을 멈추고 그 좌표를 출력하고 탐색이 완료되면 0을 출력한다. 문제는 아래와 같이 풀었다. 1. 오리들이 원하는 정점 / 2를 통해 1까지 올라온다. 2. 만약 도중에 다른 오리가 있는 정점을 만난다면 그 값을 저장한다. 3. 정점 1까지 오리가 도달했을 때 저장된 값이 있다면 그 값을, 아니면 0을 출력한다. 이 문제의 시간복잡도는 아래와 같다. 1. 트리 DFS 순회 - O(log N) 2. 오리의 수 Q - O(Q) 최악의 경우 오리가 순서대로 마지막 ~..
-
Q. 15900 자바 : 나무 탈출코딩테스트/백준_Java 2023. 4. 14. 09:40
Q. 15900 자바 : 나무 탈출 문제 : boj.kr/15900 실버 1 난이도의 문제이다. 성원이와 형석이가 대결을 한다. 트리 정점의 수가 주어지고, 모든 리프 노드에 게임말이 놓인다. 번갈아가며 한 번씩 말을 옮기고 옮길 수 있는 말이 없는 경우 패배하는 게임이다. 성원이가 선공을 한다면 게임판만 보고 승패 여부를 알려주는 문제이다. 문제는 아래와 같이 접근했다. 0. 정점의 수가 주어지므로 이를 이용해 트리를ArrayList로 구현한다. 1. 모든 리프 노드의 깊이의 합을 dfs를 사용해 구한다. (ArrayList에 부모 노드만 가지면 == 크기가 1이면 리프 노드이다.) 2. 각자 한 번씩 움직이므로 1번값 % 2 연산을 해 결과를 구한다. 주의해야 할 점은 1번 정점의 경우 부모 노드가 ..
-
Q. 1991 자바 : 트리 순회코딩테스트/SWEA_Java 2023. 4. 13. 09:47
Q. 1991 자바 : 트리 순회 문제 : boj.kr/1991 실버 1 난이도의 문제이다. 이진 트리가 주어졌을 때 전위, 중위, 후위 순회를 해 결과를 출력하는 문제이다. 주의해야 할 점은 이진 트리로 입력이 주어지며, 자식이 없을 경우 '.'으로 주어진다는 점 이다. 아래와 같은 방식으로 풀이했다. 1. 저장을 List에 해야하므로, 입력값을 int로 변환하는 과정이 필요했고, 입력은 유효한 값이 주어지므로(A-Z 사이의 값) root 노드의 값 - 'A'를 계산해 int로 변환한 뒤 자식들을 이 인덱스를 가진 List 안에 저장했다. 2. 순회를 할 때는 list에 들어있는 값 - 'A'를 이용해 자식 노드에 방문했고, 출력을 할 때는 현재 인덱스 + 'A'를 문자열로 반환해 출력했다. 이진 트리..
-
Q. 5567 자바 : 결혼식코딩테스트/백준_Java 2023. 4. 12. 09:23
Q. 5567 자바 : 결혼식 문제 : boj.kr/5567 실버 2 난이도의 문제이다. 간선이 주어지고 탐색을 통해 깊이가 2인 정점까지 방문 가능하다면 몇 개의 정점을 방문 가능한지 세는 문제이다. (상근이의 친구 - 깊이가 1, 친구의 친구 - 깊이가 2) 간선만 주어지므로 격자형 그래프가 아니라 ArrayList를 사용해서 문제를 해결했다. 또한 양방향 그래프이므로 간선을 입력받을 때 두 정점 모두 표시했다. 이 문제의 경우 아래와 같은 방식으로 해결했다. 1. 입력값을 받아 두 정점에 저장한다. 2. 깊이우선탐색(DFS)를 시작한다. 3. 이 때 주의해야 할 점은 깊이가 2일 때 까지 모든 정점을 탐색해야 하므로 방문 여부 확인은 하되, 이미 방문한 정점에 대해서도 탐색한다. (어떤 사람에게는 ..
-
Q. 18404 자바 : 현명한 나이트코딩테스트/백준_Java 2023. 4. 11. 09:21
Q. 18404 자바 : 현명한 나이트 문제 : boj.kr/18404 실버 1 난이도의 문제이다. 앞의 나이트의 이동 문제와 비슷하다. 나이트의 위치가 주어지고, 잡아야 할 말의 위치가 여러 개 주어진다. 이 때 각각의 말을 나이트가 몇 번 움직여서 말을 잡을수 있는지 출력하는 문제이다. 격자형 그래프 탐색문제에서 상 하 좌 우 순회하는 방식을 응용해탐색하는 범위만 바꾸면 쉽게 풀리는 문제이다. 체스판의 한 변의 길이로 주어지는 N의 최대값이 500이고, 잡아야 할 말의 수 M의 최대값이 1000이다. 따라서 시간복잡도는 아래와 같다. 1. 주어진 말의 수 - O(M) 2. BFS 순회 - O(N ^ 2) 시간복잡도는 약 O(N ^ 2)이고, 최대 2500000번 계산을 하면 문제를 해결할 수 있다. ..