728x90 백준 풀이103 [백준/BOJ] - 11659번 python 풀이 - dp dp 문제를 푸는 것 처럼 합을 배열에 미리 저장해 두고 주어진 범위에 따라 배열에서 찾아 마이너스 해주면 풀리는 문제 리스트 활용(누적합 미리 저장) - 성공 import sys input = sys.stdin.readline n,m = map(int,input().split()) arr = list(map(int,input().split())) sum = [0] total = 0 for i in arr: total += i sum.append(total) for _ in range(m): a,b = map(int,input().split()) print(sum[b] - sum[a-1]) 리스트 활용 - 시간 초과 import sys input = sys.stdin.readline n,m = map(i.. 2023. 4. 17. [백준/BOJ] - 1620번 python 풀이 - dict 시간 복잡도가 비교적 적은 딕셔너리를 사용하면 좋은 문제이다. idx를 통해 포켓몬을 조회할 수 있고 포켓몬을 통해 idx를 조회할 수 있게 딕셔너리에 값을 반대로도 저장한다. 입력값을 확인할 때 숫자로 이루어진 str인지 아닌지를 판별하기 위해 temp.isdigit() 을 활용하였다. 처음 본 문법. 이전 한화 코딩테스트 때 해당 문법을 알았다면 금방 풀었을 문제가 있었다. 문자열 처리 문제에서 은근 유용하게 쓰일듯 여튼 숫자 str 여부 판별해서 dic에서 값 찾아서 출력하면 끝 통과 case import sys input = sys.stdin.readline n,m = map(int,input().split())#총 포켓몬 수, 문제 수 dic = {} for i in range(1,n+1): a.. 2023. 4. 14. [백준/BOJ] - 9375번 python 풀이 - dict result 값이 어떻게 도출되는지 알아야한다. 카테고리 별로 아이템이 몇가지 있는지 확인하고 카테고리가 A,B 2가지 있다고 가정하면 result = (A카테고리 아이템의 수 + 1) * (B카테고리 아이템의 수) -1이 된다. 조합을 생각하는 문제이므로 해당 카테고리의 아이템을 착용하지 않았을 때와 각각 착용했을 때의 경우의 수는 (해당 카테고리의 아이템의 수 + 1)이다. 추가적으로 다른 카테고리의 아이템과 동시에 착용할 수 있으므로 곱연산을 진행한다. 다만, 모든 카테고리의 아이템을 사용하지 않을 경우까지 계산이 되기 때문에 해당 경우를 제거해야한다.(1을 빼주는 이유) 카테고리 별로 값을 저장시켜야하므로 딕셔너리를 사용하여 values 부분에 set 자료형을 사용하면 간단하게 풀리는 문제이다. .. 2023. 4. 12. [백준/BOJ] - 9205번 python 풀이 - bfs 문제를 잘 파악하자 1. 현재 좌표 기준으로 페스티벌에 갈 수 있는지 항상 확인한다. - 갈 수 있으면 "happy"를 출력하고 bfs 함수 return 2. 불가능할 경우 - 편의점 좌표를 입력할 때 저장시킨 리스트를 가지고 반복문을 돌린다. - 해당 idx의 편의점 방문 기록이 없을 경우 해당 편의점 좌표를 뽑아내어 현재 좌표에서 해당 편의점으로 바로 갈 수 있는지 여부를 확인한다. - 가능하다면 queue에 해당 좌표를 저장시키며 방문처리를 진행한다. (방문처리는 편의점 좌표만을 위한 것이다.) - 이런식으로 하다가 페스티벌 좌표로 접근 가능 할 경우 "happy" 출력하고 종료 - happy 출력 부분에서 return하지 못했을 경우 커서가 while문 바깥에 도달하게 될 것이므로 해당 위치에 ".. 2023. 4. 5. [백준/BOJ] - 1240번 python 풀이 - bfs 노드와 노드 사이의 거리를 저장해주어야 하는데 값 입력 받았을 때 어떤식으로 저장해야할지 고민해야하는 문제 bfs로 돌리면 함수의 매개변수가 최초 시작점, 도착 지점으로 고정되기 때문에 변수를 가져다 쓰기 용이 queue에 기준 노드와 연결되어있는 (노드, 거리)를 append 해준다. append 할 때 누적 distance를 계산하여 넣어준다. queue에서 꺼낸 노드와 도착지 노드가 동일할 경우 누적 distance를 출력 import sys from collections import deque def bfs(start, end): q = deque() q.append((start,0)) #노드, 누적 거리 ok = [False] * (n+1) ok[start] = True while q: nd, .. 2023. 4. 4. [백준/BOJ] - 6118번 python 풀이 - bfs 문제를 정확히 읽읍시다. 1. 1번 헛간에서 가장 먼 헛간을 찾아라 2. 1번에서 시작하고 bfs로 돌리면 근처에 있는 노드들을 우선 탐색하기 때문에 depth를 계산하기 용이하다. 3. idx값을 구해야하므로 enumerate를 활용하면 값을 쉽게 얻을 수 있다. import sys input = sys.stdin.readline from collections import deque n, m = map(int,input().split()) #노드 수, 라인 수 arr = [[] for _ in range(n+1)] depth = [0 for _ in range(n+1)] ok = [False] * (n+1) for _ in range(m): a,b = map(int,input().split()) arr.. 2023. 4. 3. 이전 1 2 3 4 5 6 7 ··· 18 다음 728x90
