공작소

문제 (A+B)%C는 ((A%C) + (B%C))%C 와 같을까? (A×B)%C는 ((A%C) × (B%C))%C 와 같을까? 세 수 A, B, C가 주어졌을 때, 위의 네 가지 값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000) 출력 첫째 줄에 (A+B)%C, 둘째 줄에 ((A%C) + (B%C))%C, 셋째 줄에 (A×B)%C, 넷째 줄에 ((A%C) × (B%C))%C를 출력한다. 풀이 과정 해당 조건식을 실제로 구현한 뒤 출력한다. C #include int main(void) { int a, b, c; scanf("%d %d %d", &a, &b, &c); printf("%d\n", (a + b) % c); printf(..

도입 이 글은 그래프 탐색에서 사용할 수 있는 깊이 우선 탐색 (DFS, Depth-First Search) 과 너비 우선 탐색 (BFS, Breadth-First Search) 에 대한 개념 설명을 담고 있습니다. 개인적으로 자료 구조 분야에서 스택 및 큐 개념을 배운 이후 중간 단계를 건너뛰고 바로 DFS와 BFS를 배우면서 PS에 입문한 사람으로써, DFS와 BFS는 실버 시절 제가 많은 실버 문제와 골드 문제를 풀 수 있도록 도와준 알고리즘입니다. 그래프 탐색이라고 해서 단순 그래프 측면이 아닌 다양한 방식으로 응용이 가능한 알고리즘이기에, 익힌다면 여러 분야에서 실전적으로 활용할 수 있을 것입니다. DFS와 BFS의 기본적인 개념을 응용 방식과 함께 배우고 풀이하는 것이 이 글의 목적입니다. 본..

문제 직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다. 편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다. 예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다. 심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로..

문제 ICPC Bangkok Regional에 참가하기 위해 수완나품 국제공항에 막 도착한 팀 레드시프트 일행은 눈을 믿을 수 없었다. 공항의 대형 스크린에 올해가 2562년이라고 적혀 있던 것이었다. 불교 국가인 태국은 불멸기원(佛滅紀元), 즉 석가모니가 열반한 해를 기준으로 연도를 세는 불기를 사용한다. 반면, 우리나라는 서기 연도를 사용하고 있다. 불기 연도가 주어질 때 이를 서기 연도로 바꿔 주는 프로그램을 작성하시오. 입력 서기 연도를 알아보고 싶은 불기 연도 y가 주어진다. (1000 ≤ y ≤ 3000) 출력 불기 연도를 서기 연도로 변환한 결과를 출력한다. 풀이 과정 불기 연도를 서기 연도로 바꾸려면 543년을 빼면 된다. 검색 or 예제 입출력에서 식을 얻을 수 있다. C #include..

도입 이 글은 자료구조에서 스택 다음으로 배우게 되는 큐에 대한 개념을 담고 있습니다. 스택과 유사하지만 다른 특징을 가지고 있으며, 큐 자료 구조에 대한 기반을 다져 놓으면 실전적으로 활용이 가능합니다. 큐는 다른 수많은 알고리즘 (BFS, 위상 정렬, 데이크스트라 등등) 을 배우는 데에 있어서 필수적인 기초가 되는 알고리즘이기 때문에, 큐의 개념을 이해하고 여러 문제에 활용하며 풀이한 뒤, 추후 적극적으로 응용이 가능하도록 능력을 기르는 것이 이 글의 목적입니다. 본 글은 C를 기반으로 작성되었습니다. 스택 자료 구조를 먼저 공부한 이후 큐를 공부하는 것을 추천드립니다. https://readytojoin.tistory.com/35 스택 (Stack) 스택 (Stack) 은 한 쪽 끝에서만 데이터를 ..

