코딩테스트 #04

MUUU·2022년 2월 8일
나동빈이코테코딩테스트파이썬
0

코딩테스트

목록 보기
4/8

개발형코테

  • 하나의 모듈 vs 여러개의 모듈




  • 카카오 ㅠㅠㅠ










  • 원래는 토큰 포함

import requests

#rest api 경로에 접속하여 응답(response) 데이터 받아오기
target='https://jsonplaceholder.typicode.com/users'
response=requests.get(url=target)

#응답 데이터가 json형식이므로 바로 파이썬객체로 변환
data=response.json()

#모든 사용자 정보를 확인하며 이름정보만 삽입
name_list=[]
for user in data:
    name_list.append(user['name'])
print(name_list)

['Leanne Graham', 'Ervin Howell', 'Clementine Bauch', 'Patricia Lebsack', 'Chelsey Dietrich', 'Mrs. Dennis Schulist', 'Kurtis Weissnat', 'Nicholas Runolfsdottir V', 'Glenna Reichert', 'Clementina DuBuque']

기타 그래프이론

서로소 집합: 공통원소가 없음









서로소 집합 자료구조


def find_parent(parent, x):
    # 루트노드 찾을때까지 재귀호출
    if parent[x] !=x:
        return find_parent(parent, parent[x])
    return x

