알고리즘||코딩테스트

https://www.acmicpc.net/problem/15787 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net 사용한 알고리즘 : 비트마스킹 풀이 전략 : 기본값을 2^20으로 두고 비트마스크를 통해 승객을 태우거나 하차시킨다. default=Math.pow(2,20) 최초 기차의 상태는 00000 00000 00000 00000 이다. 여기서 비트 마스킹에 사용할 값인 default를 1 00000 00000 00000 00000 로 두고 아래 명령에 따라 변화하는 기차 상태값을 살펴보자. ..

https://www.acmicpc.net/problem/17419 17419번: 비트가 넘쳐흘러 🎶 DJ욱제는 비트에 몸을 맡기는 중이다. 🎶 DJ욱제는 비트에 심취한 나머지, 비트를 비틀어 제껴버리는 문제를 내 버렸다! N자리 이진수 K가 주어진다. K가 0이 아닐 때까지 아래의 연산을 적용 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String args[]) throws IOException{ BufferedRe..

https://www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net import sys input=sys.stdin.readline n=int(input()) result=[0]*(50*20+1) #50이 20번 쓰여 더해진게 최대값이므로 RomaNum=[1,5,10,50] buf=[] cnt=0 def recur(x,start): if x==n: result[sum(buf)]=1 return for i in range(start,4): buf.append(RomaNum[i]) recur(x+1,i) buf.pop() recur(0,0) print(sum(re..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import sys input=sys.stdin.readline N,M=map(int,input().split()) visited=[False]*(N+1) result=[] def back_Tracking(x): if x==M: print(' '.join(map(str,result))) return for i in range(1,N+1): result.append(i) back_Tracking(..

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import sys input = sys.stdin.readline N,M=map(int,input().split()) visited=[False]*(N+1) result=[] def recur(x): if x==M: print(' '.join(map(str,result))) return for i in range(1,N+1): if visited[i]==False and (len(result)..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import sys input=sys.stdin.readline n,m=map(int,input().split()) visited=[False]*(n+1) result=[] def recur(x): if x==m: print(' '.join(map(str,result))) return for i in range(1,n+1): if visited[i]==False: visited[i]=True r..

https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net import sys from collections import deque n,m,r=map(int,sys.stdin.readline().split()) graph=[[] for _ in range(n+1)] visited=[0 for _ in range(n+1)] def bfs(start): cnt=1 visited[sta..

https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net import sys sys.setrecursionlimit(10**5) n,m,r=map(int,sys.stdin.readline().split()) visited=[0 for _ in range(n+1)] graph=[[] for _ in range(n+1)] cnt=1 def dfs(start): global cnt vi..

https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net import sys k=int(sys.stdin.readline()) array=list(map(int,sys.stdin.readline().split())) layer=[[] for _ in range(k+1)] for n in range(k,0,-1): i=0 while 2**(k-n)+i*(2**(k-n+1))

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net import sys class Node: def __init__(self,data,left_node,right_node): self.data=data self.left_node=left_node self.right_node=right_node nodes={} def pre_order(node): print(node.data,end='') if node.left_node!=None: pr..