둔필승총

https://www.acmicpc.net/problem/7432

[풀이]

2가지 개념 : Trie와 DFS에 대한 개념에 대한 이해가 필요하다.

Trie 개념 : (link 첨부)

먼저 Node를 class로 만든다. Node는 key, data, children(자식)을 필드변수로 가지고 있다. 

Trie는 insert와 search함수를 가진다.

insert함수는 parameter로 path를 받는다. 이는 나중에 입력받은 값을 list형태로 넣어주기 위함이다. 

(예 : ['WINNT', 'SYSTEM32', 'CONFIG'] -> 이걸 path로 넣어준다)

여기서 path의 하나하나를 children에 넣어준다. 예를 들어 WINNT는 처음 넣는 것이니까 curr_node.children에 없으므로 curr_node.children['WINNT']에는 Node('WINNT')가 들어가게 된다. 그리고 현재 노드를 WINNT인 노드로 바꾸어 준다. 

위의 방법을 Trie의 원리로 구현한 것이다.

남은 것은 dfs를 이용해서 하나씩 출력만 하면 된다. 

사전 순으로 출력을 해야 하므로 sorted(trie.head.children)을 해준다. 이는 제일 첫번째 level 0의 children들이다.

dfe에서는 node.key를 level만큼 띄워서 출력해주고, node의 children을 재귀문을 통하여 출력해준다.

import sys
input = sys.stdin.readline

class Node:
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}

class Trie:
    def __init__(self):
        self.head = Node(None)

    def insert(self, path):
        curr_node = self.head
        for file in path:
            if file not in curr_node.children:
                curr_node.children[file] = Node(file)
            curr_node = curr_node.children[file]


def dfs_node(node, depth):
    print(' '*depth, node.key, sep='')
    for child in sorted(node.children):
        dfs_node(node.children[child], depth+1)

path_list = []
n = int(input())
trie = Trie()
for _ in range(n):
    trie.insert(input().rstrip().split('\\'))
# print(trie.head.children['WINNT'].children)

for node in sorted(trie.head.children):
    dfs_node(trie.head.children[node], 0)

알고리즘 문제를 풀다가 출력 부분을 해결할 때, 문자열을 join 함수로 사용하는 방법을 많이 보아서 알아볼려고 하였다.

join 함수

형태 : 구분자.join(리스트)

join 함수는 매개변수로 들어온 리스트에 있는 요소 하나하나를 합쳐서 하나의 문자열로 바꾸어 반환하는 함수이다.

• ''.join(리스트) ''.join(리스트)를 이용하면 매개변수로 들어온 ['a', 'b', 'c'] 이런 식의 리스트를 'abc'의 문자열로 합쳐서 반환해주는 함수인 것이다.
• '구분자'.join(리스트) '구분자'.join(리스트)를 이용하면 리스트의 값과 값 사이에 '구분자'에 들어온 구분자를 넣어서 하나의 문자열로 합쳐줍니다.

ex>

a = ['a', 'b', 'c', 'd', '1', '2', '3']
print(a)
print("".join(a))
# 'a', 'b', 'c', 'd', '1', '2', '3'
# abcd123

그래서 임의의 구분자를 리스트 요소 사이사이에 넣어줄 수도 있다.

# 원본 리스트
a = ['BlockDMask', 'python', 'join', 'example']
print(a)
print()
 
# 리스트를 문자열로 합치기
result1 = "_".join(a)
print(result1)
 
# 리스트를 문자열로 합치기
result2 = ".".join(a)
print(result2)

# ['BlockDMask', 'python', 'join', 'example']
# BlockDMask_python_join_example
# BlockDMask.python.join.example

https://www.acmicpc.net/problem/2193

[풀이]

먼저 조건을 생각해보면 처음 숫자는 무조건 1이 나와야 하고, 1은 연속해서 나올 수가 없고, 0에는 아무런 제약이 없다. 끝에 숫자가 1이면 그 다음은 무조건 0이라는 사실과 끝에 숫자가 0이면 0 또는 1 두가지가 나올 수 있다.

(처음에는 헷갈려서 그림을 그리면서 해보았다..)

끝에 숫자가 0인것과 1인것을 구분해서 구해보면

각각의 숫자는 피보나치 수열을 따른 다는 것을 알 수 있다(0,1,1,2,3,5,…)

따라서 Dynamic Programming으로 각각 구해서 해결할 수 있었다.

n은 1부터 가능하므로 배열을 만들때 주의해서 index 오류를 범하지 않도록 해야 한다.

[해결]

