본문 바로가기

코딩테스트/Python

 (225)
[Python] 백준 #11725 - 트리의 부모 찾기 문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def dfs(node): global parents,tree for i in tree[node]: # tree[node](node의 부모 or 자식) 을 순회 if parents[i] == 0: # 만약 i의 부모가 아직 지정되지 않았다면 parents[i] = node # node의 자식이므로 i의 부모를 node로 설정 dfs..
[Python] 백준 #3273 - 두 수의 합 문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 풀이 문제 푸는 방식은 같지만 다른사람 코드가 더 깔끔하여 가져왔다. 이 문제는 start와 end를 사용하는 투 포인터를 사용해야한다. 오름차순으로 정렬을 해주고 양 끝에서 합을 구해가면서 답을 찾는 방식이다. start를 첫 인덱스, end를 마지막 인덱스로 지정하기위해 start = 0, end = n-1을 해준다. start보다 ..
[Python] 백준 #11399 - ATM 문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 n = int(input()) arr = list(map(int,input().split())) t = 0 arr.sort() for i in range(len(arr)): t += sum(arr[:i+1]) print(t) 그리디 알고리즘을 사용해야한다. 그리디 알고리즘이란 단순하면서 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려하지..
[Python] 백준 #1012 - 유기농 배추 문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 내 풀이 - DFS 사용 import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def dfs(x,y): visited[x][y] = True # 방문하였으니 True로 바꿔줌 for i in range(4): # 상하좌우 방문 위해 4번 반복 cx = x + dx[i] # 방문할 x좌표 cy = y + dy[i] # 방문할 y좌표 i..
[Python] 백준 #11654 - 아스키 코드 문제 https://www.acmicpc.net/problem/11654 11654번: 아스키 코드 알파벳 소문자, 대문자, 숫자 0-9중 하나가 주어졌을 때, 주어진 글자의 아스키 코드값을 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 print(ord(input())) 파이썬에서 아스키코드를 만들때는 ord를 사용한다.
[Python] 백준 #9461 - 파도반 수열 문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 n = int(input()) for _ in range(n): p = [0,1,1,1,2,2] x = int(input()) for i in range(6,x+1): p.append(p[i-1] + p[i-5]) print(p[x]) 새로 만들어지는 삼각형의 한 변은 그 전에 만들어졌던 삼각형의 한 변의 길이와 5번째 전에 만들어졌던 삼각형의 한 변의 길이를 더한 것이다.
[Python] 백준 #11286 - 절댓값 힙 문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 import heapq import sys input = sys.stdin.readline n = int(input()) h = [] for _ in range(n): x = int(input()) if x: heapq.heappush(h,(abs(x),x)) else: print(heapq.heappop(h)[1]) if h else print(0) abs를 사용..
[Python] 백준 #1927 - 최소 힙 문제 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 import heapq import sys input = sys.stdin.readline n = int(input()) h = [] for _ in range(n): x = int(input()) if x: heapq.heappush(h,x) else: print(heapq.heappop(h)) if h else print(0) 힙을 사용하여 구해주면된다.

티스토리툴바