11403번: 경로 찾기 (acmicpc.net)

++++

11725번: 트리의 부모 찾기 (acmicpc.net)

#루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정할 때 각 노드의 부모를 구하는 프로그램
from collections import deque
import sys

n = int(sys.stdin.readline()) #노드의 수

graph = [set() for i in range(n+1)]

#인접리스트 구현
for _ in range(n-1): # 정점이 n개이므로 간선은 n-1개 있음
    a, b = map(int, sys.stdin.readline().split())
    graph[a].add(b)
    graph[b].add(a)

visited = [0 for i in range(n+1)]

queue = deque([1])
while queue:
    x = queue.popleft()
    for node in graph[x]:
        if visited[node] == 0:
            visited[node] = x # 방문했을 때 0을 대체하게 되는 것은 부모 번호이다.
            queue.append(node)

for i in range(2, len(visited)):
    print(visited[i])

여러번 런타임 에러가 난 이유: 마지막 출력하는 for문에서 range를 1부터로 설정해놓아서이다. 

1은 루트노드인데, 루트노드의 부모 노드는 출력할 필요가 없다.. 

그리고 인접리스트 구현할 때도 처음에 for _ in range(n)이렇게 했었는데, n은 정점의 개수이므로 간선은 n-1개가 된다.

1475번: 방 번호 (acmicpc.net)

다솜이 방번호 문제: 방 번호가 최대 6자리인데 숫자 세트가 몇 개 필요할까? 6, 9는 돌려서 쓸 수 있다. 

내 풀이

from collections import Counter

num = input()

count = Counter(num)
count['9'] = (count['9']+count['6']+1)//2
count['6'] = 0

max_count = sorted(count.values(), reverse = True)
print(max_count[0])

문법을 좀 더 알게 되니까 Count, sorted(count.values()) --딕셔너리에서 value 값만을 기준으로 정렬하기 등을 써서 간결한 코드가 되었다. 

주의할 점

num = input()

for i in num:
    if i == '6': 
        i = '9'

---> 이렇게 해도 num 안의 원소 값이 바뀌는 게 아님.

잘 보면 당연하지만, 임시변수인 i만을 9로 바꾼 것이다. 

7개월 전에 푼 걸 봤는데 이거는 정말 처음부터 손으로 다 구현했고 시간이 덜 걸리는 방법이긴 하다.

arr=[]
arr.append(list(map(int,input())))

s=arr[0].count(6)
n=arr[0].count(9)
sn = arr[0].count(6)+arr[0].count(9)


if sn<=1:
    pass
elif sn%2==0:
    sn=sn//2
elif sn%2==1:
    sn=sn//2+1
        
for _ in range(s):
    arr[0].remove(6)
    
for _ in range(n):
    arr[0].remove(9)

arr2=[]
count=0

for i in arr[0]:
    arr2.append(i)
    dupl=0
    dupl+=arr2.count(i)
    if dupl>count:
        count=dupl

if sn>count:
    print(sn)
else:
    print(count)

1316번: 그룹 단어 체커 (acmicpc.net)

 - 입력 받은 단어들 중 그룹 단어의 개수를 출력하는 문제이다.

 - 그룹단어는 각 문자들이 단어 안에서 나눠서 등장하는 게 아니라 한번에 등장하는 단어를 말함.

내 코드

n = int(input())
arr = [input() for _ in range(n)]
count = n

for word in arr:
    visited = [word[0]]
    for i in range(1, len(word)):
        if word[i] in visited and word[i-1] != word[i]:
            count -= 1
            break
        elif word[i] not in visited:
            visited.append(word[i])

print(count)

1년 전에 작성한 더 느리고 복잡한 코드

n=int(input())
a=0
for i in range(n):
    d=input()
    l=list(d)
    for j in range(1,len(l)):
        if l[j-1]==l[j]:
            l[j-1]='*'
    while '*' in l : l.remove('*')
    if sorted(list(set(l)))==sorted(l):
        a+=1
    else: a+=0
print(a)

1181번: 단어 정렬 (acmicpc.net)

