분류 전체보기

[BOJ/JAVA] 11559번: Puyo Puyo

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 키워드 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다. 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다. 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다. 구현 정리하면 연쇄는 **중..

[BOJ/JAVA] 20055 컨베이어 벨트 위의 로봇

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 키워드 로봇은 올리는 위치에만 올릴 수 있다. 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다. 로봇은 컨베이어 벨트 위에서 스스로 이동할 수 있다. 로봇을 올리는 위치에 올리거나 로봇이 어떤 칸으로 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 ..

[BOJ/JAVA] 14653번: 너의 이름은

https://www.acmicpc.net/problem/14653 14653번: 너의 이름은 첫째 줄에 OAKAK TALK방에 있는 사람 수 N과 총 메시지의 개수 K, 정보를 알고 싶은 메시지의 번호 Q가 주어진다. (1 ≤ N ≤ 26, 1 ≤ K ≤ 10,000, 1 ≤ Q ≤ K) 둘째 줄부터 K개의 줄에 걸쳐 메시지를 읽지 www.acmicpc.net 키워드 N명이 있는 OAKAK TALK방이 있다. 그리고 그 방에는 K개의 메시지가 있다. 만약 어떤 시점에 메시지를 읽거나 보냈다면, 그 시점 이전에 수신된 메시지는 모두 읽은 것으로 처리된다. N명의 이름은 A부터 사전 순서대로 N개의 알파벳이 부여된다. “나”의 이름은 A이고 “나”는 항상 모든 메시지를 읽는다. Q번째 메시지를 읽지 않은 ..

[BOJ/JAVA] 1063번: 킹

https://www.acmicpc.net/problem/1063 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 키워드 킹은 8방향으로 이동한다. 체스판에는 돌이 하나 있는데, 돌과 같은 곳으로 이동할 때는, 돌을 킹이 움직인 방향과 같은 방향으로 한 칸 이동시킨다. 킹이나 돌이 체스판 밖으로 나갈 경우에는 그 이동은 건너 뛰고 다음 이동을 한다. 구현 8방향 이동 Map을 구현한다. 체스판 좌표를 배열 좌표에 매핑시킨다. 배열의 범위를 벗어나는지 확인하는 메소드를 구현한다. 현재 이동하려는 위치에 돌이 있는지 확인한..

[BOJ/JAVA] 20058번: 마법사 상어와 파이어스톰

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 키워드 크기가 2^N × 2^N인 격자로 나누어진 얼음판 위치 (r, c)는 격자의 r행 c열을 의미 A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다. 파이어스톰 먼저 격자를 2^L × 2^L 크기의 부분 격자로 나눈다. 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 ..

[BOJ/JAVA] 1303번: 전쟁 - 전투

키워드 당신의 병사들은 **흰색 옷**을 입고, 적국의 병사들은 **파란색 옷**을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. N명이 뭉쳐있을 때는 **N^2의 위력**을 낼 수 있다. 구현 [0][0] 부터 깊이 우선 탐색을 하면서 각 탐색 마다 방문 횟수를 저장하고, 방문 횟수의 제곱을 결과 score에 누적합을 한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class java_1303 { final static int dydx[][] = { { -1, 0 }, { 1, 0 }, { ..

[BOJ/JAVA] 17471번: 게리맨더링

키워드 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구현 2 구역을 나누는 알고리즘 조합을 이용하여 구현한다. 나눠진 2 구역이 각각 서로 연결되어 있는지 확인하는 알고리즘 DFS를 이용하여 연결되었는지 확인한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class java_17471 { static int ..

[BOJ/JAVA] 13565번: 침투

키워드 차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 안쪽(inner side) 각 격자는 검은색 아니면 흰색 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질 상하좌우로 인접한 흰색 격자들로 전달 구현 배열의 0행에서 0인 곳을 깊이 우선 탐색 (DFS)를 사용한다. 깊이 우선 탐색을 실행하면서 y값이 M-1이 되는 순간 결과는 YES가 되도록 처리한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class java_13565 { final static int dyd..

멀티 프로세서 스케줄링

개요 멀티 코어 프로세서 하나의 칩에 여러 CPU 코어가 내장 CPU를 더 추가해도 단일 애플리캐이션이 더 빨리 실행되는 것은 아니다. threads 를 이용하여 병렬 실행되도록 작성해야 한다. 캐시 작고, 빠른 메모리 캐시에 저장된 공유 리소스 데이터의 일관성 문제 버스 스누핑 각 캐시는 자신과 메모리를 연결하는 버스의 통신 상황을 계속 모니터링 CPU가 캐시에 보유한 데이터 항목에 대한 업데이트를 발견하면 변경 사항을 인식하고 복사본을 무효화하거나 업데이트 함 → CPU를 통해 공유된 데이터에 접근할 때는 정확성을 보장하기 위해 상호 배제가 필요하다. 락(lock)을 사용하여 해결한다. → 가능한 동일한 CPU에 프로세스를 유지시킨다. 다중 프로세서 스케줄러는 캐쉬 친화성을 고려해야 한다. 단일 큐 ..

싱글 프로세서 스케줄링

제한적 직접 실행 원리 OS는 시간 공유를 통해 물리적 CPU를 공유한다. 이를 이용하여 여러 작업들이 동시에 실행되는 것처럼 보이도록한다. 이를 구현하기 위해서 성능 저하, 제어 문제 를 해결해야 한다. 제한적 직접 실행 프로그램을 빠르게 실행하기 위하여 제한적 직접 실행 기법을 사용한다. 이는 단순히, 프로그램을 CPU 상에서 그냥 직접 실행시키는 것이다. 문제점 사용자가 잘못된 일을 한다면 판단하기가 쉽지 않음 OS가 CPU의 제어 권한을 얻는 것이 쉽지 않음 개요 스캐줄링 현재 프로세스를 중단하고 다른 프로세스를 실행하기로 결정 → 운영체제는 문맥교환(Context Switch)코드를 실행 워크로드 프로세스가 동작하는 일련의 행위 아래 스케줄링 방법은 다음을 가정한다. 작업은 동일한 시간 동안 실..