CS
[BaekJoon] 백준 11047번 동전 0
[BaekJoon] 백준 11047번 동전 0 문제: https://www.acmicpc.net/problem/11047 내코드 최소한의 동전으로 값을 표현해야한다. 그 순간 가장 최선의 선택인 특정 값보다 작은 값중 가장 큰 값을 선택해야 하므로 그리디 알고리즘이다. # BaekJoon11047.py n, k = map(int, input().split()) arr = [] for _ in range(n): arr.append(int(input())) result = 0 arr.sort(reverse=True) for i in arr: if k==0: break result += k // i k %= i print(result)
[BaekJoon] 백준 9461번 파도반 수열
[BaekJoon] 백준 9461번 파도반 수열 문제: https://www.acmicpc.net/problem/9461 내코드 i번째 수 + (i+1)번째 수의 합이 i+3번째에 놓이게 된다. 이를 이용해서 문제를 풀면 된다. # BaekJoon9461.py arr = [0 for i in range(101)] arr[1] = 1 arr[2] = 1 arr[3] = 1 for i in range(0, 98): arr[i + 3] = arr[i] + arr[i + 1] t = int(input()) for i in range(t): n = int(input()) print(arr[n])
[BaekJoon] 백준 9375번 패션왕 신해빈
[BaekJoon] 백준 9375번 패션왕 신해빈 문제: https://www.acmicpc.net/problem/9375 내코드 경우의 수로 푸는 수학문제였다. 각각 옷의 종류에 따라서 만약 a종류의 옷이 3벌이 있다면 각각을 선택하는 수 3 + 아무것도 선택안하는 경우 1가지 해서 총 4가지가 있고, b종류가 2벌이 있다면 동일하게 계산해서 3가지가 된다. 따라서 a종류 3벌, b종류 2벌이라면 4X3 = 12이고 각각 옷의 종류에서 아무것도 선택안하는 경우를 빼면 11가지가 답이된다. 이와 같이 코드를 작성해주면 된다. # BaekJoon9375.py test_case = int(input()) for _ in range(test_case): n = int(input()) clothe_type = ..
[BaekJoon] 백준 9019번 DSLR
[BaekJoon] 백준 9019번 DSLR 문제: https://www.acmicpc.net/problem/9019 내코드 가장 빠른 경우를 찾은 전형적인 BFS문제였다. 그런데 어떤 식으로 풀어도 시간초과 문제가 해결되지 않아서 pypy로 풀었더니 해결되었다. # BaekJoon9019.py from collections import deque import sys def solution(): visited = [False for _ in range(10000)] queue = deque([[a, ""]]) visited[a] = True while len(queue) != 0: value = queue.popleft() if value[0] == b: return value[1] # D next_va..
[Algorithm] 백트래킹 (Backtracking)
[Algorithm] 백트래킹 (Backtracking) 백트래킹이란, 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘을 말한다. 답을 찾는 도중 답이 아니어서 막히면, 되돌아가서 다시 답을 찾아간다. 단, "조건을 만족" 할때 만이다. 즉, 모든 경우의 수를 모두 찾는 것보다 경우에 따라 훨씬 빠를 수 있다. 주로 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현한다. 백트래킹 기법의 유망성 판단 어떤 값이 해가 될만하다면 유망하다(promising)고 하며, 유망하지 않은 값에 가지 않는 것..
[Algorithm] 트리 Tree
[Algorithm] 트리 Tree 트리란? 트리란 어떤 노드들의 집합으로 노드들은 각 서로 다른 자식을 가지며 이때 각 노드는 재사용 되지 않는 구조이다. 말로 풀어내면 복잡할 수 있는데 그림으로 보면 한눈에 이해가 간다. 트리와 관련된 용어 노드 node: 트리는 노드들의 집합으로 트리를 구성하는 것으로 보통 값과 부모 자식의 정보를 가지고 있다. 엣지/간선 edge: 엣지는 노드들을 연결하는 간선으로 부모 노드와 자식 노드를 연결하게 된다. 루트 노드 root node: 가장 상위 노드로 부모를 가지지 않는다. 리프 노드 leaf node: 가장 하위 노드로 자식을 가지지 않는다. 형제 노드 sibling node: 같은 부모를 가지는 자식 노드들을 말한다. 노드의 깊이 depth: 트리에서 부모에..
[BaekJoon] 백준 2606번 바이러스
[BaekJoon] 백준 2606번 바이러스 문제: https://www.acmicpc.net/problem/2606 내코드 간단하게 bfs로 풀 수 있는 탐색문제였다. dfs로도 풀 수 있을 것 같은데 다음에는 dfs로도 풀어봐야겠다. # BaekJoon2606.py from collections import deque def solution(N, M): link = [[] for _ in range(N)] visited = [False for _ in range(N)] for i in range(M): a, b = map(int, input().split()) link[a - 1].append(b - 1) link[b - 1].append(a - 1) qu = deque([0]) visited[0] ..
[BaekJoon] 백준 17626번 Four Squares
[BaekJoon] 백준 17626번 Four Squares 문제: https://www.acmicpc.net/problem/17626 내코드 문제 내용은 간결했지만 어떤식으로 풀어야 할지 생각이 필요했던 문제다. 더군다가 시간도 0.5초로 짧은 편이라서 무작정 구현하기에는 무리였다. 문제에서 가장 중요한 조건은 결국 어떤 수든 답은 1, 2, 3, 4 중에 하나라는 의미이다. 즉, 주어진 수가 정수의 제곱수면 1, 어떤 정수 i에 대해 n - i^2의 제곱근이 정수면 2, 어떤 정수 i, j에 대해 n - i^2 - j^2의 제곱근이 정수면 3, 그외의 경우는 모두 4라는 의미이다. # BaekJoon17626.py def solution(n): # n이 제곱근이 정수라면 답은 1 if int(n**0..