무니화니

오늘의 문제는 DFS를 통해서 푼 연산자 끼워넣기 문제이다. https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net n=int(input()) data=list(map(int,input().split())) cal=list(map(int,input().split())) answer=[] visited=[0]*(n-1) calList=[] for i in range(4): for j in range..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 이용한 문제를 풀어봤다. import sys from collections import deque def bfs(): q=deque() q.append(n) while q: num=q.popleft() if num==k: print(loc[k]) break for i in (num-1,num+1,num*2): if 0

오늘의 문제는 Well-known Problem으로 평가받는 N-Queen이다. 국내외를 막론하고 각종 언어로 solution이 유튜브에서부터 다양한 검색사이트에 나열되어 있을 정도이다. https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 DFS를 통하여 구현하였다. n=int(input()) chessBoard=[1e10]*n ans=0 def dfs(idx): global ans if idx==n: ans+=1 return for i in range..

https://www.acmicpc.net/problem/26092 26092번: 수학적인 최소 공통 조상 첫째 줄에 정수 $a$와 $b$가 공백으로 구분되어 주어진다. $(1\leq a,b\leq 10^{12})$ www.acmicpc.net 오늘의 문제는 수학적인 지식 (공약수)를 이용하여 푸는 문제였다. 설명은 어려워 보이지만, 간단히 설명하면 가령 36이라는 수가 있다. 36의 약수는 1,2,3,4,6,9,12,18,36가 있다. 그렇기에 36의 부모 노드는 2 이상의 약수 중 제일 작은 2로 나눈 수이다. (18) 해당 법칙을 이용하여 계속 나타내면 36-> 18 -> 9 -> 3 -> 1 이런식으로 부모노드가 이어진다. def factorization(n): d=2 factors=[] whil..

간단한 수학적 계산을 요구하는 문제다. 출처: https://www.acmicpc.net/problem/26217 n=int(input()) answer=0 for i in range(1,n+1): answer+=(n/i) print(answer) 정답 코드입니다. 예제 2번 밑의 부연설명과 같게, 씨앗의 개수가 n개라면, 당연히 1회차에는 n개 중 1개의 씨앗을 뿌리는 확률은 1 (n/n)입니다. 2회차에는 1회차에 뿌린 씨앗이 아닌 다른 씨앗을 뿌려야 하기에, 이에 대한 확률은 (n-1)/n입니다. 그렇기에 위 수의 역수인 n/(n-1)개의 씨앗을 뿌려야 합니다. 위와 같은 방식으로 확률들의 역수들을 더해주면 됩니다.

이번 문제는 기본 자료구조 중 하나인 힙을 이용하는 문제였다. 이 문제의 경우에는, 문제를 푸는 것은 쉽지만, 제한된 시간 내에서 푸는 것이 어려운 점이다. 최대한 시간을 줄여야 한다. from heapq import * import sys input=sys.stdin.readline n=int(input()) heap=[] for _ in range(n): n=int(input()) if n==0: if not heap: print(0) else: print(heappop(heap)[1]) else: heappush(heap,(abs(n),n)) heapq를 import 하고, heap에 push할 때 수의 절댓값과 실제값을 tuple에 넣어서 저장한다. 이렇게 되면, tuple의 첫째 자리가 inde..

오늘의 문제는 치킨 배달이라는 문제이다. (골드 5) DFS를 통해서 해결방법을 구현하였다. 해결 코드이다. import sys input=sys.stdin.readline def dist(a,b): return abs(a[0]-b[0])+abs(a[1]-b[1]) n,m=map(int,input().split()) data=[] for i in range(n): data.append(list(map(int,input().split()))) chicken=[] house=[] for i in range(n): for j in range(n): if data[i][j]==1: house.append([i,j]) elif data[i][j]==2: chicken.append([i,j]) dists=[] fo..

이 문제는 dfs와 유사한 방법 (백트래킹)으로 풀 수 있다. https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 풀이 n=int(input()) data=[] for i in range(n): data.append(list(map(int,input().split()))) res=0 def solve(idx,data): global res if idx==n: cnt=0 for i in range(n): if data[i][0]

오늘의 문제는 DFS와 브루트포스를 함께 사용하는 문제이다. https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이 문제에서 포인트는 '같은 팀의 팀원에 따라서 개인의 능력치가 달라진다'이다. 그렇기 때문에 각 팀의 팀원을 설정하고, 이 때의 두 팀의 능력치의 합의 차이를 구하는 방식으로 해결해보았다. 문제에 주어진 예시를 보면, 이와 같은 식으로 해결할 수 있다. def dfs(start,depth): global minDiff if depth==peopleEachT..

이번 문제는 저번에 풀었던 순열 관련 문제와 유사하다. 처음에 생각했던 방법은, 저번에 풀었던 것과 유사하게 dfs를 이용하여 푸는 것이였다. n=int(input()) nums=list(map(int,input().split())) answer=[] result=[] visited=[False]*(n+1) def solve(d,n): if d==n: answer.append(result[:]) return for i in nums: if not visited[i]: visited[i]=True result.append(i) solve(d+1,n) visited[i]=False result.pop() solve(0,n) answer.sort() a=answer.index(nums) if nums==ans..