문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 Dfs는 재귀, Bfs는 큐를 사용한다.(시간복잡도가 낮은 덱을 사용) 2차원 배열로 노드 연결여부를 구성. 최초 모든 연결을 False로 초기화 입력값에 따라 (시작노드,끝노드), (끝노드,시작노드)를 True로 만들어줌.(연결되었다) visited1,visited2는 dfs,bfs의 방문기록 작성 깊이우선탐색, 너비우선탐색에서 조건문의 기준은 “..
Koala - 11기
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 1. 문제풀이 네트워크 연결 상태를 확인 후, 1번 컴퓨터가 바이러스에 걸렸을 때 전파될 수 있는 컴퓨터의 수를 구하는 탐색 문제이다. 깊이 우선 탐색 문제 중 하나로, 네트워크 연결 상태를 입력받은 후 인접 리스트의 형태로 그래프 정보를 저장한 후, 1번 컴퓨터를 매개변수로 하여 깊이 우선 탐색을 진행하였다. 다른 컴퓨터를 방문할 때마다 바이러스에 걸린 컴퓨터의 수를 1씩 증가시킨다. 2. C++ 코..
4949번: 균형잡힌 세상 (acmicpc.net) 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net 문제 풀이 단지 (,)와 [,]가 짝을 이루어 있는지만 확인하는 문제이다. 이는 스택을 이용하여 쉽게 풀 수 있다. 온점을 이용하여 입력을 알린다. EOF문제인걸로알고있는데 정확히 코드의 형식을 지켜야한다~ 이런형식이 있다~는 아직 모르겠어서 while문에 if종료조건 달아줬다. (,[는 리스트에 append해주고 ),]가 온다면 바로 전에 (,[가 있는지 확인한다. 있다면 잘하고있는것이므..
https://www.acmicpc.net/problem/18406 18406번: 럭키 스트레이트 첫째 줄에 점수 N이 정수로 주어진다. (10 ≤ N ≤ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다. www.acmicpc.net 문제해석 점수 N이 주어졌을 때 자릿수를 절반으로 나누어 왼쪽 부분과 오른쪽 부분의 각 자릿수의 합이 동일하면 LUCKY 아니라면 READY를 출력한다. 코드 N = str(input()) check = list() check.append(list(N[:len(N)//2])) check.append(list(N[len(N)//2:])) ch = list() ch.append(list(map(int, check[0]))) ch.append(list(..
풀이 각 풍선의 값을 덱에 값, 풍선 번호 쌍으로 저장한다. 이떄 풍선번호는 1~N까지 순서로 진행된다. 현재 풍선의 값을 cur에 저장하고, 해당 풍선의 번호를 출력한다. 현재 풍선은 이미 터진 것으로 처리하고, 덱에서 제거한다. cur이 양수인 경우: cur-1만큼 덱의 앞부분을 뒤로 옮긴다. cur-1번만큼 이동 cur이 음수인 경우: -cur번만큼 덱의 뒷부분을 앞으로 옮긴다. cur번만큼 음수값으로 이동 풍선을 모두 터뜨린 후에는 풍선의 번호를 출력한다. 번호는 터뜨린 순서대로 출력된다. 코드 #include #include using namespace std; deque dq; int N; int main(void) { cin >> N; int num; for (int i = 0; i < N;..
https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 알고리즘 분류 백트래킹 문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 하나씩 문제의 조건을 만족하는 ..
문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 초기 설정 0으로 이루어진 NXN 크기의 graph를 생성한다. 사과가 있는 위치는 1로 변경한다. 방향 변환 정보를 deque으로 저장한다. (li) x, y 위치 정보를 위해 리스트를 생성하고, 방향을 위한 d를 초기화한다. 뱀의 머리부터 꼬리까지 차지하고 있는 위치를 저장하기 위한 deque를 생성하고 시작 위치를 넣어준다. (dq) 반복 방향 변환 정보가 존재하고 time에 해당한다면 ..
문제 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 설명 일련의 수열을 만들기 위한 스택 연산을 +, -로 출력한다. +는 push, -는 pop을 뜻한다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int idx = 0; ..
https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 1. 문제풀이 대기줄에서 한 명씩만 설 수 있는 공간을 거쳐서 간식을 받을 수 있는 방법으로 구현하였다. 모든 사람들이 처음에 대기열에서 다른 대기 공간으로 간다. 다른 공간을 스택으로 구현하여, 순번에 맞는 사람이 대기열에 존재할 때까지 다른 공간에 일렬로 서게 된다. 해당 스택의 마지막으로 들어온 사람의 값이 간식을 받을 차례가 아닌 경우 문제 조건에 어긋나므로 Sad를 출력하고 종료하고, ..
문제 https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 코드 import sys from collections import deque input = sys.stdin.readline n = int(input()) q = deque(enumerate(map(int, input().split()))) ans = [] cnt=0 while q: if cnt>=0: idx,paper=q.popleft() else: idx,paper=q..
https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 문제 분석 분류 정렬, 이분 탐색, 두 포인터 문제 설명 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8..
문제 풀이 t = int(input()) for _ in range(t): n = input() reverse = n[::-1] sum = str(int(n)+int(reverse)) if sum == sum[::-1]: print('YES') else: print('NO') 설명 테스트 케이스의 개수를 받고 원래 수와 뒤집은 수를 합한 값이 좌우대칭이 되는지를 확인하는 코드를 만든다.
