alpaca Labs 님의 블로그

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]))모르겠어서 검색해보니 누적 합을 사용하면 된다고 한다.더보..

https://www.acmicpc.net/problem/7576해당 문제는 탐색 문제 이다. 해당 문제를 풀때 고민했던 점은 날짜수를 세기 위해서는 날짜수를 세야 하므로 하루가 지날때 익는 토마토를 어떻게 분리하여 구하는지 였다. 그리하여 그 다음날 익을 토마토를 저장하는 stack 을 2개 만들어서 stack1에는 그 다음날 익을 토마토를 넣어주고 stack2 에는 다음날 익을 토마토가 무엇인지 찾아서 넣어주고 그날이 끝나면 초기화 해준다.import sysinput = sys.stdin.readlinecol_length, row_length = map(int,input().split())box = list()stack1 = stack2 = list()for _ in range(row_length):..

https://www.acmicpc.net/problem/2805해당 문제에서 발생할 수 있는 문제는 시간 초과와 이를 해결할 이진탐색이다.n , m = map(int,input().split())trees = list(map(int,input().split()))hightree = max(trees)result = 0low , high = 0 , max(trees) ### low에 m-1 이 아닌 0을 넣어야 함while low mid : total += tree - mid if total >= m: # 원하는 값보다 크면 전기톱 길이를 늘려야 더 적게 나오므로 low의 값을 높여준다. result = mid low = mid + 1 else:..

https://www.acmicpc.net/problem/1927해당 문제를 풀기 위해서는 우선순위 큐와 힙에 대해서 알아야 한다. 이를 위해 chat gpt 에게 물어보았다.우선순위 큐 (Priority Queue)우선순위 큐는 각 요소에 우선순위를 부여하여, 우선순위가 높은 요소가 먼저 처리되는 자료 구조입니다. 일반적인 큐(FIFO)와 달리, 요소는 우선순위에 따라 나열되고 처리됩니다. 우선순위 큐의 구현에는 다양한 방법이 있지만, 가장 일반적으로 사용하는 방법 중 하나는 **힙(Heap)**을 사용하는 것입니다.힙 (Heap)힙은 완전 이진 트리의 형태를 가지며, 부모 노드의 값이 자식 노드의 값보다 항상 크거나 작도록 하는 특성을 갖습니다. 힙은 크게 두 종류로 나뉩니다:최대 힙(Max Heap..

https://www.acmicpc.net/problem/1764딕셔너리를 사전순으로 정렬하는 것만 잊지 않으면 된다.import sysinput = sys.stdin.readlinen , m = map(int,input().split())people = dict()peoplelist = list()for _ in range(n+m): temp = input().rstrip() if temp in people: people[temp] += 1 else: people[temp] = 1count = 0for i in sorted(people): if people[i] >= 2: count += 1 peoplelist.append(i)pr..