알고라파덕 썸네일형 리스트형 [알고스팟/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 4 다음