![]()
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제분석 분류 그래프 이론, 다익스트라 문제설명 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 N(2 ≤ N ≤ 125)이 주어진다. → 동굴의 크기는 NxN N=0인 입력이 주어지면 전체 입력이 종료된다. [0][0]에서 [N-1][N-1]까지 가는 동안 지나는 칸의 크기만큼 소지금을 잃는다. 잃는 금액을 최소로 ..
![]()
1. 문제 2566번: 최댓값 첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다. 최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다. www.acmicpc.net 2. 구현 코드 max_num=0 col=0 row=0 for i in range(9): line = list(map(int,input().split())) if max(line)>max_num: max_num=max(line) col=i row=line.index(max_num) print(max_num) print(col+1,row+1) 3. 풀이 - 우선 2차원 리스트를 입력받는다. - 탐색을 통해 원하는 위치의 데이터를 찾는다. -max초기 값을 0으로 설정해놓고..
![]()
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제분석 한 컴퓨터가 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 문제이다. 코드 def bfs(x): q = deque(); q.append(x) while q: x = q.popleft() for i in arr[x]: if ..
![]()
문제 https://www.acmicpc.net/problem/2902 2902번: KMP는 왜 KMP일까? 입력은 한 줄로 이루어져 있고, 최대 100글자의 영어 알파벳 대문자, 소문자, 그리고 하이픈 ('-', 아스키코드 45)로만 이루어져 있다. 첫 번째 글자는 항상 대문자이다. 그리고, 하이픈 뒤에는 반드 www.acmicpc.net 풀이 해석 문제 자체의 난이도도 브론즈2 수준으로 그닥 어렵진 않지만 이 문제를 포스팅하는 이유는 C++로 문자열을 잘라내는 것이 Python만큼 간단하게 되지 않기 때문이다. Python으로 이 문제를 푼다면 list(str.split('-'))으로 문자열을 분리해서 리스트로 묶어내고 각 첫 글자만 모아 출력하면 간단히 끝난다. 하지만 C++에서는 이렇게 문자열을 ..
![]()
6996번: 애너그램 (acmicpc.net) 6996번: 애너그램 첫째 줄에 테스트 케이스의 개수(
![]()
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로 탐색한 결과를 출력하는 문제이다. 단, 방문할 수 있는 정점이 여러 개인 경우, 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우에 종료하도록 하는 문제이다. 이때, DFS란 깊이 우선 탐색, BFS는 넓이 우선 탐색을 의미한다. [소스코드] from collections ..
![]()
15657번: N과 M (8) (acmicpc.net) 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 소스코드 문제 풀이 중복해서 뽑을 수 있는데, 비 내림차순순으로 출력하면 되는 문제이다. 즉, 오름차순으로 출력하면 된다. 이전에 풀었던 n과 m문제와 같이 백트래킹을 이용한다. 기존에 n과 m 문제들을 수정해서 풀었다.
![]()
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/2566 2566번: 최댓값 첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다. 최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다. www.acmicpc.net 문제 풀이 방법 1. 각 행마다 리스트로 입력을 받고 2차원 리스트에 추가한다. 2. 1행 부터 각 수를 비교한다. 3. 최대값이 몇 행 몇 열에 있는지 저장한다. 코드
![]()
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 문제 분석 전형적인 그래프 탐색 문제이지만, 열쇠가 없어서 지나쳤던 문을 이후에 열쇠를 획득했을 때 재방문해서 탐색하는 것을 구현하기가 약간 까다로울 수 있습니다. 하지만 그것만 구현하면 나머지는 평범한 그래프 탐색 문제이기 때문에 그렇게 어렵지 않습니다. 차근차근 문제에 접근해봅시다. 문제 풀이 빌딩을 탐색하다가, 열쇠가 없어서 열고 지나가지 못하는 문이 문제입니다. 열지 못했던 문을 기억해뒀다가 이후 그 ..
