본문 바로가기

전체 글229

[백준] 11725번 트리의 부모 찾기(python) https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 내가 작성한 코드 import sys sys.setrecursionlimit(10**9) n = int(input()) #노드의 개수 tree = [[] for _ in range(n+1)] #tree parent = [0] * (n+1) #parent 저장 for i in range(n-1): a,b = map(int, input().split()) tree[a].append(b) tree[b].append(a) def dfs(num): for j in.. 2023. 2. 18.
[백준] 카드 정렬하기 (python) https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. 내가 작성한 코드 import heapq import sys input = sys.stdin.readline n = int(input().rstrip()) #입력 횟수 heap = [] for i in range(n): heapq.heappush(heap,int(input().rstrip())) #heap에 모든 값 push answer = 0 while True: if len.. 2023. 2. 18.
[자료구조] 힙, 최소힙, 최대힙, heapq(python) 1. 힙(heap)이란? 가장 높은 우선순위를 가지는 노드를 빠르게 찾을 수 있는 자료구조 저장된 값이 힙 조건(완전이진트리, 루트노드의 우선순위가 제일 높아야 됨)을 만족하는 리스트 최대 힙(Max Heap) : 부모 노드 key > 자식 노드 key 최소 힙(Min Heap) : 부모 노드 key < 자식 노드 key 2. heapq import heapq 를 이용해서 모듈 import heap = [] #힙으로 사용할 list 생성 삽입 연산 : heappush(heap명, item) 삭제 연산 : heappop(heap명) heap는 최소힙만 지원됨 추가) heapq 의 내부 동작 원리를 알고 싶으면 신찬수 교수님의 자료구조 강의 참고하기(https://youtu.be/8XnPN6IB22Y) he.. 2023. 2. 18.
[백준] 5014번 스타트링크(python) https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 1. 내가 작성한 코드 from collections import deque f, s, g, u, d = map(int,input().split()) visit = [0] * (f+1) def bfs(): queue = deque() queue.append(s) visit[0] = 1 visit[s] = 1 while queue: x = queue.popleft() dx = [u,-d] for i in ran.. 2023. 2. 17.
[백준] 10026번 적록색약(python) https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. 내가 작성한 코드 from collections import deque def bfs(matrix,i,j,cnt,visit): queue = deque() queue.append((i,j)) visit[i][j] = cnt dx = [-1,1,0,0] dy = [0,0,-1,1] while queue: x,y = queue.popleft() for i in range(4): nx = .. 2023. 2. 16.
[백준] 1463번 1로 만들기(python) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. 내가 작성한 코드 import sys num = int(sys.stdin.readline().rstrip()) dp = [0,0,1,1] dp = dp + [0] * (num-3) if num >= 4: for n in range(4,num+1): if n % 2 == 0 and n % 3 == 0: #2,3 모두 나누어 떨어지는 경우 dp[n] = 1 + min(dp[n//2],dp[n//3],dp[n-1]) elif n % 2 == 0: #2로만 나누어 떨어지는 경우 dp[n] = 1 + min(dp[.. 2023. 2. 16.
[백준] 9095번 1,2,3 더하기(python) https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 1. 내가 작성한 코드 t = int(input()) for i in range(t): n = int(input()) d = [0,1,2,4] #1,2,3을 만들 수 있는 경우의 수 if n > 3: d = d + [0] * (n-3) for i in range(4,n+1): d[i] = d[i-1] + d[i-2] + d[i-3] print(d[n]) 1. 수를 만들 때는 1,2,3만을 사용할 수 있다. 1을 만들 수 있는 방법 => (1) => 1가지 2를 만들 수 있는 방법 => (1,1).. 2023. 2. 16.
[백준] 22233번 가희와 키워드(python) https://www.acmicpc.net/problem/22233 22233번: 가희와 키워드 1번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, floyd, os가 됩니다. 2번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, os가 됩니다. map은 1번째 글과 2번째 글에 중복으로 등장하였음을 www.acmicpc.net 1. 내가 작성한 코드 set 을 이용해서 문제를 해결하려고 했는데 시간초과로 자꾸 실패해서 딕셔너리로 해결했다. import sys input = sys.stdin.readline n,m = map(int, input().split()) keyword = {} for i in range(n): keyword[input().rstrip()] = 1 for i in.. 2023. 2. 16.
[프로그래머스] Level1 콜라 문제(python) https://school.programmers.co.kr/learn/courses/30/lessons/132267 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 내가 작성한 코드 def solution(a, b, n): result = 0 #받을 수 있는 콜라 수 while n>=a: result += (n//a) * b #마트에서 받은 콜라 n = (n - (n//a) * a) + (n//a) * b #마트에 주고 남은 콜라 + 마트에서 받은 콜라 return result n값이 변하기 때문에, result 를 구하는 코드가 n을 갱신하는 코드보.. 2023. 2. 15.

티스토리툴바