파이썬
[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] 백준 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] 백준 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)로 계산하자는 것이다. 이 방식으로 하면 위..
[BaekJoon] 백준 1992번 쿼드트리
[BaekJoon] 백준 1992번 쿼드트리 문제: https://www.acmicpc.net/problem/1992 내코드 문제를 이해하는게 제일 어려웠다. 주어진 설명으로 이해가 가지 않았다. 다른분들이 써놓은 걸로 문제를 이해 했는데, 배열이 주어지면 모두 같은 수 인지 확인하고 맞으면 해당 수를 넣고, 아니면 4등분해서 각각 같은 수 인지 확인하고.. 반복하는 것이다. 간단하게 재귀로 풀었다. 4등분으로 나누고 다시 4등분으로 나누고.. 이렇게 반복하는 과정에서 재귀가 떠올랐다. 다만 재귀로 풀 때에는 조건에 맞게 종료해주는게 중요하다. 특정 조건에 충족했을 때 맞는 값을 반환하는 것이 그나마 제일 까다로웠다. # BaekJoon 1992.py def solution(arr, pos, x, y, ..
[BaekJoon] 백준 1541번 잃어버린 괄호
[BaekJoon] 백준 1541번 잃어버린 괄호 문제: https://www.acmicpc.net/problem/1541 괄호를 쳐서 최소값이 나오게 만들라는 문제였다. 예시를 보면 55-50+40 의 경우 (55-50+40)이면 45이지만 55-(50+40)이면 -35이다. 이렇게 괄호 위치에 따라 값이 달라질 수 있다. 우선 별다른 알고리즘이 생각나지 않아 규칙을 생각해보았다. 식이 주어졌을 때, - 뒤의 계산값이 크면 클수록 좋고, - 앞의 계산값은 작으면 작을 수록 우리가 원하는 값이 나온다. 두가지로 경우를 나눌 수 있다. (연속으로 같은 연산자가 나올 수 없기 때문) 먼저 -가 먼저 나올 경우 80-30+20-30 이와 같이 나오면 80-(30+20)-(30) 이와 같이 괄호를 치면 모두 음..