본문 바로가기

Algorithm

 (42)
[자료구조] 이진트리 Binary Tree - 자식노드를 최대 2개로 가지는 트리 Binary Search Tree - 숫자 기준으로 노드의 왼쪽 자식들은 자신보다 작은 숫자들이 위치하는 것, 반면 우측의 자식들은 자신보다 큰 숫자들이 위치하는 것. - 숫자가 아닌 우선순위를 기준으로 해도 마찬가지 자신보다 우선순위가 높은 것들은 왼쪽으로 자식을 가지고, 자신보다 우선순위가 낮은 것들을 오른쪽 자식으로 가질 수 있음 - 상황과 형태에 따라 알맞게 구성해야 함. Complete Binary Tree 2:1 or 2:0 완전 - 자식을 가지는 노드 중 하나라도 자식을 2개로 가지는 노드가 있으며됨, 동일한 레벨의 노드가 자식을 1개 혹은 2개를 가짐 Full Binary Tree 2:2 or 2:0 풀 - 자식의 노드를 2개 이..
[자료구조] Stack, Queue Stack 데이터의 상태, 값 저장용도 LIFO(Last In First Out) 마지막에 들어온 것이 먼저 나감 개인적인 생각으로 Git의 Commit, Push 등의 로그들이 Stack의 용도로 사용된다고 생각함. 예전 컴퓨터공학과 2학년 수업 중간고사 때 실생활 예로 학생식당에서 사용하는 종이컵으로 사용생각함. 종이컵 박스에서 위에만 뚫려있다면 넣을때 아래부터 위로 쌓아지고 사용하는 사람은 차례대로 위에 뚫린 구멍을 통해 하나씩 빼서 사용하는... stack의 연산 top: stack의 최근 삽입한 데이터, 혹은 위치 push: 데이터 삽입(top+1) pop: 최근에 삽입한 데이터 제거 size: stack의 크기 empty: 비워져있는지 아닌지 C++의 STL로 쉽게 확인 가능함. Queue 전..
[백준] 덩치 7568 브루트포스 Python 덩치 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 128 MB 10015 5749 5080 60.240% 문제 https://www.acmicpc.net/problem/7568 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x,y), (p,q)라고 할 때 x>p 그리고 y>q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56,177), (45,165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 ..
[백준] 분해합 2231 브루트포스 Python 분해합 한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 192 MB 12523 6608 5485 52.373% 문제 https://www.acmicpc.net/problem/2231 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,0..
[백준] 블랙잭 2798 브루트포스(Brute Force) Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import itertools N, M = map(int, input().strip().split()) lists = list(map(int, input().strip().split())) chk = 0 lists_combinations = itertools.combinations(lists,3) combisums = [] for i in lists_combinations: if M == sum(list(i)): # 만약 같은 값이 나오면 최대이기에 출력하고 종료 print(sum(list(i))) chk = 1 break if sum(list(i))
[백준] 셀프넘버 4673 Python 1 2 3 4 5 6 7 8 9 10 11 12 natural_number = set(range(1,10001)) noself_number = set() for i in range(1,10001): for j in str(i): i += int(j) noself_number.add(i) self_number = natural_number - noself_number for i in sorted(self_number): print(i) h
[백준] 하노이 탑 이동 순서 11729 Python (재귀) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 cnt = 0 result = [] def hanoi(n, fromm, by, to): global cnt cnt += 1 if n == 1: result.append(str(fromm)+" "+str(to)) else: hanoi(n-1, fromm, to, by) result.append(str(fromm)+" "+str(to)) hanoi(n-1, by, fromm, to) n = int(input()) hanoi(n,1,2,3) print(cnt) for i in result: print(i)
[정렬] 삽입정렬 삽입할 인덱스를 기준으로 왼쪽은 정렬이 되어있다고 가정 삽입할 인덱스 보다 우선순위가 높은 인덱스의 위치를 발견하면 해당 인덱스 다음의 위치에 삽입함 반대로 자기보다 우선순위가 낮으면 해당 인덱스를 +1인덱스의 위치로(한칸)옆으로 이동시킴 ex) 3,4,2,1 인덱스 1의 위치하는 값 4는 3보다 크므로 인덱스 변하지 않음. 인덱스 2의 위치한 값 2는 인덱스 1에 위치한 값 4보다 우선수위가 높음 4는 +1 인덱스로 위치함. 3441 (2는 다른 변수에 값을 저장하고 있음) 인덱스 0의 값 3은 2보다 우선순위가 낮음 그러므로 +1 인덱스오 위치함 3341(마찬가지로 2는 다른 변수에 값을 저장하고 있음) 배열에 인덱스 0보다 작은 값을 나타내는 부분이 생각날텐데 그래서 두번째 for의 조건을 보면 j..

티스토리툴바