n=int(input())
zero=[0]*n
one=[0]*n
if n>1:
    zero[1]=1
    one[0]=1
    for i in range(2,n):
        one[i] = one[i-1]+one[i-2]
        zero[i] = zero[i-1]+zero[i-2]
    print(one[n-1]+zero[n-1])
elif n==1:
    print(1)

https://www.acmicpc.net/problem/13413

[풀이]

이 문제는 두 개의 배열을 입력받아서 첫번째 것을 두번째 배열과 똑같이 만들려고 하는 것이다. 방법은 2가지인데, W,B가 있으면 두개를 바꾸던가 W->B(혹은 B->W) 이런식으로 바꿀 수 있다. W,B 2개를 바꾸면 한번에 2자리가 해결되는 것이므로 위치 바꿀 수 있으면 이 방법이 최소 횟수일 것이다.

n = int(input())
    first = input()
    second = input()

    for i in range(n):
        if first[i]!=second[i]:
            arr.append(first[i])

내가 어려웠던 곳은 일단 서로 배열이 다르면 arr 배열에 저장해두었는데, 이걸 어떻게 해야 뒤집고 바꾸는 갯수를 다 알 수 있을까였다. 다른 곳이 짝수이면 나누기 2를 해주어서 몫을 더해줄까.. 이런 생각도 해보았는데

결국은 W랑 B가 있으면 더 큰 수를 출력하면 된다. arr에 입력받은 것이 만약 WBB라면 W랑 B는 서로 위치 바꾸어서 한 번이고, B하나 남은건 W로 바꾸어 줄테니까 총 개수가 2이다.

이건 결국 W랑 B중에 더 큰 수의 개수를 정답으로 하면 된다.

t = int(input())
arr=[]
ans=0
answer=[]
for i in range(t):
    n = int(input())
    first = input()
    second = input()

    for i in range(n):
        if first[i]!=second[i]:
            arr.append(first[i])
    if arr.count('B')>=arr.count('W'):
        ans=arr.count('B')
    else:
        ans = arr.count('W')
    answer.append(ans)
    arr=[]
for a in answer:
    print(a)

Search, Insert, Delete

- 자료구조의 가장 중요한 연산들

Array : 메모리의 연속된 공간

How to Store Items in an Array?

- Packed vs. Unpacked

: 배열이 항상 가득 찬 것은 아님

: 빈 자리를 한 쪽으로 모은다

- Sorted vs. Unsorted

: Item들이 정렬된 상태를 유지하느냐 아니냐

Packed, UnSorted : 아마도 가장 간단한 방법

 Packed, UnSorted 성능

: Search : O(n) // 전부 다 보는 수밖에 없다 되게느리다.

: Insert : [Search, O(n)], O(1) // Worst Case를 따진다 -> Search해야되기 떄문에 느리다(작업자체는 빠름)

: Delete : [Search, O(n)], O(1) // Sorting이 안되어있으니까 뒤에서 들고오면 된다.

-> Insert와 Delete는 보통 Search를 먼저 수행함.

Pack, Sorted-> 제일 성능이 나오는 케이스

: Binary Search가 가능해진다.

packing이 되어서 저장이 되어 있는데 Sorting만 되어있으니까. Search가 달라진다. 

: Item의 개수를 표시하는 변수가 따로 필요

근데 Insert, Delete는 packing이 되어 있고, insert할려니까 binary search를 사용하니까 사이에 들어가야 한다. 

실패로 끝날때 index를 보면 사이에 들어가야한다는 것이 나온다. 

Search가 빠른 대신, Insert, Delete가 느리다. 모두를 좋게 하는 방법은 없다. Search가 자주 일어나는 경우 좋음.

Unpacked, UnSorted

이전에는 빈자리들이 몰려있기 때문에 몇 개다 라는것만 표현하면 어디까지 쓰고, 어디까지 안쓰는지 알 수 있었는데, 다 흩어져 있기 때문에 쓴다 표시 필요하다. 변수 여러개를 한 단위로 생각하자. 

Insert : 값을 넣는데 앞에서부터 쭉 찾으면서 안쓰는 칸 찾아서 저장하고 쓴다고 표시하면 된다. -> O(n)인거 같은데 기술을 추가하면 O(1)으로 줄일 수 있다. Unpacked, UnSorted 별로 좋은게 없다.

기술은 안쓴는칸은 빈자린데 의미없는 값을 Value에 넣어둔다. 3을 넣어주려고 한다. 3번 index라 하고 7번도 안쓴다.

