hong_mok

백트래킹(Backtracking) 이란? 비선형 구조의 자료를 탐색할 때 깊이 우선 탐색(DFS) 방식으로 경로를 따라가다가, 조건을 확인하였을 때 그 경로가 해결책으로 이어질 것 같지 않다면 더이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄이는 방식이다. 이를 가지치기(Prunning) 라고 한다. 깊이 우선 탐색(DFS) 방식과 유사하지만 DFS는 가능한 모든 경로를 추적하는데 비해서 백트래킹은 가지치키를 통해 불필요한 경로를 차단한다. 일반적으로는 경우의 수가 줄어들지만 최악의 경우에는 여전히 많은 탐색을 요하므로 처리가 불가능하다. 절차 트리의 깊이 우선 탐색을 실시한다. 조건을 확인하여 각 노드가 유망한지(Promising) 점검한다. 노드가 유망하지 않다면, 그 노드의 부모 노드로 돌아가..

https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호..

이진 검색(Binary Search) 자료의 가운데 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법이다. 원하는 값을 찾을 때 까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가며 검색한다. 이때, 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다. 알고리즘 - 자료의 중앙에 있는 원소를 고른다. - 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다. - 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다. - 찾고자 하는 값을 찾을 때 까지 위의 과정을 반복한다. 위의 알고리즘을 그림으로 나타내면 다음과 같다. 파이썬 코드 def binary_sear..

2108번: 통계학 문제 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 1. 산술평균 : N개의 수들의 합을 N으로 나눈 값 2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값 4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. 5 1 3 ..

딕셔너리 정렬하기 파이썬 내장 함수인 sorted와 lambda 를 사용하여 딕셔너리를 정렬할 수 있다. 이때, dict.items() 함수를 사용하여 인자로 전달해준다. key로 정렬하기 sorted 함수 인자로 key=lambda x : x[0] 을 전달한다. dict1 = {'a': 1, 'd': 2, 'c': 4, 'b': 3} sorted_dict = dict(sorted(dict1.items(), key=lambda x : x[0])) print(sorted_dict) {'a': 1, 'b': 4, 'c': 3, 'd': 2}Value로 정렬하기 sorted 함수 인자로 key=l..

별 찍기 - 10 문제 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다. 입력 첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3^k이며, 이때 1 ≤ k < 8이다. 27 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. *************************** * *..

터렛 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다. 한 줄에 x1, y1, r1, x2, y2, r2가 주어진다. x1, y1, x2, y2는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이고, r1, r2는 10,000보다 작거나 같은 자연수이다. 3 0 0 13 40 0 37 0 0 3 0 7 4 1 1 1 1 1 5 출력 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. 2 1 0 생각 두 점의 좌표 ( (x1, y1), (x2, y2) )가 주어지고, 두 점으로부터 목표물의 거리(r1, r2) 가 주어진다. 이때 목표물이 있을 ..

python에서 json 파일 불러오기 import json FILE_DIR = "data/data1.json" # 파일 경로 file_json = open(FILE_DIR, encoding=&#39;UTF8&#39;) file_data = json.load(file_json)

Fly me to the Alpha Centauri 문제 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동시기에 k광년을 이동하였을 때는 ..

파이썬에서 보통 입력을 받을때는 Input함수를 사용하였는데, sys 모듈을 import 한 후 sys.stdin.readline() 함수를 사용하면 빠르게 입력 받을 수 있다. - 백준 15552번 문제 참고 import sys # n = input() n = sys.stdin.readline() print(n) sys.stdin.readline() 함수 사용 시 개행문자를 같이 입력받기 때문에, 개행문자를 제외하고 입력을 받기 위해서는 뒤에 .rstrip() 을 추가해주면 된다. import sys n = sys.stdin.readline().rstrip() print(n) 입력을 여러번 받게 될 때 sys.stdin.readline() 이 조금 길 수도 있어서 변수에 함수 정보를 저장하여 사용할 수..