이것저것 공부 기록하기

문제링크 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제설명 문제풀이

문제링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제설명 짝수 N명의 사람들을 스타트 팀과 링크 팀으로 나누었을 때, 팀 간 능력치를 최소화하는 문제이다. S는 팀의 i번 사람과 j번 사람이 같은 팀에 속했을 때의 능력치를 담은 2차원 배열이며, S_ij 와 S_ji 는 다르게 취급되므로 그 경우를 각각 따져주기 위해 이중 for 문으로 각 능력치를 구하여 팀 전체의 능력치에 더해줬다. 문제풀이 combinations 를 활용해서 팀 조합을 만들고, 스타트..

문제링크 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제설명 N개로 이루어진 수열과 N-1개의 연산자가 주어질 때, 수식을 만들어 최댓값과 최솟값을 구하는 문제이다. 이 때 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 하며, 나눗셈은 정수 나눗셈으로 몫만 취한다. 또한, 음수를 양수로 나눌 때에는 양수로 바꾼 뒤 몫을 취한 후 그 몫을 음수로 바꾸어야 한다. 예를 들어..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 문제설명 문제풀이 def promising(i, col): # 대각선 방향 겹치는지 체크 k = 1 flag = True while k < i and flag: if col[i] == col[k] or (abs(col[i]-col[k]) == i-k): flag = False k += 1 return flag def nqueen(i,n,c..

문제링크 https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제설명 앞서 풀이했던 N과 M 시리즈 문제(위 링크 참고)와 유사하다. [Algorithm] 1일1솔 - 백준 15649 N과 M (1) (python3) 문제링크 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분..

문제링크 https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제설명 앞서 풀이했던 15649번: N과 M(1), 15650번: N과 M(2) 문제와 유사하며, 문제의 조건이 약간 변형되었다. '같은 수를 여러 번 골라도 된다' 는 조건이 추가되었다. 이 조건으로 인해 해당 문제는 백트래킹으로 풀이하면 pruning 과정이 따로 필요없이 dfs로 경우의 수를 탐색해주면 된다. 또한, 경우의 수로 풀이하는 경우에는 중복순열을 이용해서 풀 수 있다...

문제링크 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제설명 앞서 풀이했던 15649번: N과 M(1) 문제와 유사하며, 문제의 조건이 약간 변형되었다. '고른 수열은 오름차순이어야 한다' 는 조건이 추가되었다. 백트래킹으로 풀이하면 pruning 과정에서 해당 조건을 추가해주면 된다. 또한, 경우의 수로 풀이하는 경우에는 오름차순 조건을 충족시킨다는 건 순서 상관없이 같은 수열로 취급한다는 의미이므로, 조합을 이용해서 풀 수 있다. 문..

문제링크 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제설명 자연수 N과 M이 주어졌을 때, '1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열' 조건을 만족하는 길이가 M인 수열을 모두 구하는 문제이다. 문제 분류는 백트래킹으로 되어있지만, 중복 없이 일정한 개수의 자연수가 담긴 수열을 구하며, 순서를 상관하여 수열을 다르게 취급한다는 점에서 순열을 이용해서 풀이할 수도 있다. 문제풀이 1. 순열 이 문제에서는 수열을 순서가 다..