3에서 index 3번 안쓰고 7번 안쓰고 거기서 또 가면 2번도 안쓰고 그 다음은 value -1이라서 끝난다. 이게 없으면 죽 훑으면서 빈자리를 찾아야 하는데 3번 안쓴다는걸 바로 알 수 있고, 7을 insert할 때 3을 지우고 7로 바꾼다.

거기 있던 7을 가지고 온다. 여전히 7번통해서 2번까지 갈 수 있다. 이 기술을 쓰면 빈자리를 바로 찾을 수 있다. 그 다음에 delete 20을 한다라고 하면 20을 지워야 하는데 어떻게 지우냐. 5번 자리가 날라가는거니까 5번을 Free List Head로 가져오고, 안쓴다고 바꾼다. 20대신 3을 가져다 놓는다

여전히 안쓰는 자리 전부 찾을 수 있고, 주어진 자리를 활용할 수 있다. 그래서 insert를 O(1)으로 할 수 있다. Search가 느린데 Insert, Delete는 빠르다. Byte수가 많으면 복사하는데 오래 걸린다. 

실제로 디스크의 파일 폴더 디렉토리에 들어가면 파일 지우는 거 packed로 packing해서 유지하려면 뒤에서 갖다 옮겨야 되는데 안 쓴다고 마킹만 한다. 마킹만 하기때문에 delete는 빠르다. (현재는 모름)

Free List를 쓰는 다른 하드디스크. 

Unpacked, Sorted

Sorting 해두는 부담을 갖는 것은, search가 빠르기 때문에 sorting하는 부담을 가지는데, binary search가 되나..?

쓰는 자리와 안쓰는 자리가 섞여있다. 중간을 찍었는데 안쓰는 자리이면..? -> 비교 불가.

기술 둘!

우선 처음에는 packed처럼 packing이 되어서 돌아간다. delete하기전에 처음에 insert할때는 중간에 빈자리를 두고 insert할 이유는 없다. Packed한것처럼 돌아간다. 첫 delete를 하기 전까지 중간에 빈자리가 안생긴다. delete를 하면 중간에 빈자리가 생기는데 중간에 있는 빈자리는 첫 delete를 할 때 생긴다. 그럼 이 자리는 delete된 자리라는 것을 알 수 있다. 변수가 하나더 필요하다. 사용한 제일 오른쪽 자리에 대한 자료가 필요하다. delete된 자리들은 거기 값을 그대로 나두는 것이다. 지워졌더라도 값은 그대로 살려둔다. 그러면 살아있는 값들과 죽어있는 값들을 다봤을때 sorting이 된걸로 유지를 할 수 있다. delete할때는 binary search로 하고 그냥 지워주면 아무것도 안바뀌니까 살아있는 값 죽어있는 값 다봐도 sorting이 되어 있다. 안쓴다고 marking만 하면 sorting 상태는 유지된다.

delete는 marking만 하면 되니까 O(1). Sorting된 order를 유지하기 위해서 예를 들어서 insert 16을 하려면 6,7사이에 들어가야한다고 나올텐데 약간 빠른 O(n)임. 예를 들어서 insert 4를 한다고 생각할 때, 빈자리까지만 밀면 된다. 

실제 내가 다루는 데이터가 어떤건지에 대해서 많은 영향을 받는다. 

파이썬은 map, filter와 같은 함수형 기능을 지원하며 다음과 같은 람다 표현식도 지원한다.

list(map(lambda x:x+10,[1,2,3]))
# [11,12,13]

리스트 컴프리헨션

리스트 컴프리헨션이란 기존 리스트를 기반으로 새로운 리스트를 만들어내는 구문으로, 파이썬 2.0부터 지원되었으며 파이썬의 대표적인 특징이다. 

람다 표현식에 map이나 filter를 섞어서 사용하는 것에 비해 가독성이 훨씬 높다.

Ex> 홀수인 경우 2를 곱해 출력하라는 리스트 컴프리헨션

[n*2 for n in range(1,10+1) if n%2 == 1]
# [2, 6, 10, 14, 18]

만약에 리스트 컴프리헨션을 사용하지 않는다면 다음과 같이 작성해야 한다.

a=[]
for n in range(1,10+1):
    if n%2 == 1:
        a.append(n*2)

파이썬은 리스트만 가능한것이 아니라 딕셔너리도 가능하다.

a={}
for key,value in original.items():
    a[key] = value
# 위의 코드를 아래와 같이 바꿀 수 있다
a={key:value for key,value in original.items()}

제너레이터

