출처 : https://www.acmicpc.net/problem/19235 19235번: 모노미노도미노 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 해당 문제는 빨간색 보드에서 파란색 보드와 초록색 보드로 좌표에 따라 블록이 이동하는 게임입니다. 블록의 종류는 1x1, 1x2, 2x1이 있습니다. 해당 문제의 마지막 테스트케이스인 예제 7번을 수행하게 되면 다음 그림과 같이 배치됩니다. 파란색 보드에서 열 부분이 모두 채워지거나 초록색 보드에서 행 부분이 모두 채워지면 점수를 획득합니다. 열이나 행 부분이 모두 채워지지 않은 ..

문제 출처 : BOJ(https://www.acmicpc.net/problem/1753) 보통 그래프에서 정점끼리의 최단경로를 구하는 문제는 4가지가 있습니다. 1) 하나의 정점에서 다른 하나의 정점까지의 최단경로를 구하는 문제 2) 하나의 정점에서 모든 정점까지의 최단경로를 구하는 문제(다익스트라 알고리즘) 3) 모든 정점에서 하나의 정점까지의 최단경로를 구하는 문제 4) 모든 정점에서 모든 정점까지의 최단경로를 구하는 문제(플로이드 와샬 알고리즘) 추가로 모든 정점을 최소비용으로 연결하는 문제(MST: Minimum Spanning Tree, 최소 신장 트리)는 2가지가 있습니다. 5) 모든 정점까지의 최소비용을 오름차순으로 정렬해 연결하는 문제(크루스칼 알고리즘) 6) 하나의 정점에서 모든 정점까지..

문제 출처 : Programmers(https://programmers.co.kr/learn/courses/30/lessons/12946) 하노이의 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 두 가지 조건을 만족시키면서 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다. 1) 한 번에 하나의 원판을 옮길 수 있습니다. 2) 큰 원판이 작은 원판 위에 있어서는 안됩니다. 하노이의 탑 문제는 재귀 호출을 이용해 풀 수 있는 가장 유명한 예제 중 하나입니다. 출처 위키백과(https://ko...

출처 : Programmers(https://programmers.co.kr/learn/courses/30/lessons/42627) 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러는 여러 가지 방법으로 구현할 수 있습니다. 먼저, CPU 프로세스 스케줄링의 여러 가지 방법을 알아보려면 -> https://junboom.tistory.com/13 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 방법(FIFO: First In First Out, A -> B -> C)입니다. 이때, 각 작업의 요청으로부터 종료까지 걸린 시간의 평균은 (3 + 11 + 16) / 3 = 10ms입니다. 하지만 하드디스크 작업이 끝난 후 가장 짧은 작업 먼저 처리할 경우(SJF: Short Jo..

2020 상반기 삼성전자 SW 역량테스트 문제 출처 : BOJ(https://www.acmicpc.net/problem/19236) 4 x 4 공간 안에 물고기 16마리가 존재하고, 상어가 (0, 0) 지점의 물고기부터 먹기 시작해 먹은 물고기 방향으로 나아가며 먹기를 반복하는 문제입니다. BFS로 4 x 4 공간인 map과 물고기의 정보를 단계마다 저장할 수 있도록 HashMap과 Key인 cnt를 활용해 문제를 풀었습니다. 사이클마다 계속해서 map이 변하고, 물고기의 이동 방향이 변하기 때문에 HsahMap에 저장하는 방법을 선택했습니다. 우선, 상어가 (0, 0) 자리에 들어오고, (0, 0) 자리에 있던 물고기의 번호(num)를 섭취하고, 방향(d)을 가지게 됩니다. 이후 그 방향에 있는 모든 ..

열쇠를 회전하고, 이동시켜 자물쇠를 열 수 있는지 확인하는 알고리즘 열쇠의 크기(M)는 자물쇠의 크기(N) 보다 작을 수 있고, 열쇠가 자물쇠의 범위를 벗어나도 맞물리기만 하면 되므로 M - 1 + N + M - 1 = N + (M - 1) * 2 크기의 이차원 배열을 새로 만들어 줍니다. 가운데 N 자리에 lock을 복사합니다. 이차원 배열을 계속해서 복사하고, 복사된 이차원 배열에 열쇠가 한 칸씩 이동하면서 이차원 배열과 열쇠를 더해 lock 자리가 있는 곳만 모두 1인지 확인하여 true를 반환합니다. Java 코드 public class Solution_자물쇠와열쇠 { public static boolean solution(int[][] key, int[][] lock) { int M = key...