전체 글
-
백준(BOJ) 17070번 파이프 옮기기 1알고리즘 풀이/백준(Boj) 2019. 10. 31. 00:51
문제 : https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 www.acmicpc.net 풀이 : 각각 가로, 세로, 대각 규칙에 따라서 재귀적으로 호출해주자. 방향이 세로인지 가로인지 대각인지 알아야 하..
-
10. CPU 스케쥴링운영체제/운영체제 정리 2019. 10. 28. 21:32
CPU Scheduling Algorithms -FCFS ( First-Come, First-Served) -SJF ( Shortest Job First) -Priority -RR (Round-Robin) -Multilevel Queue -Multilevel Feedback Queue 1. FCFS ( First-Come, First-Served ) : 먼저 온 프로세스를 먼저 서비스해준다. p1 (Burst time : 24ms ), p2 ( Burst time : 3ms) , p3 ( Burst Ttme : 3ms ) 순으로 들어왔다고 가정해보자. p1은 아무도 안 기다렸으므로 0 p2는 24ms를 기다리고 p3은 27ms를 기다렸으니 평균 대기시간은 17ms이다. 만약 p3, p2, p1 순으로 왔..
-
백준(BOJ) 3085번 사탕 게임알고리즘 풀이/백준(Boj) 2019. 10. 27. 02:05
문제 : https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하 www.acmicpc.net 풀이 : 상하좌우 바꿀 수 있지만 위쪽이나 왼쪽 교환은 이전 칸에 오른쪽이나 아래쪽 교환으로 구할 수 있기 때문에 아래, 오른..
-
백준(BOJ) 1937번 욕심쟁이 판다알고리즘 풀이/백준(Boj) 2019. 10. 27. 01:37
문제 : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이 www.acmicpc.net 풀이 : 0,0부터 n n까지 모든 경우의 수를 조사하여 최대 길이를 찾아야 한다. 이때 한 y,x에서의 길이는 이미 구해진..
-
백준(BOJ) 2169번 로봇 조종하기알고리즘 풀이/백준(Boj) 2019. 10. 27. 00:37
문제 : https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 풀이 : 로봇은 왼쪽으로도 갈 수 있기 때문에 일반적인 메모이제이션 cache [y][x]는 최적의 값을 찾아주지 못한다. 따라서 cache 는 3가지 방향을 전부 다 잡아주어야 한다. 코드 ( C++ )
-
백준(BOJ) 14225번 부분수열의 합알고리즘 풀이/백준(Boj) 2019. 10. 25. 02:42
문제 : https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다. www.acmicpc.net 풀이 : S의 최대 크기는 20 이고 한 숫자당 10만이하 이니 합에 최대값은 20 * 100000일것이다. 이 배열을 잡은 후에 재귀호출을 통해서 각 부분 수열을 더하거나 지나치거나 하여 모든 경우의 수를 체크해주자. 그 후 1부터 시작해서 값이 false라..
-
백준(BOJ) 2151번 거울 설치알고리즘 풀이/백준(Boj) 2019. 10. 22. 02:22
문제 : https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (1 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다. www.acmicpc.net 풀이 : #와 !을 정점으로 하고 상하좌우로 거울이나 문이 만날수 있다면 간선을 이어주자. 그 후 처음 #에서 마지막 #으로 가는 최단거리 d를 구하자. 이는 BFS를 이용해서 풀어주자. ex) 예제 코드 ( C++ )
-
백준(BOJ) 2422번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데알고리즘 풀이/백준(Boj) 2019. 10. 18. 15:24
문제 : https://www.acmicpc.net/problem/2422 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 문제 한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다. 입력 첫째 줄에 정수 N과 M이 주어진다. N은 www.acmicpc.net 풀이 : 아이스크림의 선택은 3가지 이니 200 * 200 * 200 총 800만 가지의 경..