문제 흥선이는 팰린드롬을 싫어한다. 어느 날 지구를 정복한 흥선이는 팰린드롬 척화비를 세워, 전 지구의 팰린드롬을 없애버렸다. 그리고 수미상관 순수비를 만들어 수미상관을 널리 퍼뜨렸다. 팰린드롬과 수미상관의 정의는 다음과 같다. 팰린드롬 : (앞뒤가 똑같은 팰린드롬~) “u”, “xyx”, “krrk” 같이 뒤집어 읽어도 같은 문자열을 뜻한다. 수미상관 : (앞뒤가 똑같은 수미상관~) “z”, “pqpq”, “astoast” 같이 앞쪽 절반이 뒤쪽 절반과 같은 문자열을 뜻한다. 정확히는, 길이가 N인 문자열이면 길이가 floor(N/2)인 접두사와 접미사가 동일한 문자열을 뜻한다. 민수는 팰린드롬의 유구한 역사를 살리고 싶었지만, 여기저기 박힌 팰린드롬 척화비 때문에 그 꿈을 이룰 수 없었다. 그래도 하..

문제 준하는 사이트에 회원가입을 하다가 joonas라는 아이디가 이미 존재하는 것을 보고 놀랐다. 준하는 놀람을 ??!로 표현한다. 준하가 가입하려고 하는 사이트에 이미 존재하는 아이디가 주어졌을 때, 놀람을 표현하는 프로그램을 작성하시오. 입력 첫째 줄에 준하가 가입하려고 하는 사이트에 이미 존재하는 아이디가 주어진다. 아이디는 알파벳 소문자로만 이루어져 있으며, 길이는 50자를 넘지 않는다. 출력 첫째 줄에 준하의 놀람을 출력한다. 놀람은 아이디 뒤에 ??!를 붙여서 나타낸다. 풀이 과정 문장을 입력받고 ??!와 같이 출력한다. C #include int main(void) { char str[55]; scanf("%s", str); printf("%s??!", str); return 0; } C++..

문제 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 A와 B가 주어진다. (0 < A,B < 1010000) 출력 첫째 줄에 A+B를 출력한다. 풀이 과정 문자열을 이용해서 표현 범위를 벗어난 수를 연산할 수 있다. 일의 자리수부터 계산하면서 올림수를 따로 저장하는 일반적인 덧셈 방식을 직접 구현해주면 된다. #include #include #include char a[10005]; char b[10005]; char c[10005]; int plus = 0; int main(void) { scanf("%s %s", a, b); int a_idx = strlen(a) - 1; int b_idx = strlen(b) - 1; int c_size = 0; whi..

문제 두 자연수 A와 B가 주어진다. 이때, A+B, A-B, A*B, A/B(몫), A%B(나머지)를 출력하는 프로그램을 작성하시오. 입력 두 자연수 A와 B가 주어진다. (1 ≤ A, B ≤ 10,000) 출력 첫째 줄에 A+B, 둘째 줄에 A-B, 셋째 줄에 A*B, 넷째 줄에 A/B, 다섯째 줄에 A%B를 출력한다. 풀이 과정 기존에 A+B, A-B, AxB, A/B 문제를 풀었던 것처럼 풀이하면 된다. C #include int main(void) { int a, b; scanf("%d %d", &a, &b); printf("%d\n", a+b); printf("%d\n", a-b); printf("%d\n", a*b); printf("%d\n", a/b); printf("%d", a%b); r..

문제 심심한 승현이는 너무 심심한 나머지 올바른 괄호열을 가지고 놀고 있었습니다. (()(()))()() 그러다가 어쩌다 보니 괄호열을 부러뜨렸습니다. (() (( )))() () 크게 낙담한 승현이는 노력해 보았지만, 대부분이 부러져 버려 단 한 부분만 재사용할 수 있다는 것을 깨닫게 되었습니다. )))() 승현이는 이 괄호열을 가지고 놀려고 했으나 올바른 괄호열이 아니기 때문에 행복하지 않았습니다. 이를 보던 지학이는 승현이에게 “그러면 앞과 뒤에 적절하게 괄호를 붙이면 올바른 괄호열이 되지 않을까?”라고 했고, 승현이는 조금 생각한 뒤 그렇게 하기로 했습니다. 예를 들어, 위의 올바르지 않은 괄호열의 경우 앞에 여는 괄호 3개를 붙이면 올바른 괄호열이 됩니다. ((()))() 그러나 괄호열을 사서 ..