'Problem Solve' 카테고리의 글 목록

[백준] 11725번 트리의 부모 찾기 (Python)

문제 주소 백준 17725번 트리의 부모 찾기 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘 트리 힌트 주어진 입력대로 노드들을 양방향으로 연결하고 1을 루트로 트리를 재구성한다. 문제풀이 1에서 출발하여 BFS로 각 노드의 부모를 찾는다. n = int(input()) tree = [[] for i in range(n+1)] for i in range(n-1): a,b=list(map(int,input().split())) tree[a].append(b) tree[b].append(a) q = [1] ans= {} check = [False for i in ra..

Problem Solve/Tree 2020. 7. 1. 14:54

[백준] 1991번 트리 순회 (Python)

문제 주소 백준 1991번 트리 순회 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 알고리즘 트리 힌트 전위 순회(preorder) 노드를 방문한다. 왼쪽 서브 트리를 전위 순회한다. 오른쪽 서브 트리를 전위 순회한다. 중위 순회(Inorder) 왼쪽 서브 트리를 중위 순회한다. 노드를 방문한다. 오른쪽 서브 트리를 중위 순회한다. 후위 순회(postorder) 왼쪽 서브 트리를 후위 순회한다. 오른쪽 서브 트리를 후위 순회한다. 노드를 방문한다. 문제풀이 파이썬의 딕셔너리를 이용하여 트리를 구현할 수..

Problem Solve/Tree 2020. 7. 1. 13:50

[백준] 10799번 쇠막대기 (python)

문제 출처 한국정보올림피아드 지역본선 2015 중등부 2번 한국정보올림피아드 지역본선 2015 초등부 3번 문제 주소 백준 10799번 쇠막대기 코드업 4833 : 쇠막대기 알고리즘 스택 힌트 레이저가 있는 위치에 막대기가 몇 개 있는지 알면 계산할 수 있다. 문제풀이 class ArrayStack: def __init__(self): self.data = [] def size(self): return len(self.data) def isEmpty(self): return self.size() == 0 def push(self, item): self.data.append(item) def pop(self): if self.isEmpty() is not True: return self.data.pop()..

Problem Solve/Stack 2020. 5. 29. 17:49

[백준] 1966번 프린터 큐 (python)

문제 출처 Northwestern European Regional Contest NWERC 2006 F번 문제 주소 백준 1966번 프린터 큐 1966번: 프린터 큐 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료�� www.acmicpc.net 알고리즘 큐 문제풀이 큐 구현부 class ArrayQueue: def __init__(self): self.data = [] def size(self): return len(self.data) def isEmpty(self): return self.size()==0 def enqueue(self, item): self...

Problem Solve/Queue 2020. 5. 23. 09:30

[백준] 13335번 트럭 (Python)

문제 출처 ICPC Regionals Asia Pacific Korea Daejeon Nationalwide Internet Competition 2016 L번 문제 주소 백준 13335번 트럭 13335번: 트럭 문제 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단�� www.acmicpc.net 알고리즘 Queue 힌트 다리가 무게가 0인 트럭들로 꽉 차있다고 생각하고 문제를 푼다 문제풀이 truck큐와 bridge큐를 만들어서 다리 위에 있는 트럭들과 대기중인 트럭들을 관리한다. class ArrayQueue: def __init__(self): self.da..

Problem Solve/Queue 2020. 5. 22. 21:49

[HackerEarth] Fun Game (python)

문제 주소 Fun Game 힌트 입력 데이터 리스트와 그 reverse한 리스트를 비교하면된다. 풀이 스택 구현부 class ArrayStack: def __init__(self): self.data = [] def size(self): return len(self.data) def isEmpty(self): return self.size() == 0 def push(self, item): self.data.append(item) def pop(self): if self.isEmpty() is not True: return self.data.pop() def peek(self): if self.isEmpty() is not True: return self.data[-1] else: print("Stack..

Problem Solve/Stack 2020. 5. 21. 15:42

[백준] 9251번 LSC (C)

문제 주소 백준 9251번 LSC 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 알고리즘 DP 힌트 첫번째 문자열의 i번 문자까지의 문자열과 두번째 문자열의 j번 문자까지의 문자열의 LCS의 길이를 구한다. 문제풀이 dp[i][j]에 문자열 a의 i번 문자까지의 문자열과 문자열 b의 j번 문자까지의 문자열의 LCS의 길이를 저장한다. 가장 끝의 문자만 비교하는 식으로 길이를 구해나갈 수 있다. 끝 문자가 같을 경우 dp[i][j] = dp[i-1][j-1]+1 끝..

Problem Solve/Dynamic Programming 2020. 4. 21. 09:49

[백준] 2565번 전깃줄 (C)

문제 출처 한국정보올림피아드 지역본선 2007 초등부 4번 문제 주소 백준 2565번 전깃줄 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net 알고리즘 DP 힌트 서로 교차하지 않는 전깃줄의 최대 개수를 구한다. 문제풀이 서로 교차하지 않는 전깃줄의 최대 개수를 구하기 위해선 한 쪽 전봇대 기준으로 정렬을 한 뒤 나머지 전봇대의 번호에서 가장 긴 증가하는 수열을 구하면 된다. #include ..

Problem Solve/Dynamic Programming 2020. 4. 12. 00:31

[백준] 11054번 가장 긴 바이토닉 부분 수열 (C)

문제 주소 백준 11054번 가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 알고리즘 DP 힌트 i위치까지 가장 긴 증가하는 부분수열의 길이와 i위치까지 가장 긴 감소하는 부분 수열의 길이를 구한다. 문제풀이 dp[i][0]에 i위치까지 가장 긴 증가하는 부분수열의 길이 dp[i][1]에 i위치까지 가장 긴 감소하는 부분 수열의 길이를 저장하고 두 합이 가장 큰 것의 값을 구한다. #include using namespace std; int in[1002]; int dp[1002][2]; int mai..

Problem Solve/Dynamic Programming 2020. 4. 9. 12:59

[백준] 11053번 가장 긴 증가하는 부분 수열 (C)

문제 주소 백준 11053번 가장 긴 증가하는 부분 수열 불러오는 중입니다... 알고리즘 DP 힌트 dp배열에 i번째 수 까지 가장 긴 증가하는 부분 수열의 길이를 저장한다. 문제풀이 i번째 수 까지 가장 긴 증가하는 부분 수열의 길이를 구하기 위해선 i번째 이하의 1~i-1의 구간의 수를 j라 할 때 in[i]가 in[j]보다 크다면 dp[j]+1, 작다면 dp[j]를 선택한 값의 최대값을 구하면 된다. 답은 dp[1]~dp[n]까지의 수 중 최대값이다. #include using namespace std; int dp[1001]; int in[1001]; int main(){ int n; cin>>n; for(int i=1;i>in[i]; int ans=0; for(int i=1;i

Problem Solve/Dynamic Programming 2020. 4. 6. 11:41

낭만 IT

Problem Solve → (51)건