# 두 원소가 속한 집합 합치기
def union_parent(parent, a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b
        
v,e=map(int, input().split())
parent=[0]*(v+1) #부모테이블 초기화

# 부모를 자기자신으로 초기화
for i in range(1,v+1):
    parent[i]=i

for i in range(e):
    a,b=map(int,input().split())
    union_parent(parent,a,b)
    

#각 원소가 속한 집합 출력하기
print('각 원소가 속한 집합:', end='')
for i in range(1, v+1):
    print(find_parent(parent,i),end=' ')
print()

#부모테이블 내용 출력
print('부모 테이블: ', end=' ')
for i in range(1,v+1):
    print(parent[i],end=' ')

경로압축


서로소집합 자료구조: 경로압축

def find_parent(parent, x):
    # 루트노드 찾을때까지 재귀호출
    if parent[x] !=x:
        parent[x]=find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합 합치기
def union_parent(parent, a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b
        
v,e=map(int, input().split())
parent=[0]*(v+1) #부모테이블 초기화

# 부모를 자기자신으로 초기화
for i in range(1,v+1):
    parent[i]=i

for i in range(e):
    a,b=map(int,input().split())
    union_parent(parent,a,b)
    

#각 원소가 속한 집합 출력하기
print('각 원소가 속한 집합:', end='')
for i in range(1, v+1):
    print(find_parent(parent,i),end=' ')
print()

#부모테이블 내용 출력
print('부모 테이블: ', end=' ')
for i in range(1,v+1):
    print(parent[i],end=' ')
바뀐부분
def find_parent(parent, x):
	# 루트노드를 찾을때까지 재귀호출 
	if parent[x] !=x:
    		parent[x]=find_parent(parent, parent[x])
    return parent[x]

서로소 집합 사이클판별




서로소 집합을 활용한 사이클판별
def find_parent(parent, x):
    # 루트노드 찾을때까지 재귀호출
    if parent[x] !=x:
        parent[x]=find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합 합치기
def union_parent(parent, a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b
        
v,e=map(int, input().split())
parent=[0]*(v+1) #부모테이블 초기화

# 부모를 자기자신으로 초기화
for i in range(1,v+1):
    parent[i]=i

# 사이클발생 여부    
cycle=False

for i in range(e):
    a,b=map(int,input().split())
    # 사이클이 발생한 경우 종료
    if find_parent(parent,a)==find_parent(parent,b):
        cycle=True
        break
    # 사이클이 발생하지 않았다면 합집합 union 연산 수행
    else:
        union_parent(parent,a,b)
if cycle:
    print('사이클이 발생')
else:
    print('사이클이 불발생')

바뀐부분

cycle=False
for i in range(e):
    a,b=map(int,input().split())
    # 사이클이 발생한 경우 종료
    if find_parent(parent,a)==find_parent(parent,b):
        cycle=True
        break
    # 사이클이 발생하지 않았다면 합집합 union 연산 수행
    else:
        union_parent(parent,a,b)

신장트리(spanning tree)

  • 모든 노드들이 연결된 것

최소신장트리

크루스칼 알고리즘(Kruskal Algorithm)





# 크루스칼 알고리즘 (Kruskal Algorithm))
def find_parent(parent, x):
    # 루트노드 찾을때까지 재귀호출
    if parent[x] !=x:
        parent[x]=find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합 합치기
def union_parent(parent, a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b
        
v,e=map(int, input().split())
parent=[0]*(v+1) #부모테이블 초기화


# 모든간선을 담을 리스트와, 최종비용을 담을 변수
edges=[]
result=0

# 부모를 자기자신으로 초기화
for i in range(1,v+1):
    parent[i]=i
    
# 모든 간선에 대한 정보 입력받기
for _ in range(e):
    a,b, cost=map(int,input().split())
    # 비용순으로 정렬하기 위해 튜플의 첫번째 원소를 비용으로 설정
    edges.append((cost,a,b))

#간선을 비용순으로 정렬
edges.sort()

#간선을 하나씩 확인하면
for edge in edges:
    cost,a,b=edge
    #사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent,a)!=find_parent(parent,b):
        union_parent(parent,a,b)
        result+=cost
print(result)

위상정렬







from collections import deque
v,e=map(int, input().split())

# 모든 노드 진입차수 0으로 초기화
indegree=[0]*(v+1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결리스트 초기화
graph=[[] for i in range(v+1) ]

#방향 그래프의 모든 간선 정보를 입력받기
for _ in range(e):
    a,b=map(int,input().split())
    graph[a].append(b) #정점 A에서 B로 이동가능
    #진입차수 1증가
    indegree[b]+=1
    
#위상정렬함수
def topology_sort():
    result=[] 
    q=deque()
    # 처음 시작시에는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1,v+1):
        if indegree[i]==0:
            q.append(i)
            
    #큐가 빌때까지 반복
    while q:
        now=q.popleft()    
        result.append(now)
        # 해당원소아ㅗ 연결된 노드들의 진입차수에서 1빼기
        for i in graph[now]:
            indegree[i]-=1
            #새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i]==0:
                q.append(i)
    #위상정렬을 수행한 결과 출력
    for i in result:
        print(i,end=' ')
topology_sort()

7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4
1 2 5 3 6 4 7

기타 알고리즘

소수(prime number)

def is_prime_number(x):
    for i in range(2,x):
        if x%i==0:
            return False #소수가 아님
        return True #소수임

print(is_prime_number(4))
print(is_prime_number(7))

False
True

개선된 소수 알고리즘 ( 제곱근까지 판별하기)

import math
def is_prime_number(x):
    for i in range(2, int(math.sqrt(x))+1):
        if x%i==0:
            return False
        return True

다수의 소수 판별 : 에라토스테네스의 체 알고리즘

  • 특정한 수의 범위 안에 존재하는 모든 소수를 찾을 겨우
  • i는 소수
# 에라토스테네스의 체 알고리즘
import math

n=1000  #1000까지의 모든 수에 대해서 소수판별
array=[True for i in range(n+1)]

for i in range(2, int(math.sqrt(n))+1):
    if array[i]==True:
        j=2
        while i*j <=n:
            array[i*j]=False
            j+=1
for i in range(2, n+1):
    if array[i]:
        print(i, end=' ')

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997

  • 10억이 소수인지 아닌지 판별가능? => 메모리도 많이차지

투 포인터(two pointers)



n=5
m=5
data=[1,2,3,2,5]
count=0
interval_sum=0
end=0

# start를 차례대로 증가시키며 반복
for start in range(n):
    # end를 가능한만큼 이동시키기
    while interval_sum < m and end < n:
        interval_sum+=data[end]
        end+=1
    # 부분합이 m일때 카운트증가 
    if interval_sum ==m:
        count+=1
    interval_sum-=data[start]
print(count)

3

구간합 문제(interval_sum)




n=5
data=[10,20,30,40,50]

sum_value=0
prefix_sum=[0]
for i in data:
    sum_value+=i
    prefix_sum.append(sum_value)
    
# 구간합 계산 (세번째 부터 네번째까지 )
left=3
right=4
print(prefix_sum[right]-prefix_sum[left-1])

70

벨만포드알고리즘

profile
MUUU
데이터분석
이전 포스트

코딩테스트 #03

다음 포스트

프로그래머스 lv.1

0개의 댓글