boj

[python] 백준 - 1261. 알고스팟

🤔문제 해결 G4 | 다익스트라(BFS도 가능) 다익스트라 유형으로 되어있지만 BFS도 가능한거 같다. BFS로 풀 면 길을 찾아 갈 때 0이면 그냥 가고 1이면 +1해서 가면 된다. 이 문제는 다익스트라로 풀어봤다. ( 다익스트라와 우선순위큐(힙큐)는 짝꿍 ) 주어진 미로와 같은 크기의 2차원 배열을 만든다. ( 가중치를 업데이트 해줄 배열 ) 0,0 부터 주변을 탐색하며 방(0)이면 비용을 현재비용으로 넣고, 벽(1)이면 비용을 현재비용 +1해서 업데이트 해준다. 업데이트가 된 지점을들 힙큐에 넣고 목적지가 나올 때 까지 위의 과정을 반복한다. 💻소스 코드 import heapq if __name__ == '__main__': N, M = map(int, input().split()) # 문제는 1부..

[python] 백준 - 2110. 공유기 설치

🤔문제 해결 S2 | 이분탐색 특정 범위 안에서 개수를 정한다? => 이분 탐색 공유기를 설치할 수 있는 최소간격과 최대간격의 중간값부터 시작 중간값(공유기 설치 간격)으로 공유기를 설치 했을 때 설치한 공유기가 부족하면 설치 간격을 좁혀서 더 많이 설치하자 설치한 공유기가 많거나 같으면 설치한 간격을 늘려서 덜 설치하거나 최대로 간격을 늘려보자 💻소스 코드 import sys N, C = map(int, input().split()) house = [int(sys.stdin.readline()) for _ in range(N)] # 정렬 house.sort() # 와이파이 간격을 얼마나 해야할지 모르니 최대거리와 최소거리의 중간부터 시작 left = 1 right = house[-1] - house[0..

[python] 백준 - 1780. 종이의 개수

🤔문제 해결 S2 | 분할정복 첫번째에 있는 코드가 더 정답인거 같다( 둘다 통과했지만 ) 첫번째 코드는 항상 9개의 조각으로 잘라서 진행한다. - 이게 문제랑 더 맞는거 같다. 하지만 두번째 코드는 (처음 풀어서 통과하고 다시보니 이상함) 9개의 조각이 아니다. 종이가 들어오면 3x3으로 다 잘라버린다. 그래도 통과한다. 이게 되네?? 내가 문제를 잘 이해하지 못한건지... 내가 짠 코드를 이해하지 못한건지 잘 모르겠다. 💻소스 코드 from itertools import chain # 2차원 리스트를 1차원리스트로 바꿔주는 친구 def bt(paper): global a, b, c nn = len(paper) if len(set(chain.from_iterable(paper))) == 1: if pa..

[python] 백준 - 10819. 차이를 최대로

🤔문제 해결 S2 | 완전탐색 뭔가 특별한 방법이 있는거 같아서 열심히 짜봤지만 숫자가 겨우 8개 이하이므로 순열을 사용해서 해결(문제유형도 완전탐색) 경우의 수를 전부 구함 💻소스 코드 from itertools import permutations n = int(input()) numbers = list(map(int, input().split())) result = [] for permu in permutations(numbers, n): tmp = 0 for i in range(n - 1): tmp += abs(permu[i] - permu[i + 1]) result.append(tmp) print(max(result)) 📕문제 확인 출처: BACKJOON ONLINE JUDGE 링크: https:..

[python] 백준 - 1541. 잃어버린 괄호

🤔문제 해결 S2 | 수학, 그리디 요번 구현 문제의 핵심은 최초로 마이너스가 나온순간 뒤의 모든 숫자는 음수로 진행할 수 있다!! 💻소스 코드 c = input() answer = 0 c += '*' # 문제의 핵심!! 마이너스가 최초로 한번 나오는 순간 뒤의 모든 숫자들은 마이너스로 취급한다.!!! number = '' operator = '+' for i in range(len(c)): if c[i].isdigit(): number += c[i] else: if operator == '+': answer += int(number) else: answer -= int(number) if c[i] == '-': operator = '-' number = '' print(answer) 📕문제 확인 출처:..

[python] 백준 - 1182. 부분수열의 합

🤔문제 해결 S2 | 완전탐색(백트래킹) 문제를 잘 이해하지 못해서 많이 헷갈렸다. 그냥 쉽게 설명해서 주어진 숫자들 중 n개를 뽑아서 더한 값이 S와 같은 조합이 몇개인지 구하라는 말 파이썬에서는 쉽게 콤비네이션을 쓰면 된다. 문제 유형에 백트래킹이 있으므로 백트래킹을 연습하고 싶으면 백트래킹을 써도 좋다. 💻소스 코드 from itertools import combinations N, S = map(int, input().split()) numbers = list(map(int, input().split())) answer = 0 for i in range(1, N + 1): for combi in combinations(numbers, i): # print(combi) if sum(combi) ==..