Patrick's Devlog

1. 개요 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 1-1. 설명 비어있는 공집합 S가 주어졌을때, 원소 추가, 제거, 체크, 토글 등 여러 연산들을 수행하는 프로그램을 작성한다. 자세한 연산은 위의 링크를 참고한다. 1-2. 제한 사항 - 첫 줄에 수행해야 하는 연산 수 M이 주어지며, M은 1 이상 3,000,000 이하 - 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한줄에 하나씩 주어짐 2. 구현 2-1. 풀이 메모리가 매우 한정적이므, 비트마스킹을 이용해 풀었다..

1. 개요 https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 1-1. 설명 A와 B로 이루어진 영단어를 통해 간단한 게임을 만들었다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀때는 다음과 같은 두가지 연산만 가능하다. - 문자열 뒤에 A 추가 - 문자열 뒤에 B를 추가 후 문자열을 뒤집음 주어진 조건을 이용해 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성한다..

1. 개요 https://www.acmicpc.net/problem/4659 4659번: 비밀번호 발음하기 좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtp www.acmicpc.net 1-1. 설명 발음이 가능한 패스워드를 만드는 회사가 존재한다. 적당히 외우기 쉬우면서 안전하게 계정을 지킬 수 있는 비밀번호를 생성하기 위해 계획중이다. 높은 품질을 지닌 비밀번호 조건에 맞추어 비밀번호가 입력되었을 때, 높은 품질인지 확인하는 프로그램을 작성한다. 1-2. 제한 사항 - 여러개의 테스트 케이스로 이루어져 잇으며, 각 줄에 테스트할 패스워드가 주어짐 - 마지막 테..

1. 개요 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1-1. 설명 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고있다. 어느날 이 N명의 학생이 X번 마을에 모여 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있으며, i번째 길을 지나가는데 T_i의 시간을 소비한다. 각각 학생들은 파티에 참석하기 위해 걸어서 다시 마을로 돌아와야 한다. 이때, 최단 시간에 오고가기를 원할 때 ..

1. 개요 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1-1. 설명 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성한다. 방문할 수 있는 정점이 여러개 일 시, 정점 번호가 작은것을 먼저 방문하고 더이상 방문할 수 없는 경우 종료한다. 1-2. 제한 사항 - 첫 줄에 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점 번호 V가 주어짐 - N은 1 이상 1,000 이..

1. 개요 https://www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 1-1. 설명 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해놓은 배열이다. 문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 후 출력하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에 문자열 S가 주어지며, S는 소문자로 이루어져 있고 길이는 1,000 이하 2. 구현 2-1. 풀이 S를 받아 반복문을 통해 substr을 거쳐 접미사 배열을 생성해주었다. 후에 sort 함수를 통해 정렬 후 출력해주었다. 2-2. 코드 #include #..

1. 개요 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 1-1. 설명 오르막 수는 수의 자리가 오름차순으로 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성한다. 수는 0으로 시작할 수 있다. 1-2. 제한 사항 - 첫 줄에 N이 주어지며, N은 1 이상 1,000 이하 2. 구현 2-1. 풀이 DP의 Bottom-..

1. 개요 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1-1. 설명 방향 그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성한다. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 1-2. 제한 사항 - 첫 줄에 정점 개수 V, 간선 개수 E가 주어지며, V는 1 이상 20,000이하이고 E는 1 이상 300,000 이하 - 모든 정점은 1부터 V까지 번호가 ..