제너레이터는 루프의 반복 동작을 제어할 수 있는 루틴 형태를 말한다. 예를 들어 숫자 1억 개를 만들어내 계산하는 프로그램을 작성한다고 하였을때 이 경우 제너레이터가 없으면 메모리 어딘가에 만들어낸 숫자 1억 개를 보관하고 있어야 한다. 그러나 제너레이터를 이용하면, 단순히 제너레이터만 생성해두고 필요할 때 언제든 숫자를 만들어낼 수 있다. 

기존의 함수는 return 구문을 맞닥뜨리면 값을 리턴하고 모든 함수의 동작을 종료한다. 그러나 yield는 제너레이터가 여기까지 실행 중이던 값을 내보낸다는 의미로, 중간값을 리턴한 다음 함수는 종료되지 않고 계속해서 맨 끝에 도달할 때까지 실행된다. 

def get_natural_number():
    n=0
    while True:
        n+=1
        yield n

이 경우 함수의 리턴 값은 다음과 같이 제너레이터가 된다.

만약 다음 값을 생성하려면 next()로 추출하면 된다. 예를 들어 100개의 값을 생성하고 싶다면 다음과 같이 100번 동안 next()를 수행하면 된다.

g=get_natural_number()
for _ in range(0,100):
	print(next(g))

range()

제너레이터의 방식을 활용하는 대표적인 함수로 range() 가 있다. 주로 for 문에서 쓰이는 range() 함수의 쓰임은 다음과 같다. 

list(range(5))

# [0,1,2,3,4]

range()는 range 클래스를 리턴하며, for 문에서 사용할 경우 내부적으로는 제너레이터의 next()를 호출하듯 매번 다음 숫자를 생성해내게 된다. 

enumerate()

enumerate()는 '열거한다'는 뜻의 함수로, 순서가 있는 자료형(list,set,tuple)을 인덱스를 포함한 enumerate 객체로 리턴한다. 

a=[1,2,3,2,45,2,5]
print(list(enumerate(a)))
# [(0, 1), (1, 2), (2, 3), (3, 2), (4, 45), (5, 2), (6, 5)]

이처럼 list()로 결과를 추루할 수 있는데, 인덱스를 자동으로 부여해주기 때문에 매우 편리하게 사용할 수 있다. 

for i,v in enumerate(a):
	print(i,v)

https://www.acmicpc.net/problem/2346

[나의 문제 분석]

