https://www.acmicpc.net/problem/1260 문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결..
Koala - 15기
https://www.acmicpc.net/problem/15650문제풀이from itertools import combinationsn, m = map(int, input().split())arr = [i for i in range(1, n+1)]for s in combinations(arr, m): print(*s)1. 전 문제인 15649에서 오름차순이라는 조건이 추가2. 순열-> 조합으로 생각하여 품
https://www.acmicpc.net/problem/10972알고리즘 분류수학조합론from itertools import permutations as pminput = __import__('sys').stdin.readlineN = int(input())num_tuple = tuple(map(int, input().split()))state = 0for i in pm(range(1,N+1),N): if num_tuple == tuple(range(N, 0, -1)): print(-1) break if state: print(' '.join(map(str, i))) break if i == num_tuple: state ..
https://www.acmicpc.net/problem/1697문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.출력수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.입출력 예제코드..
https://www.acmicpc.net/problem/1718문제 풀이1. 평문과 암호화 키 입력받기2. 평문 길이만큼 반복 -> 문자가 소문자라면 -> 해당 문자와 암호화 키의 차이 구하기3. 차이에 맞는 소문자로 반환하여 리스트에 저장4. 해당 리스트 출력문제 코드s = list(input())key = list(input())for i in range(len(s)): if 97
1260번: DFS와 BFS (acmicpc.net)import sysinput = sys.stdin.readlinen,m,v=map(int,input().split())di={}for _ in range(m): a,b=map(int,input().split()) if a in di: di[a].append(b) di[a]=sorted(di[a], reverse=True) else: di[a]=[b] if b in di: di[b].append(a) di[b] = sorted(di[b], reverse=True) else: di[b]=[a]def DFS(start): #깊이~후입선출=스택 st=list() visit=..
https://www.acmicpc.net/problem/1032문제풀이arr 리스트에 파일 이름들을 저장한다. 그리고 각각의 파일이름의 한 글자씩을 서로 비교한다. 만약 하나라도 한 글자가 다르면 "?"를 출력하고 아니면 글자를 출력한다.소스코드N = int(input())arr = []for i in range(N): arr.append(input())for i in range(len(arr[0])): x = arr[0][i] check = True for j in range(1, N): if x != arr[j][i]: check = False break if check: print(x, end='') ..
문제 & 링크https://www.acmicpc.net/problem/11660 풀이1. 테이블에 값을 입력 할 때 시작점인 (1, 1)부터 현재 위치인 (i, j)까지의 전체 누적합을 dp 테이블에 저장한다. 설명: 현재 위치까지의 누적합을 저장하기 위해서는 빨간 사각형(dp[i - 1][j])과 파란 사각형(dp[i][j - 1])을 더하고 둘이 겹치는 부분(dp[i - 1][j - 1])을 빼준 뒤 현재 위치의 값을 더해주면 된다. 2. 원하는 범위의 누적합을 구할 때 1에서 만든 dp 테이블을 이용하여 구한다.설명: 원하는 범위의 누적합인 초록 사각형을 구하기 위해서는 전체 사각형(dp[x2][y2])에서 빨간 사각형(dp[x1 - 1][y2])과 파란 사각형(dp[x2][y1 - 1])을 빼준 ..
문제 & 링크https://www.acmicpc.net/problem/1644 풀이1. 에라토스테네스의 체를 이용하여 4,000,000까지의 모든 소수를 구해준다. (2부터 4,000,000까지 반복문을 이용하여 탐색한다. 탐색된 수 자기 자신을 제외한 모든 배수들을 bool 타입을 이용해서 체크한다.)2. 반복문을 마친 후 체크되지 않은 수들이 곧 소수이기에, 이를 따로 배열에 저장한다.3. 투 포인터(i = 0, j = 1)를 이용하여 해당 인덱스에 임시 연속합(tmp)을 만든다.4. N이 소수일 경우 cnt를 1 증가시킨다.5. 임시 연속합(tmp)이 N보다 클 경우 임시 연속합에서 i 인덱스에 해당하는 소수를 빼고, i를 증가시킨다.6. 임시 연속합(tmp)이 N보다 작을 경우 j를 증가시키고,..
https://www.acmicpc.net/problem/10451Algorithm순열이 주어졌을 때, 존재하는 사이클의 수를 출력하는 문제이다. 문제에서 주어지는 순열 순서대로 graph에 넣어주면 [[3], [2], [7], [8], [1], [4], [5], [6]] 와 같은 그래프가 만들어진다.우리는 존재하는 사이클의 수를 알고 싶기 때문에, bfs를 돌면서 모든 그래프를 방문할 때까지 시작점을 달리하여 반복해 주면 된다.cycle_cnt = 0 while (False in visited): start_p = visited.index(False) bfs(graph,start_p,visited) cycle_cnt+=1즉, 반복문을 통해 bfs를 돌린후에 ..
https://www.acmicpc.net/problem/1158 K번 쨰 수가 되기 직전까지 맨 앞의 원소를 K-1 번 꺼내오고(poll) 꺼내온 원소들을 맨 뒤로 넣는다.(offer)그리고 K번째로 뽑힌(poll) 원소는 출력하면 된다. import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { Buf..
문제 풀이math 모듈을 이용하면 쉽게 최대공약수를 구할 수 있다.a, b의 최소공배수는 a * b / gcd(a, b)임을 이용한다코드
