Berom's Blog

백준 11724 연결 요소 개수문제방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 풀이문제 푸는 흐름은 맞는데 BFS와 DFS 개념이 아직 덜 잡힌 것 같다. DFS 풀이123456789101112131415161718192021222324252627282930import syssys.setrecursionlimit(10000)n,m = map(int,sys.stdin.readline().split())nodes = [[] for i in range(n+1)]nodes[0]=[0,0]check = [False for _ in range(n+1)]c ...

백준 11659 구간 합 구하기 4문제수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 풀이123456789101112import sysn,m = map(int,sys.stdin.readline().split())numbers = list(map(int,sys.stdin.readline().split()))sums = [0,numbers[0]]for num in range(2,len(numbers)+1): sums.append(sums[num-1]+numbers[num-1])for i in range(m): start,end=map(int,sys.stdin.readline().split()) print(sums[end]-sums[start-1]) 간단한 문제인데, 계속 시간 초과가 나왔었다.구간 합을 구할 때마다 계속 반복되는 연산이 많아 그런거라, 합을 미리 구해 빼서 해결하였다

백준 1260 DFS와 BFS문제풀이12345678910111213141516171819202122232425262728293031323334353637import sysfrom collections import dequen,m,v =map(int,sys.stdin.readline().split())nodes = [[] for _ in range(n+1)]check = [False for _ in range(n+1)]for i in range(m): node1,node2 = map(int,sys.stdin.readline().split()) nodes[node1].append(node2) nodes[node2].append(node1)for i in range(1,n+1): nodes[i].sort()def bfs(v): check[v]=True q = deque([v]) while q: node=q.popleft() ...

백준 1303 전쟁 - 전투문제풀이12345678910111213141516171819202122232425262728293031323334353637383940414243444546import sysfrom collections import dequeN,M = map(int,sys.stdin.readline().split())mp = []for i in range(M): mp.append(list(sys.stdin.readline().rstrip()))visited=[[False] * N for _ in range(M)]W, B = [], []dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]def bfs(x, y): q = deque([(x, y)]) color = mp[x][y] count=0 while q: x, y = q.popleft() for i in range(4): nx,ny= ...

백준 1373 2진수 8진수문제2진수가 주어졌을 때, 8진수로 변환하는 프로그램을 작성하시오. 풀이파이썬에서는 내장 함수로 8진수 변환 함수인 oct가 존재한다.또한 int()의 경우 매개 변수를 이용해서 2진수로 표현할 수 있다. int(input(),2)는 입력 받은 십진수를 2진수로 바꿔준다. 코드1print(oct(int(input(),2))[2:])

백준 1389 케빈 베이컨의 6단계 법칙문제BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오. 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다.둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다.A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다.친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다.모든 사람은 친구 관계로 연결되어져 있다.사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다. 풀이1234567891011121314151617181920212223242526272829import sysfrom collections import dequen,m= map(int, sys.stdin.readline().spl ...

백준 1463 1로 만들기문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 풀이 그리디 알고리즘 문제가 아니다 10의 경우 10 - 9 - 3 - 1 로 3번 만에 만든다 그리디 알고리즘 문제라면 10 - 5 - 4 - 2 - 1 로 4번 시도해야한다 그리디 알고리즘으로 풀 경우의 해가 유효성이 검증되지 못했다. 메모제이션 기법을 사용한다 10 - 9 - 3 - 1로 10의 해를 구한다. 이 때 3은 (1을 구하는 횟수 + 1), 9는 (3을 구하는 횟수 + 1)이 성립한다 주어질 숫자의 최소 횟수를 아래서부터 계속 만들어가면, 최솟 값을 구할 수 있다. 코드12345678910111213import sysnum = int(sys.s ...

백준 1541 잃어버린 괄호문제세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 풀이12345678910111213141516171819202122232425262728293031import sysfrom collections import dequesen =sys.stdin.readline().rstrip()sentence = deque([i for i in sen])numbers,op=[],[]temp=''while sentence: x = sentence.popleft() if 48<=ord(x)<=57: temp+=x else: numbers.append(int(temp)) temp=&#x ...

백준 15654 N과 M (5)문제N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 풀이12345678import sysfrom itertools import permutationsN,M=map(int,sys.stdin.readline().split())numbers = list(map(int,sys.stdin.readline().split()))numbers.sort()for n in permutations(numbers, M): print(*n)

백준 1697 숨바꼭질문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 풀이bfs 개념을 직접 문제에 적용해본 적이 없어서, 그걸로 어떻게 문제를 푼다는거지? 했었다. 12345678910111213141516171819import sysfrom collections import dequen,k = map(int,sys.stdin.readline().spli ...