![]()
https://www.acmicpc.net/problem/20304 20304번: 비밀번호 제작 서강대학교 전산실에서 보안직원으로 일하는 향빈이는 한 통의 이메일을 받게 되었다. 이메일에는 서버 관리자 계정에 대한 비정상적인 로그인 시도가 감지되었다는 내용이 적혀 있었고, 첨부 www.acmicpc.net 코드 import java.io.*; import java.util.*; public class Main { static int n,m,answer; static int[] keys; static Queue q = new ArrayDeque(); static int[] arr = new int[1000005]; static void init() throws IOException { n = rstn();..
![]()
https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 문제분석 분류 BFS 문제설명 아군은 B, 적군은 W 가로-세로-위-아래 N명이 뭉쳐있으면 Power += N^2 섬 크기 구하기 문제 유형과 비슷한 문제 코드 #include #include #include using namespace std; int axisY, axisX; vector map; struct node { int y; int x; }; queue q; i..
![]()
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 분석 배추를 보호하기 위해 인접해있는 배추 무리마다 배추흰지렁이를 배치하기 위해서 배추흰지렁이가 얼마나 필요한지를 구하는 문제이다. 배추는 상하좌우 네 방향으로 붙어있는 경우에 인접한 것이다. 인접한 배추 무리가 몇 개인지 구하면 된다. 너비우선탐색(BFS)를 통해 문제를 풀 수 있다. 코드 #include #include #include using namespace std; #define MAX 50 ..
![]()
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 문제 분석 전형적인 그래프 탐색 문제이지만, 열쇠가 없어서 지나쳤던 문을 이후에 열쇠를 획득했을 때 재방문해서 탐색하는 것을 구현하기가 약간 까다로울 수 있습니다. 하지만 그것만 구현하면 나머지는 평범한 그래프 탐색 문제이기 때문에 그렇게 어렵지 않습니다. 차근차근 문제에 접근해봅시다. 문제 풀이 빌딩을 탐색하다가, 열쇠가 없어서 열고 지나가지 못하는 문이 문제입니다. 열지 못했던 문을 기억해뒀다가 이후 그 ..
![]()
https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제분석 분류 자료구조, 우선순위 큐 문제설명 배열에 정수 x(x ≠ 0)를 넣는다. 입력에서 0이 주어지는 횟수만큼 답을 출력한다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우..
![]()
백준 17298 오큰수 Intro Solution 결과를 출력할 리스트를 미리 만들고, -1로 가득 채워 초기화한다. 주어진 수열의 수를 인덱스와 함께 스택에 저장한다. 수열을 순회하며 스택의 꼭대기에 있는 수와 비교한다. 꼭대기의 수가 더 클 경우, 결과 리스트에 그 값을 저장한다. Code def solve(): n = int(input()) A = list(map(int, input().split())) stack = [] nge = [-1]*n for i, a in enumerate(A): while stack: if stack[-1][1] < a: j, _ = stack.pop() nge[j] = a else: break stack.append((i, a)) print(*nge) solve()
![]()
https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제분석 N명의 사람이 원을 이루면서 앉아있을 때, K번째 사람을 모든 사람이 제거될 때까지 계속 반복하는 문제이다. 코드 from collections import deque n, k = map(int, input().split()) queue = deque(range(1, n + 1)) answer = [] while queue: for _ in range(k-1): queue.append(queue.popleft()) answer.append(queue.popleft()) print..
![]()
https://www.acmicpc.net/problem/2164 [문제 해석] 본 문제는 큐를 사용해 푸는 문제로, N장의 카드를 입력해 1~N의 수를 큐에 입력하여, Q를 주어진 조건에 맞게 pop, push를 활용해 푸는 문제이다. [소스코드] from collections import deque N = int(input()) deque = deque([i for i in range(1, N+1)]) while(len(deque) >1): deque.popleft() move_num = deque.popleft() deque.append(move_num) print(deque[0]) [문제 해결] deque를 사용하여, deque의 배열 길이가 1보다 클 때 반복하도록 한다. 가장 왼쪽에 있는 원소..
![]()
2346번: 풍선 터뜨리기 (acmicpc.net) 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 문제 해석 N개의 풍선이 원형으로 놓여있고 안에는 숫자가 적혀있다. 풍선을 터뜨린 후 안의 숫자만큼 이동 후 다시 풍선을 터뜨리는 식으로 진행된다. 코드 문제 풀이 원형이기 때문에 앞뒤로 빼고 넣기 위해 자료구조로 덱을 사용하였다. 풍선 번호를 나타내는 덱과 풍선 안의 숫자를 나타내는 덱을 따로 que와 paper의 이름으로 선언해주었다. 처음 for문을 통해 덱에 알맞은 숫자들은 넣어 주고 ..
![]()
https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 문제분류 자료구조, 우선순위큐, 덱 문제분석 정해진 구간 L에 대하여 최솟값을 구하는 문제 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Deque; impor..
![]()
https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제분석 분류 큐 문제설명 N장의 카드를 입력한다. 1부터 N까지의 수를 큐에 입력한다. Q를 주어진 조건에 맞게 pop,push,pop 활용한다. 입력 6 출력 4 코드 #include #include using namespace std; int main() { queueque; int N; cin >> N; for(int x =1 ; x 1) //1개가 남을 때 까지 { que.pop(); q..
![]()
https://www.acmicpc.net/problem/1874 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 문제 분석 1부터 n까지의 수를 스택에 넣어놓고 입력받은 수열을 만들기 위해 push와 pop연산을 어떻게 수행해야 하는지 출력하는 문제다. push연산을 수행할 땐 +, pop연산을 수행할 땐 -를 출력한다. 입력받은 수열을 만들 수 없는 경우에는 NO를 출력한다. 코드 #include #include #inclu..
