나그네

Atcoder Beginner Contest 322 (ABC 322) 문제 세트는 여기서 확인할 수 있다. 문제 A. First ABC 2 (AC / 1 min 44 sec) 더보기 문자열 s에서 "ABC"가 처음 등장하는 위치가 몇 번째 문자인지 출력하는 문제. 없는 경우 -1을 출력한다. #include using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); int n; string s; cin >> n >> s; if (s.find("ABC") != -1) cout > n >> m >> s >> t; if (t.substr(0, n) == s) { if (t.substr(m - n, n) == s) cout > m; vector v(m)..

1. PS란? C++을 알아보기 전에 먼저 PS가 무엇인지부터 알아봅시다. PS란 Problem Solving의 약자로, 제한된 시간과 메모리 내에 주어진 문제를 해결하는 코드를 작성하는 행위를 일컫는 말입니다. 프로그래밍 대회나 기업의 코딩테스트는 모두 PS에 속한다고 볼 수 있습니다. 자세히 파고들면, 프로그래밍 대회의 경우 더 많은 문제를 더 빠르게 해결할수록 높은 순위를 차지하게 됩니다. 이를 Competitive Programming이라고 하며 줄여서 CP라고 합니다. 2. 어떤 언어를 쓰나요? 보통 언어로 C/C++을 주로 사용합니다. 타 언어에 비해 실행시간이 짧다는 장점이 있고, STL을 위해 C++을 많이 사용합니다. C++은 객체지향언어의 대표적인 언어지만, 사실 객체 지향의 특성을 살..

20206번: 푸앙이가 길을 건너간 이유 문제 https://www.acmicpc.net/problem/20206 20206번: 푸앙이가 길을 건너간 이유 첫째 줄에는 정수 A, B, C (-10,000 ≤ A, B ≤ 10,000, -100,000 ≤ C ≤ 100,000)가 주어진다. 해당 숫자들은 좌표 평면 상에서 Ax+By+C=0 형태로 표현되는 푸앙이가 지나가는 직선 상의 경로을 나타낸다. (단 www.acmicpc.net 풀이 Ax+By+C=0 형태의 표현되는 직선 상의 경로가 직사각형을 통과하는지 여부를 묻는 문제입니다. Ax+By≤-C 또는 Ax+By≥-C로 식을 바꾸어 생각해야합니다. 문제에서 테두리 위로만 지나가는 경우는 위험지역을 통과하지 않는 것으로 간주한다고 했으므로 등호를 포함해..

이 카테고리는 곧 군대에 가는 제가 지금까지 공부했던 내용을 잊어버리지 않도록 기록하는 용도입니다. 이왕 쓰는 김에 보기 좋게 정리해서 다른 분들께도 참고자료가 되었으면 좋겠습니다. 이미 C++을 어느 정도 하실 줄 아는 분께는 도움이 되지 않을 수도 있습니다. "PS를 위한"이 붙은 이유는 제가 PS를 하는 게 아니라면 필요없을 만한 내용들이 포함되어 있기 때문입니다. 따라서 필수가 아닌 내용(예외처리, 동적할당 등)은 다루지 않을 예정입니다. 기본 C++에 대한 내용은 추후에 따로 작성해보도록 하겠습니다. 제가 배우고 주워들은 내용을 토대로 쓰는 글이라 많이 미흡할 수 있습니다. 그리고 기초라고 생각하는 부분은 일부 넘어갈 수도 있습니다. 최대한 자세하게 써보려고 노력하겠습니다! 질문은 댓글을 달아주..

14715번: 전생했더니 슬라임 연구자였던 건에 대하여 (Easy) 문제 https://www.acmicpc.net/problem/14715 14715번: 전생했더니 슬라임 연구자였던 건에 대하여 (Easy) 첫 번째 줄에 처음 주어진 슬라임의 에너지 K (2 ≤ K ≤ 1, 000, 000) 가 주어진다. www.acmicpc.net 풀이 간단한 정수론 문제입니다. K = A × B 형태로만 분할할 수 있으므로 최종적인 형태는 소인수분해된 형태임을 예측할 수 있습니다. 즉, K가 100일 때, 100 = 2^2 × 5^2 이므로 4개의 소인수로 분해됩니다. 이 문제는 흠집이 제일 많이 생긴 슬라임의 흠집 개수의 최소를 구하는 문제입니다. 흠집을 최소화하기 위해선 가능한한 완전 이진 트리 형태로 분할하는..

15925번: 욱제는 정치쟁이야!! 문제 https://www.acmicpc.net/problem/15925 15925번: 욱제는 정치쟁이야!! 첫째 줄에 각 줄의 컴퓨터 개수 N과 이후의 컴퓨터실 사용 여부가 하나의 공백을 사이에 두고 주어진다. 사용 여부는 사용시 1, 미사용시 0으로 주어진다. (1 ≤ N ≤ 31, N % 2 == 1) 이후 둘째 줄부터 www.acmicpc.net 풀이 브루트포스 문제로 O(N^2)으로 해결가능합니다. 사용 여부를 x라고 할 때, 한 행 또는 열에서 x가 N/2개 이상이면 모두 x로 바꿉니다. 문제의 예제 입력 1을 예로 들어 설명해보겠습니다. 5 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0 0 0 1 1 1 0 1 0 1 1 1 일 때, 행부터 먼저 모..

24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4 문제 https://www.acmicpc.net/problem/24265 24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 MenOfPassion 함수는 어떤 n에 대해서 i=1~n-1까지 총 n-1번 반복되는 for문을 수행합니다. 이 for문 내부에선 j=i+1~n까지 총 n-i번 반복되는 for문을 수행합니다. 이중 for문 내부의 코드는 i=1일 때 j=2~n, i=2일 때 j=3~n, ... , i=n..

24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3 문제 https://www.acmicpc.net/problem/24264 24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 MenOfPassion 함수는 어떤 n에 대해서 n회 반복되는 for문을 수행합니다. 이 for문 안에서 다시 n회 반복되는 for문을 수행합니다. 따라서 이중 for문 안의 코드1은 n^2번 수행됩니다. 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수는 2입니다. 코드 #inclu..

24263번: 알고리즘 수업 - 알고리즘의 수행 시간 2 문제 https://www.acmicpc.net/problem/24263 24263번: 알고리즘 수업 - 알고리즘의 수행 시간 2 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 MenOfPassion 함수는 어떤 n에 대해서 n회 반복되는 for문을 수행합니다. for문 안의 코드1은 n번 수행됩니다. 따라서 코드1의 수행 횟수는 입력받은 n과 같은 값을, 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수는 1입니다. 코드 #include using name..

24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1 문제 https://www.acmicpc.net/problem/24262 24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 MenOfPassion 함수는 어떤 n에 대해서 항상 1번만 return 합니다. 따라서 수행 횟수는 1, 최고차항의 차수는 0입니다. 코드 #include using namespace std; int main() { int a; cin >> a; cout