본문 바로가기

알고파

[알고스팟/ALGOSPOT] 11. ORIVIRUS 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 이번 문제는 오리바이러스라는 문제입니다! 저는 흠.. 약간 BFS같은 느낌으로 풀어보았습니다~ 문제 개요 테스트 케이스가 입력으로 주어지면 먼저 오리의 수 N이 주어지고 NxN 오리들끼리의 친구관계가 주어집니다. 그리고 여기서 또 테스트 케이스가 나와 개수만큼 처음 바이러스을 갖는 오리의 번호가입력됩니다. 그럼 여기서 처음 2마리의 오리가 바이러스를 다 퍼트렸을 때 감염된 오리의 수를 구해주시면 됩니다. 문제 풀이 먼저 오리들의 친구 관계를 인접 행렬 리스트로 바꾸어 줍니다. 인접 행렬 리스트란 0번째 열에 연결된 노드의 개수, 그리고 1~노드의 개수까지 연결된 노드의 번호를 저장합니다. 인접 행렬 리스트도 따로 블로그에 포스팅하겠습니다. 이렇게.. 더보기
[알고스팟/ALGOSPOT] 10. PACKING 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 이번 10번 문제는 PACKING이라는 문제입니다.!! 이 문제는 동적계획법 대표 문제입니다. 가방 문제라고도 불리구요! 문제 개요 입력에서 테스트 케이스가 주어집니다. 테스트 케이스당 물건의 개수 N과 가방의 용량 W가 주어집니다 그리고 N개의 줄에 걸쳐 물건의 이름과 부피, 절박도(가치)가 주어집니다.N개의 물건을 용량내로 최대한의 가치, 절박도로 채워야 하는 것이 목표입니다. 최대 가치와, 물건 개수, 물건의 이름들을 출력해야 합니다. (경로 추적이 필요합니다~) 문제 풀이 최대 가치만 구하라 하면 동적계획법만을 사용하면 되지만, 물건의 개수와 이름을 구해야하기 때문에 추가적으로 재귀함수를 이용하여 경로를 추적합니다. 동적 계획법 부분 점화.. 더보기
[알고스팟/ALGOSPOT] 9. JOSEPHUS 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 이번 문제는 JOSEPHUS라는 문제로!! 원탁의 기사같은 연결리스트 문제입니다!! 문제 개요 입력에서 테스트 케이스가 주어지면 테스트 케이스마다 N명의 사람과 1번이 죽었을 때 그 사람으로 부 터 몇 번째인 사람이 죽을 K가 주어집니다. 1번부터 시작하여 차근차근 죽어가고 마지막으로 살아남는 2명의 사람을 출력하는 문제가 되겠습니다. 문제 풀이 N개의 입력을 받고 1번부터 N번까지 연결리스트를 구축을 합니다. 그러면 위치는 마지막 N번이 되어있습니다. pre를 N번, cur을 1번으로 하게끔 1~n을 동적할당 합니다. 여기서부터 pre의 next를 cur의 next로 바꾸어주어 1번을 지우고 pre는 그대로, cur은 다음으로 넘어갑니다. 총개.. 더보기
[알고스팟/ALGOSPOT] 8. CONCERT 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 이번 문제는 동적계획법을 이용하여 해결하는 CONCERT라는 문제입니다. 문제 개요 먼저 입력에서 테스트 케이스가 주어지면 테스트 케이스 당 2줄씩 입력이 주어집니다. 첫 번째 줄에는 곡의 개수, 시작 볼륨, 최대 볼륨이 2번째 줄에는 곡의 개수만큼의 볼륨이 주어집니다. 여기서 각 볼륨을 키우든 줄이든 하여 볼륨이 0보다 작지 않고, VM보다 크지 않는 것들 중에서 가장 큰 값을 출력하라는 문제입니다. 문제 풀이 이 문제는 동적계획법을 어떻게 활용할까를 생각한다면 해법을 찾을 수 있다. 각 단계별로 볼륨을 만들 수 있는 것들을 모두 어떻게 저장을 할 것인가에 주목을 하여 생각을 해야 한다. 글씨가 읽기 힘드실텐데..ㅠㅠ 죄송합니당 먼저 입력을 받.. 더보기
[알고스팟/ALGOSPOT] 7. NQUEEN 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 이번 문제는 NQUEEN이라는 문제입니다. 재귀함수를 이용하여 백트래킹을 구현하였습니다. 문제 개요 NxN 크기의 체스판에 N개의 킨을 서로 공격할 수 없도록 올려놓는 퍼즐입니다. 테스트케이스가 주어지고, 테스트 케이스마다 체스판의 크기 N이 입력됩니다. 여기서 N개의 퀸을 배치하는 가지수를 출력해야 합니다. 문제 풀이 N개의 퀸을 배치해야 함으로, 한 줄에는 한 개의 퀸만이 들어가야 됩니다. 이를 이용하여 첫 행에 1~N열에 퀸을 배치하고 배치하였을 때 퀸의 이동경로를 체크합니다. 체크는 chk[][]라는 배열을 만들어 퀸의 이동경로에 포함되면 1을 아니면 0으로 입력합니다. 2번째 행부터 재귀함수를 이용하여 1열~N열 까지의 칸중에서 체크되지.. 더보기
[알고스팟/ALGOSPOT] 6. BOARDCOVER 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 6번 문제는 BOARDCOVER라는 문제입니다! 저는 이 문제를 재귀함수로 DFS(깊이 우선 탐색법)를 구현하여 풀었습니다. 문제 개요 입력에서 테스트 케이스가 주어지면 하나의 테스트 케이스당 (NxM)행렬의 게임판이 주어집니다. 이 게임판에서 '#'은 블록이 있는 부분이고, '.'은 블록이 없는 부분입니다. 그럼 저희는 블록이 없는 부분 '.'을 '#'으로 채워주어야 합니다! 블록의 개수는 ㄱ, ㄴ과 ㄱ, ㄴ의 90도 회전한 블록 4개가 있습니다. 문제 풀이 재귀함수를 이용하여 DFS를 구현하였습니다. 먼저 입력을 받을 때 블록이 없는 부분 '.'부분을 추출해 놓으면 속도를 더 빠르게 할 수 있습니다. 탐색도 쉽게 할 수 있구요! 예를 들어 입.. 더보기
[알고스팟/ALGOSPOT] 5. CSBASEBALL 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 5번 문제는 CSBASEBALL이라는 문제입니다! 문제 개요 입력에 테스트 케이스가 주어지고, 하나의 테스트 케이스마다 2개의 입력이 들어온다. 첫 입력 A는 CS야구팀의 점수, B는 화나 핀토스팀의 점수가 된다.(이름 참..ㅋㅋ) 그러면 여기서 A팀이 B팀을 이길 수 있게 하는 안타 수를 구하는 것이 문제다. 문제 풀이 동점 상황에서는 1점을 더 얻으면 되므로 4개의 안타가 필요하겠고 지고 있는 상황에서는 4개의 안타에 두 A, B의 차이의 합이 필요하겠다. (4개의 안타 이후에는 안타 하나당 1점을 얻을 수 있다.) 이기고 있는 상황에서는 안타가 필요없다. 간단한 구현문제였습니다! 문제 출처 : https://algospot.com/judge.. 더보기
[알고스팟/ALGOSPOT] 4. CLOCKSYNC 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 이번 문제는 CLOCKSYNC라는 문제인데요~ 12시 3시 6시 9시로 되어있는 시계를 스위치를 이용해서 모두 12시로 바꾸는 최소로 눌러야할 스위치의 개수를 구하라 라는 것이에요. 모두 12시로 바꿀 수 없다면 -1을 출력해야 하구 시간초는 10S가 되겠어요~ 먼저 이 문제의 올바른 풀이법은 BFS(너비우선탐색)라고 생각해요~ 흠 먼저 기존 상태에서 사용 할 수 있는 스위치를 판별을 하여 가지를 뻗어나가요. 가지를 뻗다 모두 12시가 되면 그 방법이 항상 최소 스위치 개수가 되기 때문에 그 수를 출력해요. 대략적인 그림을 그렸는데 저기 트리의 맨윗부분 기존에서 예를 들어 스위치를 5개 사용하였다면 다른 형태의 5개의 정보가 QUEUE 배열에 들.. 더보기
[알고스팟/ALGOSPOT] 3. STRJOIN 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 알고스팟 제 3번째 문제는 STRJOIN이라는 문제입니다. N개의 문자열을 순서와 상관없이 합쳐서 한 개의 문을 만들 때 가장 적은 비용을 구하라는 문제가 됩니다. 이 문제를 생각해보면 항상 제일 작은 문자열끼리 서로 결합을 시키고 또 그다음 작은 문자열끼리 결합을 시켜야 합니다. 그래야 가장 작은 비용으로 결합을 시킬 수 있습니다. 그래서 1. N개의 문자열 길이를 오름차순 정렬을 한다. 2. 가장 작은 2개의 문자열을 결합시켜 문자열 길이를 갱신한다. 3. 나머지 N-1개의 문자열 길이를 오름차순 정렬을 한다. 4. 2~3번 과정을 반복하여 마지막 비용 값을 출력한다. 이런 과정이 되겠습니다. 문제 출처 : https://algospot.co.. 더보기
[알고스팟/ALGOSPOT] 2. MERCY 알고리즘 알고파! 알고라파덕 안녕하세요~ 알고라파덕입니다! 알고스팟에는 튜토리얼급 구현 문제가 9문제가 있습니다! 그중에서 첫 번째 튜토리얼 문제인 MERCY 문제를 봐봅시다. 입력에 10보다 작은 INTEGER 정수가 들어오면 그 개수만큼 Hello Algospot!을 출력을 해야합니다. 1. 임의의 개수 정수를 하나의 변수로 입력받는다. N 2. FOR문이나 WHILE문으로 Hello Algospot!을 출력한다. 튜토리얼급 구현 문제는 되게 간단가 많은데요. 얼른 포스팅하고 고급 알고리즘에 대해 설명을 하겠습니다~ 알고파! 알고라파덕! 문제 출처 : https://algospot.com/judge/problem/read/MERCY 더보기

티스토리툴바