내 코드

from collections import defaultdict
n = int(input())
words = [input() for _ in range(n)]
words.sort()

dict = defaultdict(set)

for word in words: 
    length = len(word)
    dict[length].add(word)

for length in sorted(dict.keys()):
    for word in sorted(dict[length]):
        print(word)

<과정>  
1. 입력되는대로 단어를 추가한 리스트를 만든다.
2. 그 리스트의 단어들을 사전순으로 정렬한다.
3. 딕셔너리를 하나 초기화한다.
4. 각 단어의 길이를 키로, 그 길이를 가진 단어들을 value로 딕셔너리를 채운다.
5. 그.. key값(단어길이)를 기준으로 정렬한 length별로 그에 해당하는 word를 하나씩 프린트한다.
6. 그러면 이미 처음부터 사전순 정렬된 리스트였기 때문에 길이순+사전순으로 프린트가 됨.

# 길이순, 사전순 정렬이라고 문제에는 나와있지만 사전순 길이순으로 해도 결과는 같고 또 그렇게 하는 것이 훨씬 더 쉽다. 

아래는 6개월 전에 푼 코드이다. 람다는 쓰는 법을 계속 까먹어서 검색을 안 하면 쓸 수가 없다..........

n= int(input())
arr=[]

for _ in range(n):
    arr.append(str(input())) #단어 입력받아서 리스트에 넣기

arr=list(set(arr)) #중복되는 단어 삭제
arr.sort() #알파벳 사전순으로 정렬


arr.sort(key = lambda i:len(i)) #알파벳 길이순으로 정렬

for i in arr:
    print(i)

1157번: 단어 공부 (acmicpc.net)

from collections import Counter
d=str(input())
cnt=Counter(d.upper()).most_common()
list=[]
for i in cnt:
    if i[1]==cnt[0][1]:
        list.append(i[0])
if len(list)>=2:
    print('?')
else: print(cnt[0][0])

Counter라는 거 쓰면... 키값은 그 원소, 밸류는 몇 번 나왔는지로 딕셔너리를 자동으로 만들어 준다. 

그리고 Counter(d.upper()).most_common()

이 부분에서 그냥 d를 넣은 게 아니라 d에 있는 모든 알파벳을 대문자로 바꿨고(대소문자 구별 없이 개수를 세기 위해서)

Counter(리스트 이름).most_common()이거는 등장 횟수가 높은 것부터 내림차순으로 자동정렬되는 함수이다. 

그리고 list라는 빈 배열을 다시 만들었음. 

딕셔너리 cnt의 각 원소쌍 i에 대해서.. 최빈값이랑 같은 값이 있으면 list에 넣는다.

len(list)가 2 이상이면 가장 많이 등장한 문자를 찾을 수 없으므로 물음표를 출력하고 아니면 그냥 젤 많이 등장한 문자 출력하기~

+)

전에 푼 문제에 해설을 쓰다보니 이상해서 List부분을 없애고 단순히 두개 이상인지만 확인할 수 있도록 하는 코드로 바꿨다. 

from collections import Counter
word = input()
dict = Counter(word.upper()).most_common()
count = 0
for i in dict:
    if i[1] == dict[0][1]:
        count += 1

if count >= 2:
    print("?")
else: print(dict[0][0])

1152번: 단어의 개수 (acmicpc.net)

#단어의 개수 구하기
sentence = input()
if len(sentence)>=2:
    count = 1

    for i in range(1, len(sentence)-1):
        if sentence[i] == " ":
            count += 1

    print(count)
elif len(sentence)==1 and sentence[0]!=" ":
    print(1)

else: print(0)

#1년 전의 내가 제출한 아주아주 간결한 코드: 시간도 더 조금밖에 안 걸림. ㅋ
s=list(map(str,input().split()))
print(len(s))

1149번: RGB거리 (acmicpc.net)

#RGB거리: 빨/초/파 중 하나의 색으로 칠해야 한다. 이웃한 집들과는 색이 달라야 한다. 칠하는 최소 비용 구하기.

n = int(input())

graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

