컴공과고씨

https://www.acmicpc.net/problem/11720 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net 이 문제를 보고 두가지 방법을 떠올렸는데 공백을 주지 않기 때문에 int 받으면 각자리 수 반복문을 통해 구해서 출력하거나 string을 이용해서 각 자리를 stoi를 이용해서 int로 변환해서 더해주는 것이다. 나는 후자를 사용했다. 쉽게 string으로 입력을 받아서 각 하나하나 마다 문자를 - '0'을 통해서 char형을 int형으로 변환해주었다. 전체코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include #include using namesp..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 내가 처음 푼 방법은 우선순위 큐 한개와 스택을 이용해서 풀었다. 최대값은 top에서 그냥 빼주면 끝이지만 최소값을 빼는 방법은 스택을 이용해서 큐에 있는 모든 수를 빼면서 스택에 넣어준다. 그럼 스택 맨 위에 있는 것은 최소값이 된다. 그래서 스택에서 맨 위 값을 제거하고 다시 우선순위 큐에 넣는 방식으로 구현했다. 결과는 시간초과이다. 그래서 다른 방법 multiset을 이용하는 방법으로 ..

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net priority queue 우선순위 큐를 사용하면 쉽게 풀리는 문제이다. priority queue를 간단히 설명하자면 heap으로 구성된 queue로 항상 최대값 혹은 최소값이 root에 있다. priority_queue는 default로는 최소값이 root에 있기 때문에 이것을 그대로 사용해주면 된다. 전체코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제를 보고 priority queue를 떠올리면 쉽게 풀리는 문제였다. priority queue를 간단히 설명하자면 heap으로 구성된 queue로 항상 최대값 혹은 최소값이 root에 있다. priority_queue는 default로는 최대값이 root에 있기 때문에 이것을 최소로 바꾸어주기만 하면된다. 바꾸는 법은 벡터 sort와 마찬가지로 해주면되는데 주의할 점은 최..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 유형을 보고 분할정복을 떠올려 풀어준 문제이다. 각 변을 3씩 나누면서 보면 탐색하는 문제이다. 보면 처음에 9로 시작한다. 모든 원소가 같지 않다면 n/3으로 나누고 각 분면의 시작 좌표로 이동해주어야한다. ​이런식의 좌표가 나온다. y가 행 x는 열. 단계별 풀이 1. 입력을 받아주고 papper 재귀함수로 들어간다. 2. bool 변수 선언 후 각 분면에 있는 원소들을 탐색해..

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 ..