링크 : https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 문제 풀이 다들 에라토스테네스의 체로 구현했는데 나는 하나씩 입력받아 이를 소수인지 판별하는 방식이 가장 먼저 떠올라 해당 방식으로 풀어보았다. 파이썬은 에라토스테네스의 체로 구현해보았다. C++ 코드 전문 HTML 삽입 미리보기할 수 없는 소스 Python 코드 전문 HTML 삽입 미리보기할 수 없는 소스 소감

링크 : https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 문제 풀이 어떤 방법을 사용해도 정수형으로는 풀 수 없는 문제이다. 그러므로 char 배열을 이용하거나 string을 이용해야 한다. 둘 다 맥락은 비슷하지만 string으로 풀어보았다. C++ 상세 풀이 더보기 for (i = 0; i < len; ++i) { tmp = carry; carry = false; if (i < A.size()) tmp += A[A.size() - i - 1] - '0'; if (i < B.size()) tmp += B[B.size() - i - 1] - '0'..

링크 : https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제 문제 풀이 수학 문제다. 푸는 방법은 DP와 그리디, 두 가지 방법이 있다. 우선 그리디로 푸는 방법은 간단하다. 최대한 적은 봉지를 들고 가고 싶다 했으니, 5kg짜리 봉지로만 담으면 된다. 처음에 주어진 N값이 5로 나누어 떨어진다면 (N % 5 == 0) 바로 5로 나눈 값을 출력하면 되고, 그렇지 않다면 3kg 봉지로 담고 출력할 값을 늘려줌과 동시에 N에서 3을 빼는 식으로 풀었다. ..

링크 : https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 문제 문제 풀이 수학 문제다. 다양한 방법을 통해서 풀 수 있겠지만 공식을 만들어서 풀라고 유도하는 문제다. N % H를 통하여 손님이 머무르게 될 층을 구할 수 있다. (6 % 10 = 4, 4층) N / H + 1을 통하여 손님이 머무르게 될 호를 구할 수 있다. +1을 하는 이유는 호수가 0부터 시작하는게 아닌 1부터 시작해서이다. N % H가 0이라면 꼭대기 층이며 호..

링크 : https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 문제 문제 풀이 예제 2번 때문에 반복문으로 풀 시 무조건 시간 초과가 나는 문제이다. 이미 정상에 도달했으면 미끄러지지 않는 조건 때문에, 잘 생각하면 V - A가 최종적인 목표임을 알 수 있다. 또한 V - A 거리를 가기 위한 일수는 (V - A) / (A - B) 이며, 정상에 딱 도달하면 미끄러지지 않으니 % 연산자를 이용해 0이 나오면 +1을 하고, 아니라면 +2를 해준다. (기본적으로 1일부터 시작하기 때문에 +1이 들어간다.) C+..

링크 : https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 문제 문제 풀이 문제가 조금 헷갈리게 적혀있다. 아래 사진처럼의 지그재그로 이해하면 될 듯 하다. C++ 코드 전문 HTML 삽입 미리보기할 수 없는 소스 Python 코드 전문 HTML 삽입 미리보기할 수 없는 소스 소감

비트 연산 비트란? 컴퓨터에서 자료를 표현하기 위해 사용하는 최소 단위로, 1bit = 0 or 1로 표현되고 8bit = 1byte이다. 비트 연산자 기본적인 비트 연산자는 &, |, ^, ~, 등등이 있지만 여기서는 매우 기본적인 개념보다는 헷갈렸던 개념이나 연산의 쓰임새 등을 언급할 생각이다. 참고로 비트 연산자는 우선순위가 매우 낮은 편에 속하므로 헷갈리면 소괄호를 잘 활용하자. a > n a * $2^{-n}$ (a / \(2^n\)) a n은 오른쪽으로 n번 shift를 의미한다. 예로 4 >> 2는 0100을 전체적으로 오른쪽으로 2번 이동하니 0001이 되고, 이는 10진수로 1을 의미한다. (4 / 4와 같다.) 깊게 들어간다면 Arithmetic Shift와 Logical Shift가 ..

링크 : https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 문제 문제 풀이 가장 중앙 방, 즉 1번 레이어는 1, 2번 레이어부터 2~7, 3번 레이어는 8~19, 4번 레이어는 20~36.. 즉 6, 12, 18, 24의 등비수열대로 늘어나는 패턴을 확인할 수 있다. 이를 활용해 등비수열의 합을 구하고 늘어난 레이어를 출력해주면 된다. C++ 상세 풀이 더보기 void solution(int N) { int cnt = 1; int layer = 1; w..

링크 : https://www.acmicpc.net/problem/1712 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 www.acmicpc.net 문제 문제 풀이 기본 수학 카테고리임에도 불구하고 처음에 별 생각 없이 반복문으로 풀었다가 예제 3번에 의해 시간 초과가 나는 문제이다. 수학으로 풀어야 시간 초과가 나지 않는다. 고정 비용 + 가변 비용 x 𝒳 A A / (C - B) < 𝒳 이 된다. 결국 𝒳를 구해야 하므로 A..

링크 : https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 문제 문제 풀이 C++ 상세 풀이 더보기 아이디어가 떠오르면 구현하기는 아주 쉬운 문제이다. 이것도 알파벳이니 이전 문제들과 똑같은 맥락으로 alphabet 배열을 선언해 모두 0으로 초기화한다. (bool형으로 선언해 false로 초기화하거나 해도 좋다.) 연속으로 계속 같은 문자가 나와야 하므로, 먼저 새로운 알파벳이 나오면 배열에서 1로 변경하고, 이..

링크 : https://www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 문제 문제 풀이 처음에는 아무 다른 알파벳도 들어가도 되나 싶어서 푸는 데 조금 오래 걸렸던 문제이다. C++ 상세 풀이 더보기 우선 find함수를 쓰기 위해 vector을 선언해 안에 크로아티아 알파벳들을 넣어준다. 그 후, 크로아티아 알파벳이 없을때 까지 반복한다. 크로아티아 알파벳을 찾는다면 느낌표로 변경해서 출력 조건인 알파벳 갯수를 좀 더 쉽..

링크 : https://www.acmicpc.net/problem/5622 5622번: 다이얼 첫째 줄에 알파벳 대문자로 이루어진 단어가 주어진다. 단어의 길이는 2보다 크거나 같고, 15보다 작거나 같다. www.acmicpc.net 문제 문제 풀이 C++ 상세 풀이 더보기 아스키 코드에서 활용했던 개념을 이용하는 문제다. 각 문자에 매칭되는 숫자는 정해져 있으므로 아무래도 배열로 미리 값들을 선언해 두고 활용하는 것이 편할 것이다. void solution(string str) { int num[] = {3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10}; int res = 0; int len = str.l..