빨, 초, 파로 각각의 집을 칠하는 가격 순서대로 입력받아서 그래프로 나타내기

dp = []
for _ in range(n):
    dp.append([0, 0, 0])

dp[0][0] = graph[0][0]
dp[0][1] = graph[0][1]
dp[0][2] = graph[0][2]

for i in range(1, n):
    
    dp[i][0] = min(dp[i-1][1], dp[i-1][2])+graph[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2])+graph[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1])+graph[i][2]
    
    '''
    if dp[i-1][0]+graph[i][1] <= dp[i-1][2]+graph[i][1]:
        dp[i][1]= dp[i-1][0]+graph[i][1]
    else: dp[i][1] = dp[i-1][2]+graph[i][1]
    ↑ 이런 형식에서 간단하게 수정함.
    
    '''
    
print(min(dp[n-1]))

백준 한수

#한수 : 양의 정수 x의 각 자리가 등차수열을 이루는 수. n이 주어졌을 때 ..1부터 n까지 한수의 개수 출력하기

n = int(input())
#1부터 99까지는 한수이다. 

hansu = [111, 123, 135, 147, 159, 210, 222, 234, 246, 258, 321, 333, 345, 357, 369, 420, 432, 444, 456, 468, 531, 543, 555, 567, 579, 630, 642, 654, 666, 678, 741, 753, 765, 777, 789, 840, 852, 864, 876, 888, 951, 963, 975, 987, 999]
count = 0

if n < 100:
    print(n)
else:
    count+=99
    for i in range(len(hansu)):
        if hansu[i]<=n:
            count+=1
        else: break

    print(count)

더 노가다로 풀었지만 풀이시간도 줄고 실행시간도 줄었다. 원래 코드는 

if arr[1]-arr[0]==arr[2]-arr[1]:
            a+=1

이런 식임

백준 복습

# #1000
a, b = map(int, input().split())
print(a+b)


# #1003
arr1=[1, 0, 1, [0]*38]
arr2=[0, 1, 1, [0]*38]

for i in range(3, 41):
    arr1[i] = arr1[i-1]+arr1[i-2]
    arr2[i] = arr2[i-1]+arr2[i-2]

n= int(input())
for _ in range(n):
    a=int(input())
    print(arr1[a], arr2[a])


#1009
n = int(input())

arr2 = [6, 2, 4, 8]
arr3 = [1, 3, 9, 7]
arr7 = [1, 7, 9, 3]
arr8 = [6, 8, 4, 2]
arr4 = [6, 4]
arr9 = [1, 9]

for _ in range(n):
    a, b = map(int, input().split())
    if a%10 == 1 or a%10 ==5 or a%10 == 6:
        print(a%10)
    elif a%10 == 2:
        print(arr2[b%4])
    elif a%10 == 3:
        print(arr3[b%4])
    elif a%10 == 7:
        print(arr7[b%4])
    elif a%10 == 8:
        print(arr8[b%4])
    elif a%10 == 4: 
        print(arr4[b%2])
    elif a%10 == 9:
        print(arr9[b%2])
    else: #a%10==0:
        print(10)



#1010 다리놓기 재원이
count = int(input())
for _ in range(count):
    num1 = 1
    num2 = 1
    n, m = map(int, input().split())
    for i in range(m-n+1, m+1):
        num1 *= i

    for j in range(1, n+1):
        num2 *= j

    print(num1//num2)



#1012

from collections import deque

case= int(input())

for _ in range(case):
    m, n, k = map(int, input().split())
    count = 0 
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    graph = [[0]*m for i in range(n)]
    for _ in range(k):
        a, b = map(int, input().split())
        graph[b][a] = 1

    queue = deque([(m, n)])

    while len(queue)>=1: 
        x, y = queue.popleft()
        canmove=0
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx<0 or nx>=m or ny<0 or ny>=n:
                continue
            if graph[ny][nx]==1:
                queue.append((nx, ny))  
                canmove+=1  
        #만약 네 방면 모두 0이었다면?
        if canmove == 0:
            count+=1

    print(count)