이것저것 공부 기록하기

문제링크 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://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/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제설명 배열이 아니라 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬하는 문제이다. 정렬문제이므로 어차피 문자열로 처리해야 했기에 입력값을 int로 변환하지 않고 문자열 타입 그대로 받았다. 그 후 sorted() 를 취해 문자열을 정렬한 후, "".join() 을 사용했다. 참고 python에서 문자열 자체를 정렬하려면, s.sort()를 쓰면 안된다. string의 경우 첫글자의 주소값으로 참조를 하기에 원본이 변경되면 안되므로, str type에 sort() ..

문제링크 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제설명 홀수 N개의 값들에 대해 산술평균, 중앙값, 최빈값, 범위를 차례로 구하는 문제로 까다로운 조건이 없었다. 최빈값이 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력해야 하는 조건이 주어졌다. 이 조건에 대해서는 Counter의 most_common으로 2개까지만 구한 후 케이스를 구분하는 방식을 취했다. most_common으로 최빈값을 구한다면, 중앙값 뿐 아니라 최빈값에 대해서도..

문제링크 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제설명 시간 제한과 메모리 제한이 있는 문제이며, 특히 메모리 제한이 빡센 문제로 단순하게 sort로 풀고 PyPy3로 돌려서 해결되는 문제가 아니다. 앞에서 블로깅했던 수 정렬하기 2(https://www.acmicpc.net/problem/2751) 문제는 메모리 제한이 256MB 였지만, 이번 문제는 메모리 제한이 8MB이므로 정렬이라는 접근보다는 새로운 접근으로 풀어야 했다. '수 정렬하기 2' 처..