알고스팟 풀이 썸네일형 리스트형 [알고스팟/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 더보기 [알고스팟/ALGOSPOT] 1. HELLOWORLD 알고리즘 알고파 "알고라파덕" 제가 아는 알고리즘의 모든 정보를 다 담고 싶어서 시작하게 되었습니다~ 제가 풀은 알고스팟 문제들의 알고리즘적인 해법, 힌트를 공개 할 것이구요! 제가 배우고 사용하고 있는 알고리즘을 알고리즘을 공부하시는 분들께 도움이 될 수 있도록 알고리즘 강의 카테고리도 만들 예정입니다. 제가 푼 문제들을 중점으로 계속 포스팅을 할 것이구요! 개인적인 댓글이나 메시지로 소스 코드 질문, 아니면 저의 소스 코드를 보여드리려구 합니다! 그럼 첫 문제 HELLOWORLD부터 시작해서 쭉 해보겠습니다~ HELLOWORLD는 C언어 C++을 시작하시는 분들은 모두 보셨을 아주 기본적인 문제입니다. 입출력만 할 수 있다면 풀 수 있는 문제입니다. 1. 이름의 수를 한 개의 변수로 읽는다. N 2... 더보기 이전 1 2 3 다음
