분류 전체보기
[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..
[BaekJoon] 백준 1931번 회의실 배정
[BaekJoon] 백준 1931번 회의실 배정 문제: https://www.acmicpc.net/problem/1931 내코드 처음에는 이해하기 어려워서 고민하다가 다른 분들은 어떻게 풀었는지 참고해서 풀었다. 핵심은 빨리 끝나는 순으로 정렬 후 끝나는 시간이 같다면 빨리 시작하는 순으로 정렬하는 것! 어쨌건 현재 상황에서 가장 최선의 선택(빨리 끝나는 순으로 정렬)을 한다는 점에서 그리디 알고리즘이라고 볼 수 있다. 코드에서 파이썬의 sort함수를 사용해 줬고, 그 안에 lamda라는 인자가 있는데 처음엔 처음 보는 lamda라서 뭔지 찾아보고 구현했다. 아래와 같이 써주면 e라는 배열을 정렬할건데, 0번째 값을 우선으로 오름차순으로 나열하고, 이후에 1번째 값을 기준으로 내림차순으로 구현한다는 의미..
[BaekJoon] 백준 1927번 최소 힙
[BaekJoon] 백준 1927번 최소 힙 문제: https://www.acmicpc.net/problem/1927 내코드 우선 순위큐에서 힙을 이용해 푸는 문제다. 파이썬에는 힙 모듈이 있어 이를 이용해서 풀었다. # BaekJoon1927.py import sys import heapq input = sys.stdin.readline number = int(input()) heap = [] for _ in range(number): num = int(input()) if num != 0: heapq.heappush(heap, num) else: try: print(heapq.heappop(heap)) except: print(0)
[BaekJoon] 백준 11659번 구간 합 구하기 4
[BaekJoon] 백준 11659번 구간 합 구하기 4 문제: https://www.acmicpc.net/problem/11659 내코드 우선 문제를 처음 봤을 때 주어진 숫자를 가지고 정직하게 풀었을 때 시간이 부족할 것이라는 생각이 들었다. N개의 숫자들 중에서 특정 구간을 M번 더해야 하는 경우를 생각해보면, 최악의 경우 100,000(처음부터 끝까지 모든 수(N의 최대값)를 더했을 때 덧셈의 횟수) X 100,000(합을 구해야 하는 횟수 M의 최대값)은 1억을 넘어가고 1억을 약 1초라고 했을 때 한참 넘어가기 때문이다. 그래서 생각한 방식이 첫번째 수부터 n번째 수까지 더한게 f(n)이라고 하면 i번째~j번째 구간의 합은 f(j) - f(i - 1)로 계산하자는 것이다. 이 방식으로 하면 위..