컴공과고씨

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 처음에 고민을 하다가 팩토리얼 숫자를 그리면서 규칙을 좀 살펴보니 5배수가 곱해질때마다 뒤에 0 이 붙는 것을 보고 이것을 이용해 풀었다. 왜냐하면 10이 곱해지려면 2와 5가 필요한데 2는 항상 5보다 많기 때문에 5가 몇개 있는지 세주면 된다. 주의 해야할 것은 5의 배수중 25 와 같이 5가 2번 곱해진것은 0이 2개가 추가 됨에 주의 해주면된다. 위 방법과 다이나믹 프로그래밍을 이용하여 하나씩 0의 개수를 저장하는데 5배수가 들어있는 수가 곱해지는 차례에는 i-5번..

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 이 문제는 비트 연산 이용하는 문제로 나는 처음에 벡터를 이용해 풀어서 시간초과가 났다. 비트연산을 모르는 사람이 있다면 https://hagisilecoding.tistory.com/54 여기서 공부를 하고 오면 쉽게 이해할 수 있다. 단계별 문제 풀이 1. |= (1

1주차 (03.27~04.02) 문제 문제명 난이도 참조 소요 시간 후기 23876 일곱 난쟁이 하 x 8 min x 35490 블랙잭 하 x 9min x 48439 셀프 넘버 하 x 11min x 48164 한수 중하 x 16min x 20086 N-Queen 중 백트래킹을 이용하여 푸는 문제라는 힌트 참조 힌트 보기전(1h) 본 후(1h) 총 2h 처음 백트래킹 알고리즘을 떠올리지 못하고 포문으로만 접근하려 함. 백트래킹 유형 문제임을 인지하고 다시 풀었음 10435 리모컨 중 x 1.5h 푸는 아이디어는 빠르게 생각해 냈지만 구현부분에서 채널 탐색 범위를 잘못잡아서 시간을 많이 씀. 2주차 (04.03~04.10) 문제 문제명 난이도 참조 소요 시간 후기 11720 숫자의 합 하 x 5min x 1..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 이해 이 문제는 숫자가 나열되어있을 때 자신보다 작은 숫자의 개수로 그 숫자를 바꾸어 주는 것이다. 예를 들면 1 -9 -7 4 4 8 -10 -10 -10 2 3 3 1 이렇게 숫자가 있을 때 정렬을 해주면 -10 -10 -10 -9 -7 1 1 2 3 3 4 4 8 이므로 -7보다 작은 수는 3개이므로 -7 -> 3으로 변하는 것이다. 문..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 해시맵을 써서 쉽게 풀 수 있었다. 단계별 문제 풀이 1. 해시맵에 듣도 못한 사람 이름을 넣어줌 2. 보도 못한 사람의 이름을 해시맵 key에 넣어 검색하여 해시맵에 있는 이름이면 result 벡터에 넣어주고 듣보잡 사람 수를 세기 위해 카운트 해줌 3. 벡터를 정렬 후 카운트 해준 값을 출력해주고 벡터 출력 전체코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제를 보고 -가 있는 순간 뒤에 나오는 모든 숫자를 - 처리해주면 최소값이 된다. 위 아이디어를 생각해내면 풀리는 문제였다. 이유는 -가 있으면 뒤에 숫자는 괄호를 활용하여 +가 나오든 -가 나오든 모든 숫자를 -로 처리가 가능하기 때문이다. 단계별 문제 풀이 1. 더해야할 숫자, 빼야할 숫자 저장하는 배열 선언 2. 전에 -가 부호가 나왔는지 저장하는 bool 변수 선언 (초기값 : tr..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제의 핵심은 각 행에 있을 수 있는 퀸은 단 한개라는 것을 인지하고 풀어주어야한다. 0번째 행의 퀸의 위치를 결정하고 그 다음 위치를 결정할 때 한 열씩 그 위치에 퀸이 들어갈 수 있는지 조사한 후 다음행으로 넘어가서 다시 퀸이 들어갈 수 있는 열을 구해주는 식으로 풀어주면된다. 이런 구조를 구현하려면 백트래킹 기법을 사용해야 구현이 가능하다. 단계별 문제풀이 1. 각 행의 퀸의 위치 열을 저장하는 배열 c..

https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net n이 100보다 작으면 모두 등차수열인 수 인것을 인지. 숫자마다 각 자리수를 빼서 비교하여 등차 수열인지 아닌지 판별해주면됨. 문제풀이 1. 자리수 배열, 자리수 차이 배열 선언 2. 100보다 작은 경우 입력값 N을 출력 3. 100보다 클 경우 각 자리수를 배열에 저장 4. 각 자리수 배열에서 그 다음 인덱스 값을 빼서 자리수 차이 배열에 저장 5. 자리수 차이 배열의 값을 비교하여 한개라도 다..

https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 각 자리의 수와 그 숫자를 더해서 만든 수는 생성자가 있는 경우이므로 표시를 해주고 표시가 된 숫자들을 빼고 출력해주면된다. 문제 풀이 1. bool 형 배열 만들고 false로 초기화 2. 1부터 10,000까지 각 자리수를 더해주고 그 수를 더한 배열 index에 true를 넣어줌 3. bool 형 배열 중 false인 것을 출력 전체코드 1 ..

https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 카드를 3장을 뽑아서 주어진 숫자를 넘지 않고 최대한 가깝게 만들어주면 되는 문제이다. 문제 풀이 1. 카드 입력을 받아 배열에 저장 2. 3중 포문을 이용하여 3장의 카드의 합을 구함. 3. (주어진 숫자) - (3장의 합) 의 절대값을 이전 값과 비교 그리고 3장의 합이 주어진 숫자보다 작은지 확인 4. 위 조건일 경우 ans에 저장하고 다음 3장의 합으로 넘어..