어흥

문제 링크: https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 1. 주의할 점 - KMP 알고리즘에 대해 알고 있어햐 한다 2. 구현 - 문자열 P와 S를 입력 받는다 - getPi()함수를 통해 접미사와 접두사의 일치 길이를 나타내는 배열을 반환한다 - KMP 알고리즘을 통하여 진행한다 - KMP 알고리즘에 대해 간략히 설명을 하면 다음과 같다 Origin의 문자열은 i를 통해 문자를 가리키고, Pattern의 문자열은 j를 통해 문자를 가리킨다 Origin[i] == ..

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18P2B6Iu8CFAZN SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - 이 문제는 Test가 불가능하므로 제출을 통해 검사해야 한다 - 다익스트라 알고리즘 혹은 플로이드-와샬 알고리즘을 통해 구현할 수 있다 - 테스트 케이스마다 초기화를 해야한다 2. 구현 [다익스트라 알고리즘] - 2차 배열에 간선의 정보를 저장해도 되지만, 시간이 많이 소요되므로 List형태로 간선의 정보를 저장한다 - 모든 정점에서부터 시작해 각 정점까지의 거리를 ..

문제 링크: https://www.acmicpc.net/problem/9938 9938번: 방 청소 문제 은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다. 서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다. 은기는 술병을 1번부터 N번까지 순서대로 정리할 것이고, 각각의 술병에 대 www.acmicpc.net 1. 주의할 점 - 한번 채워진 서랍은 항상 채워진 상태를 유지한다 - 서랍이 채워져 있는지 확인하는 배열이 필요하다 - A와..

문제 링크: https://www.acmicpc.net/problem/10775 10775번: 공항 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다. 이러한 사고가 일어나면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 www.acmicpc.net 1. 주의할 점 - 현재 숫자 N을 기준으로 1~N중에서 비행기를 넣을 수 있는 가장 큰 번호의 게이트를 Par[]배열에 담는..

문제 링크: https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 www.acmicpc.net 1. 주의할 점 - Node를 Cluster로 묶을 수 있어야 한다 - 중복 방문하는 Node에 대한 처리를 해야 한다 2..

문제 링크: https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 www.acmicpc.net 1. 주의할 점 - MST의 알고리즘으로는 프림이나 크루스칼이 존재하는데 둘중 하나로 풀면 된다 - 간선의 개수 적으..

문제 링크: https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계 www.acmicpc.net 1. 주의할 점 - Union-find와 함께 친구의 수를 저장하는 배열이 필요하다 - 이미 같은 집합에 속해 있는 경..

문제 링크: https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래 www.acmicpc.net 1. 주의할 점 - 그래프로 생각 -> DFS로 접근 -> 중복된 숫자 처리 2. 구현 - 그래프로 생각하여 Arr[]배열..