![]()
문제 풀이테스트 케이스의 수를 받고 큐 자료구조에 중요도를 넣는다.주어진 입력값 중 m 값을 계속 바꾸며 내가 찾는 문서가 어디 있는지 추적한다.문서를 인쇄할 때마다 카운트를 늘려 몇 번째로 출력되는지를 찾는다.내가 찾는 문서가 가장 앞에 있고, 중요도가 최댓값과 같다면 그 때 출력할 수 있음을 유의하며 코드를 작성한다.코드from collections import deque t = int(input()) for _ in range(t): n, m = map(int, input().split()) lst = list(map(int, input().split())) q = deque() cnt = 1 for i in lst: q.append(i) ..
https://www.acmicpc.net/problem/4963문제정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.입력/출력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개..
![]()
https://www.acmicpc.net/problem/4963구상1. 가로, 세로 뿐만 아니라 대각선도 있으니 이를 고려해야겠다. 8번 반복해야겠네.2. bfs방식이겠다.3. bfs가 몇번 반복됐는지 보면 섬의 개수가 나오겠다.코드#include #include #include using namespace std;int map[51][51];bool visit[51][51];int w, h;int dx[] = {0,0,-1,1,1,1,-1,-1}; // 대각선까지 고려해아함int dy[] = {1,-1,0,0,1,-1,-1,1};int cnt = 0;void bfs(int a, int b){ queue> q; q.push(make_pair(a, b)); while(!q.empty()..
https://www.acmicpc.net/problem/1260 문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결..
![]()
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를 증가시키고,..
