CS/Algorithm 문제
[BaekJoon] 백준 18870번 좌표 압축
[BaekJoon] 백준 18870번 좌표 압축 문제: https://www.acmicpc.net/problem/18870 내코드 처음 문제를 풀었을 때 시간초과가 났다. 이유가 뭘지 고민하다가 검색해보니까 다른 사람도 나와 같이 풀어서 시간 초과가 난 경우가 많았다.(역시 사람 생각하는건 다 똑같..) 문제는 index 메서드였다. index 메서드는 O(N)의 시간 복잡도를 가지기 때문에 for문 안에서 N*N이 되어 시간이 오래 걸리는 거였다. # 틀린 코드 # BaekJoon18870.py N = int(input()) arr = list(map(int, input().split())) sorted_arr = sorted(list(set(arr))) for i in range(N): arr[i] ..
[BaekJoon] 백준 2630번 색종이 만들기
[BaekJoon] 백준 2630번 색종이 만들기 문제: https://www.acmicpc.net/problem/2630 내코드 재귀로 푸는 쉬운 문제였다. 배열 정보를 받아서 한변의 길이 & x 좌표 & y 좌표 이렇게 3개의 값으로 사분면 모두를 돈다. 만약 특정 사분면의 모든 값이 같다면 더이상 자를 필요가 없으므로 해당 색상 + 1 을 해주고 해당 사분면을 확인하는 것을 종료하고 만약 특정 사분면의 모든 값이 같지 않다면 한번더 4등분해서 들어간다(재귀). def checkSame(n, x, y): global arr value = arr[x][y] for i in range(n): for j in range(n): if arr[x + i][y + j] != value: return False ..
[BaekJoon] 백준 1620번 나는야 포켓몬 마스터 이다솜
[BaekJoon] 백준 1620번 나는야 포켓몬 마스터 이다솜 문제: https://www.acmicpc.net/problem/1620 내코드 처음엔 무작정 배열에 넣어풀어봤다. 역시나 시간초과가 났다. N, M 최대값이 100,000인데 python의 list 자료형에서 index 메서드의 시간 복잡도가 O(n)이라서 총 O(M*N)의 시간 복잡도가 나오기 때문인가보다. 1억당 1초라 하면 100,000 * 100,000를 게산하면 1억을 훌쩍 넘겨버린다. # 틀린코드 N, M = map(int, input().split()) arr = ["" for _ in range(N)] for i in range(N): arr[i] = input() for _ in range(M): question = inp..
[BaekJoon] 백준 1074번 Z (Python)
[BaekJoon] 백준 1074번 Z 문제: https://www.acmicpc.net/problem/1074 내코드 처음에 생각한 방식은 다음과 같다. 1. 한변 길이가 4이상이면 나눠서 재귀로 돌기 2. 한변 길이가 2이면 r, c에 맞는 위치가 있는지 확인하고 없으면 다음 사분면 돌기 하지만 이렇게 하면 시간 초과가 났다. # 잘못 푼 코드 # BaekJoon1074.py def solv(n, x, y): global result if n == 2: if y == r and x == c: print(result) exit() elif y == r and x+1 == c: print(result + 1) exit() elif y+1 == r and x == c: print(result + 2) ex..
[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..