![]()
문제 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 문제 분석 전형적인 그래프 탐색 문제이지만, 열쇠가 없어서 지나쳤던 문을 이후에 열쇠를 획득했을 때 재방문해서 탐색하는 것을 구현하기가 약간 까다로울 수 있습니다. 하지만 그것만 구현하면 나머지는 평범한 그래프 탐색 문제이기 때문에 그렇게 어렵지 않습니다. 차근차근 문제에 접근해봅시다. 문제 풀이 빌딩을 탐색하다가, 열쇠가 없어서 열고 지나가지 못하는 문이 문제입니다. 열지 못했던 문을 기억해뒀다가 이후 그 ..
![]()
11880번: 개미 (acmicpc.net) 11880번: 개미 승현이는 방학을 맞아 심심하지만, 공부는 하기 싫습니다. 이렇게 방 안에서 하루하루 시간을 낭비하던 중, 승현이는 자신의 직육면체 모양의 지우개에 개미 한 마리가 붙어 있다는 것을 알게 www.acmicpc.net 소스코드 문제풀이 처음에는 그려진 그림에 따라서 A, B만 존재하는줄 알고 가로^2 + (세로+높이)^2만 하면 되는 줄 알아서 틀렸었다. 하지만 문제에서 서로 반대편에 위치 했다고 나와있었다. 즉, 직육면체를 펴보면 가장 큰 값이 다른 값과 더해지지 않고 그 자체로 제곱이 되어야 길이가 가장 짧기 때문에 max,min 함수를 이용하여 구현하였다. 그리고 주어진 수의 범위는 int로 표현할 수 있지만 제곱되면 표현하기 어렵기 때문..
https://www.acmicpc.net/problem/5533 5533번: 유니크 첫째 줄에 참가자의 수 N이 주어진다. (2 ≤ N ≤ 200) 둘째 줄부터 N개 줄에는 각 플레이어가 1번째, 2번째, 3번째 게임에서 쓴 수가 공백으로 구분되어 주어진다. www.acmicpc.net 문제분석 참가자 수만큼 이차원 배열에 입력받는다. 이때 이차원배열의 구성을 헷갈리지 않도록 주의해야한다. 소스코드 n = int(input()) score = [[], [], []] sum = [] for i in range(n): a, b, c = map(int, input().split()) score[0].append(a) score[1].append(b) score[2].append(c) for i in rang..
![]()
문제 풀이 일단 이건 네개의 면적을 구하기 전 일단 [0]으로 100*100칸을 만들어 줘야 한다.(이중 리스트로) 그런 다음 사용자가 4번 값을 입력하면 그 때마다 그 수를 1로 바꾸고 마지막에 전부 다 업데이트? 된 것들 중 다시 한번 그 100*100 을 돌려보면서 1의 개수를 구하면 된다. 풀이 코드 a=[[[0]for t in range(100)] for k in range(100)] for k in range(4): lx,ly,rx,ry=map(int,input().split()) for i in range(lx,rx): for j in range(ly,ry): a[i][j]=1 cnt=0 for m in range(100): for n in range(100): if a[m][n]==1: c..
