MungGu Story

백준 1799, 비숍 문제설명 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 비숍문제는 백트래킹 대표 문제 중 하나인 N-Queen의 상위호환 문제입니다. 단순 백트래킹 개념만 사용할게 아니라, 비숍이라는 체스말의 특성까지 잘 활용해야 시간초과없이 수행해야 통과할 수 있는 문제입니다. 체스판의 크기와 비숍 말을 둘 수 있는 위치가 주어졌을때, 서로가 서로를 잡을 수 없게하는 조건을 충족하면서 가장 많은 비숍을 둘 수 있는 경우를 찾는 문제입니다. 체스판의 너비를 입력받은 후, N x N 크기의 체스판에 비숍 말을 둘..

오늘은 카카오 기출 알고리즘 문제 중, 재귀알고리즘 문제인 괄호변환문제를 풀어보도록 하겠습니다. 해당 문제에 대한 설명은 아래 링크를 참고하시면 되겠습니다. ▼ 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 해당 문제는 문제에서 설명한 대로 재귀코드를 구현하여 올바른괄호 형태를 만들어주고 반환해주면 되는 문제로, 문제설명만 제대로 읽어서 그래도 구현해준다면 풀 수 있는 문제였습니다. 그럼 곧바로 swift언어를 사용해서 해당문제를 풀어보겠습니다. 카카오 재귀알고리즘 문제, 괄호변환 swift 언어 풀이 먼저 ..

백준 10974번 모든 순열 예제설명 백준 10974번 모든순열은 N이 주어졌을 때 1부터 N까지의 수를 가진 모든 순열을 사전순으로 출력하는 문제입니다. 본 문제는 재귀 / 비재귀 방식으로 모두 풀 수 있는 문제입니다. 시간제한은 1초, 메모리제한은 256MB입니다. 모든ㄴ순열의 출력은 DFS, 백트래킹을 사용해서 출력해볼 예정입니다. N의 범위가 최대 8이므로, N!의 시간복잡도로도 충분히 풀리는 문제입니다. 최대 값인 8의 경우에도 최대 1억번의 연산에 미치지 않기 때문입니다. 위와 같이 N이 3일 경우, 1, 2, 3 세개의 숫자가 있는 모든 순열을 사전순, 개행단위로 출력해주면 되는 문제입니다. 이어서 swift언어와 DFS(깊이 우선 탐색) 백트래킹을 활용해서 문제를 풀어보도록 하겠습니다. 백..

백준 15683번, 감시 문제설명 오늘은 백준 15683, 감시 문제를 풀어보겠습니다. 감시 문제는 solved.ac기준, 골드5로 코딩테스트 기준 중후반에 나올 수 있는 수준의 문제입니다. 시간 제한은 1초, 메모리 제한은 512MB입니다. 제출횟수가 많은 검증된 문제(?)라고 할 수 있습니다. 해당 문제의 설명은 다소 복잡한 관계로, 본 포스팅에 적은 설명과 별개로 직접 해당 문제의 설명을 보고 이해하시길 권장드립니다. 문제설명은 가볍게 하고 넘어가겠습니다. 1x1크기의 정사각형들로 이루어진 N x M 크기의 직사각형 사무실이 있습니다. 이곳은 빈공간 0 / 벽 6 / cctv 1~5가 설치되어있습니다. cctv는 1, 2, 3, 4, 5의 다섯가지 종류의 cctv가 있고, 각 cctv가 감시할 수 ..