0 만들기

Oct 23, 2020 in Algorithm, Sorting

문제유형 : 재귀
설명
1. 자연수 N의 범위(3 <= N <= 9)가 한정적이므로 완전 탐색으로 문제 해결
2. 수의 리스트와 연산자의 리스트로 분리하여 모든 경우의 수를 해결
3. 가능한 모든 경우를 고려하여 연산자 리스트를 만들 때 재귀를 사용
4. 파이썬 eval() 함수를 이용하여 문자열 형태의 표현식을 계산한다.

풀이

import copy

def recursion(array, n):
    if len(array) == n:
        operators_list.append(copy.deepcopy(array))
        return
    array.append(' ')
    resursive(array, n)
    array.pop()

    array.append('+')
    recursive(array, n)
    array.pop()

    array.append('-')
    recursive(array, n)
    array.pop()

test_case = int(input())

for _ in range(test_case):
    operators_list = []
    n = int(input())
    recursive([], n-1)

    integers = [i for i in range(1, n+1)]

    for operators in operators_list:
        string = ""
        for i in range(n-1):
            string += str(integers[i]) + operators[i]
        string += str(integers[-1])
        if eval(string.replace(" ", "")) == 0:
            print(string)
    print()

Comment and share

Z

Oct 23, 2020

백준 1074 : 문제링크

문제유형 : 재귀
설명
1. 2^N의 사각형을 2^(N-1)의 사각형 4개로 나누어 재귀로 해결
2. N = 2일때 까지 분할

풀이

def solve(n, x, y): global result
    if n == 2:
        if x == X and y == Y:
            print(result)
            return
        result += 1
        if x == X and y + 1 == Y:
            print(result)
            return
        result += 1
        if x + 1 == X and y == Y:
            print(result)
            return
        result += 1
        if x + 1 == X and y + 1 == Y:
            print(result)
            return
        result += 1
        return
        solve(n / 2, x, y)
        solve(n / 2, x, y + n / 2)
        solve(n / 2, x + n / 2, y)
        solve(n / 2, x + n / 2, y + n / 2)

result = 0
N, X, Y = map(int, input().split(' ')) 
solve(2 ** N, 0, 0)

Comment and share

피보나치 수

Oct 23, 2020 in Algorithm, Recursive

백준 1074 : 문제링크

문제유형 : 재귀
설명
- 2^N의 크기의 사각형을 2^(N-1)의 사각형 4가지 부분으로 나눠서 재귀적으로 해결

풀이

실패 코드

def solve(n, x, y):
    global result
    if n == 2:
        if x == X and y == Y:
            print(result)
            return
        result += 1
        if x == X and y + 1 == Y:
            print(result)
            return
        result += 1
        if x + 1 == X and y == Y:
            print(result)
            return
        result += 1
        if x + 1 == X and y == Y:
            print(result)
            return
        result += 1
    solve(n / 2, x, y)
    solve(n / 2, x, y + n/2)
    solve(n / 2, x + n / 2, y)
    solve(n / 2, x + n / 2, y + n / 2)

result = 0
N, X, Y = map(int, input().split(' '))
solve(2 ** N, 0, 0)

Comment and share

수 정렬하기3

Oct 22, 2020 in Algorithm, Sorting

백준 10989 : 문제링크

문제유형 : 정렬
설명
- 데이터의 개수가 최대 10000000개
- 계수 정렬 사용
  - 배열의 인덱스를 특정한 데이의 값으로 여기는 방식
  - 배열의 크기는 데이터의 범위를 포함할 수 있도록 설정
  - 데이터가 등장한 횟수만큼 각 인덱스의 배열 값을 증가시킴

풀이

import sys

n = int(sys.stdin.readline())
array = [0] * 10001

for i in range(n):
    data = int(sys.stdin.readline())
    array[data] += 1

for i in range(10001):
    if array[i] != 0:
    for j in range(array[i]):
        print(i)

Comment and share

좌표 정렬하기

Oct 22, 2020 in Algorithm, Sorting

백준 11650 : 문제링크

문제유형 : 정렬
설명
1. 튜플로 두 개의 데이터를 묶어서 저장
2. 파이썬 기본 정렬 알고리즘은 튜플의 인덱스 순서대로 오름차순 정렬한다.

풀이

n = int(input())

array = []

for _ in range(n):
    x, y = map(int, input().split)
    arrray.append((x, y))

array = sorted(array)

for i in array:
    print(i[0], i[1])

Comment and share

나이순 정렬

Oct 22, 2020 in Algorithm, Sorting

백준 10814 : 문제링크

문제유형 : 정렬
설명
1. 튜플로 두 개의 데이터를 묶어서 저장
2. sorted 함수로 정렬, lambda로 첫번째 정렬 기준값을 정함
3. 튜플로 저장하면 첫번째 정렬 기준값이 동일할 때 다음 값으로 자동 정렬

풀이

n = int(input())

array = []

for _ in range(n):
    input_data = input().split(' ')
    array.append((int(input_data[0])), input_data[1])

array = sorted(array, key=lambda x : x[0])

for i in array:
    print(i[0], i[1])

Comment and share

소트인사이드

Oct 21, 2020 in Algorithm, Sorting

백준 1427 : 문제링크

문제유형 : 정렬
설명
1. 9 에서 0 까지 차례대로 내려가면서 확인
2. 각 숫자의 개수를 계산해서 출력

풀이

선택 정렬

array = input()

for i in range(9, -1, -1):
    for j in array:
        if int(j) == i:
            print(i, end='')

Comment and share

수 정렬하기

Oct 21, 2020 in Algorithm, Sorting

백준 2750 : 문제링크

문제유형 : 정렬
설명
- 선택 정렬로 풀이
- sort함수로도 해결 가능

풀이

선택 정렬

n = int(input())
array = list()

for _ in range(n):
    array.append(int(input()))

for i in range(n):
    min_index = i
    for j in range(i+1, n):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]

for i in array:
    print(i)

기본 라이브러리

n = int(input())
array = list()

for _ in range(n):
    array.append(int(input()))

array.sort()

for i in array:
    print(i)

Comment and share

수 찾기

Oct 21, 2020 in Algorithm, Hash

백준 4195 : 문제링크

문제유형 : 해시, 배열, 구현
설명
- python에서 dictionary 자료형으로 HASH 구현가능
- Union Find 알고리즘 이용

풀이

def find(x):
    if parent[x] == x:
        return x
    else:
        p = find(parent[x])
        parent[x] = p
        return parent[x]

def union(x, y):
    x = find(x)
    y = find(y)

    if x != y
        parent[y] = x
        number[x] += number[y]

test_case = int(input())

for _ in range(test_case):
    parent = dict()
    number = dict()

    f = int(input())

    for _ in range(f):
        x, y = input().split(' ')

        if x not in parent:
            parent[x] = x
            number[x] = 1
        if y not in parent:
            parent[y] = y
            number[y] = 1

        
        union(x, y)

        print(number[find(x)])

Comment and share

SHA-256

Oct 21, 2020 in Algorithm, Hash

백준 10930: 문제링크

문제유형 : 해시, 구현
설명

hashlib.sha256 함수로 SHA 256 해시를 구한다.

풀이

import hashlib

input_data = input()
encoded_data = input_data.encode()
result = hashlib.sha256(encoded_data).hexdigest()
print(result)

Comment and share

Yechan Kim