요세푸스 문제(https://jobdong7757.tistory.com/113?category=916339)와 비슷했던것 같다. 근데 문제는 여기서 s 배열에 음수가 존재하면 오른쪽이 아닌 왼쪽으로 원을 둘러서 가야된다는 사실이다. 이 부분때문에 헷갈려서 헤매었다. 그리고 처음 시작점이 여기서는 0으로 지정되어있다. 그래서 한번 삭제를 하고 반복문을 돌려주어야 한다. 

[나의 해결 방안]

n=int(input())
s=list(map(int,input().split()))
start=0
index=[x for x in range(1,n+1)]
answer=[]
temp = s.pop(start)
answer.append(index.pop(start))

while s:
    if temp<0:
        start = (start+temp)%len(s)
    else:
        start=(start+temp-1)%len(s)
    temp = s.pop(start)
    answer.append(index.pop(start))
for i in answer:
    print(i,end=' ')

n과 s는 주어진 입력이고 start에는 다음 지점을 저장해주려고 하였다. index는 정답에 저장하기 위해서(정답은 0 index를 1로 바꿔서 출력해주어야하기 때문)에 사용하였다. temp에는 s배열의 값을 temp에 저장해주었다.

while문을 하기 전에 이 문제는 시작점이 0으로 정해져있기 때문에 start=0으로 초기화 하고 temp는 s의 start값의 index를 pop해서 저장해준다. 

while문을 이제 시작할때 temp의 값이 음수일때가 문제인데 이 문제를 python의 나머지 기호(%)를 잘몰랐던 나의 무지였었다. 

https://seokdev.site/204 이 사이트에서 다시 공부하고 왔다.. python에서는 c언어의 %와 달리 -1%10을 하면 9가 나오게 된다. 즉, A%B 가 있으면, A에다가 B를 계속 더하면서 처음으로 양수가 되었을 때 B로 나눠 나머지를 준다.

예를 들어 -1%10이면 -1+10=9, 9%10=9 이런식으로 나오는 것이다.

이 문제에서 temp가 음수이면 그냥 start에 temp를 더해서 s의 길이로 나누면 왼쪽으로 -temp만큼 가는것처럼 보이게 되는 것이다. 그래서 temp<0일 때를 처리해 줄 수 있다.

[다른 사람 풀이]

위의 풀이가 temp<0을 처리하기 제일 용이했었는데 그것 말고도 deque에 temp<0을 처리해줄 수 있는 방법도 있었다.

enumerate는 반복문 사용 시 몇 번째 반복문인지 확인이 필요할 때 사용할 수 있다. 이거는 index 번호와 collection의 원소를 tuple 형태로 반환한다. 

예를 들어 이런식이다.

t = [1, 5, 7, 33, 39, 52]
for p in enumerate(t):
	print(p)

(0, 1)
(1, 5)
(2, 7)
(3, 33)
(4, 39)
(5, 52)

그리고 deque의 rotate() 메서드.

deque.rotate(num)을 하면 deque를 num만큼 회전한다.(양수면 오른쪽, 음수면 왼쪽)

# Contain 1, 2, 3, 4, 5 in deq
deq = deque([1, 2, 3, 4, 5])

deq.rotate(1)
print(deq)
# deque([5, 1, 2, 3, 4])

deq.rotate(-1)
print(deq)
# deque([1, 2, 3, 4, 5])

그래서 위 문제는 다음과 같이 풀 수 있다. (참고: https://par3k.tistory.com/215)

from collections import deque
n = int(input())
q = deque(enumerate(map(int,input().split())))
ans=[]

while q:
    idx,num = q.popleft()
    ans.append(idx+1)
    if num>0:
        q.rotate(-(num-1))
    elif num<0:
        q.rotate(-num)
print(' '.join(map(str,ans)))

아까처럼 temp>0일때는 rotate를 시계반대방향으로(왼쪽)하면 되니까 q.rotate(-(num-1))을 하였다. num-1을 한것은 해당하는 풍선은 터뜨려야 하기 때문에. 

그리고 num<0이면 q.rotate(-num)을 하면 된다. -num은 양수이므로 오른쪽(시계방향으로) rotate된다.

https://www.acmicpc.net/problem/10799

[나의 문제 분석]

문제가 복잡하게 적혀 있는데 괄호로 표현해주어서 이해하기 쉬웠다. 처음에 생각한것은 쇠막대기와 레이저의 출발과 끝을 따로 배열로 저장해서 하나씩 볼려고 하였다. 물론 직관적으로 바로 풀었는데 O(n^2)이라서 문제 맞추면 더 좋은 풀이 생각해야지 했더니만 역시.. 시간초과가 뜨고 말았다.

[처음 풀이] 예시들은 제대로 출력되지만 더 빠른 방법이 정답일것 같았다.

s=input()
pipe=[]
raser=[]
stack=[]
answer=0
for i in range(len(s)):
    if s[i]=='(':
        stack.append(i)
    elif s[i]==')':
        if s[i-1]=='(':
            stack.pop()
            raser.append((i-1,i))
        else:
            pipe.append((stack.pop(),i))
for i in pipe:
    count=0
    for j in raser:
        if i[0]<j[0] and i[1]>j[0]:
            count+=1
    answer+=count+1
print(answer)

괄호는 '(', ')' 두개밖에 없고 '('인 경우는 쇠파이프 1개가 새로 시작하거나, 레이저인 경우밖에 없고, ')'인 경우는 쇠파이프 1개가 끝나거나 레이저인 경우밖에 없으므로 결국 input받은걸 하나씩 분석해가면 O(n)안에 문제를 해결할 수 있다.

[나의 해결 방안]

'('인 경우에는 stack안에 집어넣고 ')'인 경우 앞에 것이 바로 '('이면 레이저이므로 stack에 넣은 '('를 빼내준다. 그리고 레이저로 자르면 되는데 이때는 stack의 크기만큼 나온다.

그리고 ')'를 만났는데 그 앞에게 ')'인 경우는 막대기 하나가 끝난경우로 보면 되므로 stack에서 하나 pop해주고 정답을 +1해준다.

s=input()
stack=[]
answer=0
# '('가 들어오는 경우 -> 쇠파이프 1개가 새로 시작하거나, 레이저인 경우
# ')'가 들어오는 경우 -> 쇠파이프 1개가 끝나거나, 레이저인 경우
for i in range(len(s)):
    if s[i]=='(':
        stack.append(i)
    elif s[i]==')':
        if s[i-1]=='(':
            stack.pop()
            answer+=len(stack)
        elif s[i-1]==')':
            stack.pop()
            answer+=1
print(answer)

[다른 사람 풀이]

거의 비슷한것 같다.