Study Log

20200308 알고리즘

1. Anagram ( by dict )

Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아 나그램이라고 합니다. 예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재 배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다.

길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세 요. 아나그램 판별시 대소문자가 구분됩니다.

▣ 입력설명 첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다. 단어의 길이는 100을 넘지 않습니다.

▣ 출력설명 두 단어가 아나그램이면 “YES”를 출력하고, 아니면 ”NO”를 출력합니다.

▣ 입력예제 1

AbaAeCe

baeeACA

▣ 출력예제 1

YES

Solution

import sys
sys.stdin = open("input40.txt", "rt")

p1 = dict()
p2 = dict()
for a in input():
    p1[a] = p1.get(a, 0) + 1

for b in input():
    p2[b] = p2.get(b, 0) + 1

if p1 == p2:
    print('YES')
else:
    print('NO')

2. Anagram ( by list )

문제는 1번과 같음

Solution

import sys
sys.stdin = open("input41.txt", "rt")

a1 = input()
a2 = input()
def hash_func(x):
    if x.isupper():
        return ord(x)-65
    else:
        return ord(x)-97+26
h1 = [0] * 52
h2 = [0] * 52
for x in a1:
    h1[hash_func(x)] += 1
for x in a2:
    h2[hash_func(x)] += 1

for i in range(52):
    if h1[i] != h2[i]:
        print('NO')
        break
else:
    print('YES')
  • 아스키코드 소문자는 97~122
  • 대문자는 65~90

3. 최소힙

최소힙은 완전이진트리로 구현된 자료구조입니다. 그 구성은 부모 노드값이 왼쪽자식과 오른 쪽 자식노드의 값보다 작게 트리를 구성하는 것입니다. 그렇게 하면 트리의 루트(root)노드는 입력된 값들 중 가장 작은 값이 저장되어 있습니다. 예를 들어 5 3 2 1 4 6 7순으로 입력되 면 최소힙 트리는 아래와 같이 구성됩니다.

최소힙 자료를 이용하여 다음과 같은 연산을 하는 프로그램을 작성하세요. 

1. 자연수가 입력되면 최소힙에 입력한다.
2. 숫자 0 이 입력되면 최소힙에서 최솟값을 꺼내어 출력한다.(출력할 자료가 없으면 -1를 출력한다.) 
3. -1이 입력되면 프로그램 종료한다.

▣ 입력설명 첫 번째 줄부터 숫자가 입력된다. 입력되는 숫자는 100,000개 이하이며 각 숫자의 크기는 정 수형 범위에 있다.

▣ 출력설명

  1. 연산을 한 결과를 보여준다.

▣ 입력예제 1

5
3
6
0
5
0
2
4
0
-1

▣ 출력예제 1 

3
5
2

Solution

import sys

class Heap:
    def __init__(self):
        self.data = [None]

    def insert(self, item):
        self.data.append(item)
        i = len(self.data) - 1
        while i > 1:
            if self.data[i] < self.data[(i // 2)]:
                self.data[i], self.data[(i // 2)] = self.data[(i // 2)], self.data[i]
            else:
                break

    def remove(self):
        if len(self.data) > 1:
            self.data[-1], self.data[1] = self.data[1], self.data[-1]
            data = self.data.pop()
            self.min_heapify(1)
        else:
            data = None
        return data

    def min_heapify(self, i):
        left = 2 * i
        right = 2 * i + 1
        smallest = i
        if left < len(self.data) and self.data[i] > self.data[left]:
            smallest = i
        if right < len(self.data) and self.data[left] > self.data[right]:
            smallest = i
        if smallest != i:
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
            self.min_heapify(smallest)


sys.stdin = open("input42.txt", "rt")
heap = Heap()
while True:
    i = int(input())
    if i == -1:
        break
    elif i == 0:
        min = heap.remove()
        print(min)
    else:
        heap.insert(i)

Solution2 ( heapq 이용 )

import sys
import heapq as hq
sys.stdin = open("input42.txt", "rt")

a = []
while True:
    n = int(input())
    if n == -1:
        break
    if n == 0:
        if len(a) == 0:
            print(-1)
        else:
            print(hq.heappop(a))
    else:
        hq.heappush(a, n)
  • heapq 는 기본적으로 최소힙으로 작동한다.

4. 최대힙

힙만 최대힙으로 바꾸고 문제는 같음

Solution ( Class 이용)

import sys
import heapq as hq
sys.stdin = open("input42.txt", "rt")

class Heap:
    def __init__(self):
        self.data = [None]

    def insert(self, item):
        self.data.append(item)
        i = len(self.data) - 1
        while i > 1:
            if self.data[i] > self.data[i//2]:
                self.data[i], self.data[i//2] = self.data[i//2], self.data[i]
            else:
                break

    def remove(self):
        i = len(self.data) - 1
        if i > 1:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            data = self.data.pop()
            self.max_heapify(1)
        else:
            data = None
        return data

    def get_length(self):
        return len(self.data)

    def max_heapify(self, i):
        left = 2*i
        right = 2*i+1
        largest = i
        size = len(self.data)
        if left < size and self.data[i] < self.data[left]:
            largest = left
        if right < size and self.data[largest] < self.data[right]:
            largest = right
        if largest != i:
            self.data[largest], self.data[i] = self.data[i], self.data[largest]
            self.max_heapify(largest)

heap = Heap()
while True:
    i = int(input())
    if i == -1:
        break
    elif i == 0:
        if heap.get_length() > 1:
            max = heap.remove()
            print(max)
        else:
            print(-1)
    else:
        heap.insert(i)

Solution2

import sys
import heapq as hq
sys.stdin = open("input42.txt", "rt")

a = []
while True:
    n = int(input())
    if n == -1:
        break
    if n == 0:
        if len(a) == 0:
            print(-1)
        else:
            print(-hq.heappop(a))
    else:
        hq.heappush(a, -n)
  • 넣을 때 부호를 - 로 바꾸면 최소힙 -> 최대힙이 되겠지

5. 이진수 만들기

10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요. 단 재귀함수를 이용 해서 출력해야 합니다.

▣ 입력예제 1

11

▣ 출력예제 1

1011

Solution

import sys
sys.stdin = open("input44.txt", "rt")


def DFS(x):
    if x == 0:
        return
    DFS(x//2)
    print(x%2, end='')


if __name__ == "__main__":
    n = int(input())
    DFS(n)
Written by@[HongDongUk]
공부한 것을 소소하게 적는 블로그.

GitHubFacebook