🔗 문제 링크 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 💡 문제 풀이 및 해석 주어진 단어중 정해진 갯수를 뽑는 조합문제이다. 조합으로 뽑은 다음에, 모음이 1개 이상, 자음이 2개 이상 들어갔는지 체크해주면 됩니다. ⭐️ 정답 코드 및 설명 #include #include #include #include using namespace std; int L, C; bool visit[15]; vector word; set answer; void input() { cin >> L >> C; word = vecto..
알고리즘 문제 풀이
🔗 문제 링크 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 💡 문제 풀이 및 해석 원형이 PPAP 인지 확인해야 하는 문제다. P -> PPAP 이므로 역으로 생각하면 PPAP -> P 가 된다고 생각할 수 있다. 그럼 문자열에서 앞에서부터 PPAP 인 부분을 P 로 바꿔가면서 O(N) 으로 탐색하면 된다. ⭐️ 정답 코드 및 설명 #include #include using namespace std; string sol(string str) { string temp = ""; int tempIndex = 0; for (int i = 0; i < str.siz..
🔗 문제 링크 https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 💡 문제 풀이 및 해석 주어진 조건이 뒤에 'A'를 붙이는 것과 'B'를 붙이고 뒤집는 것이다. 최악의 조건을 생각해보자. S.size() = 1, T.size() = 50 이다. 여기서 S -> T 로 갈 때, 브루트포스하게 할 수 없다. 2의 50제곱은 좀 많이 크다. S -> T 로 갈 때, 조건을 설정해주면 어떨까?? 이 문제는 사실 ..
🔗 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 문제 풀이 및 해석 최악의 경우 모든 금(10^9)+은(10^9) 을 10^5*2 만큼 움직여야 하므로 400조의 시간이 걸린다. 이는 일반적인 방법으로는 해결할 수 없고, "이분탐색"과 같은 방식으로 해결할 수 있을 것으로 보인다. 하지만, 어떤 조건이 성립해야 모두 시간안에 옮길 수 있을까? 라는 조건은 쉽게 생각나지 않는다. (저도 이 부분은 구글링을 했습니다.) 최대로 옮길 수 있는 금의 양 >= a && 최대로 옮길 수 있는 은의 양 >= b && 금+은 통합해서 최대로 옮길 수 있..
🔗 문제 링크 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 💡 문제 풀이 및 해석 문제부터 선수과목이라고 써져 있는 것을 보니, 위상정렬 문제임을 알 수 있다. (많이 풀어본 경험으로써??) 위상정렬이라고 마냥 어렵게 생각할 것 없다. 과목 A를 해결하면 과목 B를 배울 수 있다는 조건을 보자. A -> B 라고 생각하자. 그러면 화살표를 받는 B는 선수과목의 숫자가 +1이 되는 것이다. 그러면, 이는 선수과목의 숫자가 0이라면 수강할 수 있다는 뜻이 되기도 한다. 3번 해석을 input()에 적용시켰다. X가 선수과목해야 하는 숫자..
🔗 문제 링크 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 💡 문제 풀이 및 해석 첫 번째로 친구들의 집합을 만드는 것이 중요했다. 친구관계도를 만들기 위해서 myFriend를 이용해서 i번의 친구를 vector로 저장한다. 그럼 i번의 친구들의 친구들을 다시 모두 탐색한다. 단, 아직 친구 그룹이 형성되어 있다면 찾지 않는다. (이미 같은 그룹이기 때문) 1N 번의 아이를 23번 과정을 반복해서 모든 그룹을 만들어준다. ..
🔗 문제 링크 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 💡 문제 풀이 및 해석 경우의 수가 크지 않으므로 BruteForce로 풀 수 있을 것이라 생각했다. 일단, 0개를 설치한 경우는 반드시 조건에 성립하므로 예외처리해 준다. (안 해줘도 상관없다.) DFS 방식으로 사다리를 설치하면 브루트 포스하게 풀 수 있다. (이게 최선인지는 아직 모르겠다.) 설치할 다리의 개수를 모두 설치했을 때, 이 방식이 정답인지 확인하고 아니면 다음 경우의 수로 넘어간다. 정답이 나올 때까지 3번-4번을 반복한다. 모두..
🔗 문제 링크 1082번: 방 번호 첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다. www.acmicpc.net 💡 문제 풀이 및 해석 만약 0 만 살 수 있거나 N == 1인 경우 방번호는 0으로 고정이다. 가장 큰 수는 어떤 수일까? 2-1. 자릿수가 긴 수이다. 2-2. 자릿수가 같다면, 앞에서부터 비교할 때, 앞자리의 수가 큰 수이다. 먼저 0을 제외한 가장 코스트가 낮은 숫자를 찾아 맨 앞자리에 넣는다. 0과 비교해서 더 낮은 코스트인 수를 뒤에 최대한 많이 붙인다. 가장 앞자리부터 9 ~ 앞자리의수 까지 비교해서 교체할 수 있으면 교체한다. ⭐️ 정답 코드 및 설명 #include #include using namesp..
