파게로그

문제 링크: 15652번 백트래킹 기본 4 https://www.acmicpc.net/problem/15652 cur = i를 통해 현재 숫자를 저장해주고, depth가 증가했을 때 그 숫자부터 삽입할 수 있도록 한다. 백트래킹 기본 1을 참고하면 좋다. def print_list(l): for item in l: print(item, end = ' ') print() def select(n, m, res, cur, depth): if depth == m: print_list(res) return for i in range(cur, n+1): res[depth] = i cur = i select(n, m, res, cur, depth+1) n, m = map(int, input().split()) res..

문제 링크: 15651번 N과 M (3) https://www.acmicpc.net/problem/15651 depth를 통해 재귀의 깊이를 알 수 있는 것은 굉장히 편리하다! 백트래킹 기본 1을 참고하면 좋다. def print_res(res): string = "" for i in res: string += str(i) + " " print(string) def select(m, res, depth): if depth == m: print_res(res) return for i in range(1, n+1): res[depth] = i select(m, res, depth+1) n, m = map(int, input().split()) res = [0]*m select(m, res, 0)

문제 링크: 15650번 N과 M (2) https://www.acmicpc.net/problem/15650 백트래킹 기본 1의 코드를 참고해서 보면 좋다. def select(arr, n, m, current, depth): # arr를 다 채웠으면 print 후 return if depth == m: string = "" for i in arr: string += str(i) + " " print(string) return # arr를 다 채우지 못했더라도 범위를 벗어나면 return if current > n: return # current를 arr에 저장할 때 arr[depth] = current select(arr, n, m, current+1, depth+1) # current를 arr에 저장..

문제 링크: 15649번 N과 M (1) https://www.acmicpc.net/problem/15649 1부터 n까지의 숫자 중 방문하지 않은 숫자에 대해서 방문 처리를 하고, 그 숫자를 길이가 m인 arr의 depth에 해당하는 자리에 저장해준다. 그리고 depth를 증가시켜 또 다른 방문하지 않은 숫자에 대해서 이러한 과정을 반복한다. depth가 1부터 시작한다고 하면, depth는 지금 몇 번째 깊이의 숫자를 고르고 있느냐에 대해서 나타낸다. 즉 depth == m까지 계속해서 증가해야 하고, depth > m일 때 arr는 출력되며, 그 뒤의 경우는 promising하지 않으므로 return한다. import java.util.Scanner; public class Main { public..

CSP(제약 만족 문제, Constraint Satisfaction Problems)란 무엇인가? CSP는 변수가 가지는 도메인 내에서, 주어진 제약 조건을 만족하는 해를 찾는 문제를 말한다. 제약 조건을 만족하는 상태가 CSP의 목적 상태이다. 백트래킹 또는 퇴각검색이란 제약 만족 문제(CSP, Constraint Satisfaction Problems)를 위해 해결하여 쓰이는 일반적인 문제 풀이 기법이다. Backtracking algorithm 특징 첫째로, 제약 조건을 만족시키지 않는 경우 탐색 범위에서 제외되므로 탐색 공간을 줄일 수 있다. 전수검사(exhaustive search)에 해당하지만 가지치기(pruning)가 발생하기에 엄밀한 의미에서 전수검사는 아니다. 둘째로, 모든 상태가 제약 ..

문제 링크: 11650번 좌표 정렬하기 https://www.acmicpc.net/problem/11650 Pos라는 클래스를 새로 생성했기에, Comparator나 Comparable 둘 중 어느 것을 써도 관계없다. import java.util.*; class Pos { int x; int y; public Pos(int x, int y) { this.x = x; this.y = y; } public String toString() { return x + " " + y; } } public class Main { public static void main(String[] args) { /* 입력 */ Scanner sc = new Scanner(System.in); int n = sc.nextInt..

문제 링크: 2108번 통계학 https://www.acmicpc.net/problem/2108 입력이 500,000개인데 계속해서 시간 초과가 나서 이상하게 생각했는데, 범인은 다른 게 아니라 입력의 문제였다. 개수가 조금만 많다 싶어도 바로 sys.stdin.readline()을 사용하도록 하자! import sys ### 입력 n = int(input()) ls = [] sum = 0 cnt_pos = [0]*(4000+1) # 양수 세기(0 포함) cnt_neg = [0]*(4000+1) # 음수 세기 for i in range(n): t = int(sys.stdin.readline()) ls.append(t) # 총합 계산해주기 sum += t # 양수 또는 음수 빈도 체크 if t>=0: cn..

문제 링크: 11651번 좌표 정렬하기 2 https://www.acmicpc.net/problem/11651 정렬에 대해서 특별한 것은 없다. 다만 nextInt()가 입력받는 것은 정수까지이다. 정수 뒤의 \n은 바로 뒤의 nextLine()이 입력받기에 Exception이 발생한다. 따라서 nextLine()을 사용하기 전, nextLine()을 한 번 더 호출하여 \n를 처리하도록 한다. import java.util.*; class Pos implements Comparable { int x; int y; public Pos(int x, int y) { this.x = x; this.y = y; } public String toString() { return x + " " + y; } publi..