https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백트래킹 문제 중 하나인 스도쿠 문제입니다. 9x9 격자가 주어졌을때 조건에 따라 빈칸을 다 채우는 것이 스도쿠 입니다. 조건은 다음과 같습니다. 1. 모든 칸에는 1~9사이의 숫자가 들어간다. 2. 행 9칸에는 1~9사이의 숫자가 중복되면 안된다. 3. 열 9칸도 마찬가지로 1~9사이의 숫자가 중복되면 안된다. 4. 3x3 격자로 나누게된다면 총 9개의 구역이 생기는데 빈칸을 채우려는 숫자의 구..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹 알고리즘에서 유명한 문제입니다. 체스판에서 퀸은 행,열 대각선을 자유롭게 움직일 수 있습니다. N x N 체스판에서 퀸을 놓아 퀸끼리 서로 공격 할 수 없게 설계하도록하는 모든 경우의 수를 구하는 것이 문제입니다. 조건 1. 같은 행과 열에는 퀸이 두 개 이상 존재 할 수 없다. (한 행과 한 열에서는 퀸 한개만 존재 할 수 있습니다) 2. 대각선에서도 퀸은 두 개 이상 존재 할 수 없다. 1번 조건에는..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net DFS를 이용한 백트래킹 문제입니다. 조건과 부합하면 화면에 출력하고 return하여 백트래킹 해줍니다. visited 배열로 중복사용되지 않게 처리해주고 return이 되면 다시 마지막에있는 숫자를 pop_back()과 vistied[i] = false로 미 방문 처리하여 다음 순열에서 사용가능하게 처리합니다. 전체소스코드 #include #include #include #include usi..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 재귀를 이용한 분할 정복 문제입니다. 색종이가 생기지 않을시(모두 파란색이거나 모두 흰색이거나) 해당 색종이를 다시 사등분하여 흰색 색종이와 파란색 색종이의 갯수를 골라내는 문제입니다. 항상 큰 색종이에서 작은 색종이 4개가 생기기 때문에 분할정복을 사용해 1개단위 까지 재귀를 통해 함수를 반복해서 호출하여 색종이가 완성된다면 return 하는 방식으로 함수를 구현해주었..

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.제한 사항 works는 길이 1 이상, 20,000 이하인 배열입니다. works의 원소는 50000 이하인 자연수입니다. n은 1,000,000 이하인 자연수입니다. 입출력 예 worksnresult [4, 3, 3] 4 12 [2, 1, 2] 1 6 [1,1] 3 0 입출력 예 ..

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를..