alpaca Labs 님의 블로그

https://www.acmicpc.net/problem/9461수학 관련 문제는 규칙성만 찾으면 쉽게 풀 수 있다. 규칙성을 찾기 위해서 일단은 수기로 추가로 삼각형의 길이를 계속 구해봤다.1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, 351, 465, 616 ... 뭔가 뒤에것을 더해서 앞에 값에 추가하는 규칙성이 있는거 같아서 숫자가 커질때마다 커진 정도를 구해봤다.0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49 ...  놀랍게도 위와 숫자가 겹치는 것을 볼수 있다. 4번째 이전 숫자와 현재 숫자를 더하면 그 다음 숫자를 구할 수 있..

https://www.acmicpc.net/problem/9375입력이 아래와 같을 때23hat headgearsunglasses eyewearturban headgear3mask facesunglasses facemakeup faceheadgear 의 경우 2개 eyewear의 경우 1개가 있다.(2+1) * (1+1) - 1 = 5 이다. 옷을 입지 않는 경우가 있으므로 각 경우에 +1 을해주면 되고, 옷을 아예 안입으면 안되므로 -1 을 해준다.2번째 케이스의 경우도 (3+1) - 1 = 3 이다.test = int(input())for t in range(test): n = int(input()) cloth = dict() for _ in range(n): value ..

https://www.acmicpc.net/problem/1389해당 문제를 먼저 dfs 로 풀었는데 계속 메모리 초과가 발생하였다. import sysinput = sys.stdin.readlinen , m = map(int,input().split())nodes = [[] for _ in range(n+1)]stack1 = list()stack2 = list()result = [0 for _ in range(n+1)]for _ in range(m): start , end = map(int,input().split()) nodes[start].append(end) nodes[end].append(start)for i in range(1,n+1): count = 0 for j ..

https://www.acmicpc.net/problem/2579 해당 문제는 동적 프로그래밍으로 푸는 문제였고, 어떻게 구현하는지 몰라 gpt의 도움을 받아 작성했다. 그래도 코드에 대해서 100프로는 이해하지 못한거 같다... 다른 동적 프로그래밍 문제를 더 풀어봐야 할거 같다....stair = int(input())stairs = [int(input()) for _ in range(stair)]dp = [0 for _ in range(stair)]while True: if stair == 1: print(stairs[0]) break elif stair == 2: print(stairs[0]+stairs[1]) break dp[0]..

https://www.acmicpc.net/problem/7569해당 문제는 https://alpacalabs.tistory.com/18 와 같은 제목의 문제로 약간 만 다르다. 테스트 예제는 맞지만 계속 틀렸다고 하여 문제가 무엇인지 검색해 보았지만 의문은 해결되지 않았다. 아래는 테스는 예제는 맞지만 틀렸다고 한 코드이다.import sysinput = sys.stdin.readlinecol_length, row_length, z_length = map(int,input().split())box = list()stack1 = stack2 = list()for _ in range(row_length*z_length): box.append(list(map(int,input().split())))fo..

https://www.acmicpc.net/problem/17219딕셔너리 사용하는 되는 간단한 문제.n , m = map(int,input().split())memo = dict()for _ in range(n): key , value = map(str,input().split()) memo[key] = valuefor _ in range(m): print(memo[input()])

https://www.acmicpc.net/problem/18870좌표 압축이란 말을 이해하기 힘들어서 검색해 보았다. 검색한 결과는 다음과 같았다. 좌표 압축은 주어진 좌표들의 상대적 순위를 기반으로 새로운 값을 할당하는 것입니다. 각 좌표의 압축된 값은 해당 좌표보다 작은 서로 다른 좌표의 개수와 같아야 합니다. n = int(input())arr = list(map(int,input().split()))dic = dict()arr2 = arr[:]arr2.sort()count = 0for i in arr2: if i not in dic: dic[i] = count count += 1for i in arr: print(dic[i],end=' ')입력5 2 4 -10..

https://www.acmicpc.net/problem/14940각 좌표마다 거리를 측정해서 숫자를 지정해 주는 것은 어떻게 하는지 몰라서 고민하다가 전에 풀었던 https://alpacalabs.tistory.com/18 에 토마토 문제랑 거의 흡사하게 풀면 되겠다고 생각하고 풀었다.import sysimput = sys.stdin.readlinerow_length , col_length = map(int,input().split())visited = [[False for _ in range(col_length)] for _ in range(row_length)] Map = list()resultMap = [[0 for _ in range(col_length)]for _ in range(row_len..

https://www.acmicpc.net/problem/11724문제 자체를 이해하는것이 조금 어려웠다. 방향성이 없는 그래프이기 때문에 (1,2) (1,3) 도 2와 3이 연결된 것이라고 하는 것이다. 문제 풀이는 dfs 로 풀면 된다.import sysinput = sys.stdin.readlinen , m = map(int,input().split())edges = [tuple(map(int,input().split())) for _ in range(m)]visited = [False] * (n+1)nodes = [[] for _ in range(n+1)] # [[]] * (n+1) 을 하면 동일한 객체가 생성되기 떄문에 값을 새로 추가하면 모든 배열이 동시에 적용된다.stack = list(..

https://www.acmicpc.net/problem/11659해당 문제를 풀때는 너무 쉬운데? 라고 생각했지만 바로 시간초과가 떠버렸다...아래 코드는 맨 처음 작성했던 시간 초과가 발생한 코드이다.이대로 실행하면 구간 마다 SUM 을 실행시키기 때문에 O(n*m)의 시간 복잡도가 발생한다고 한다.import sysinput = sys.stdin.readlinen , m = map(int,input().split())arr = list(map(int,input().split()))for _ in range(m): start , end = map(int,input().split()) print(sum(arr[start-1:end]))모르겠어서 검색해보니 누적 합을 사용하면 된다고 한다.더보..