목록C,C++/코딩테스트 (102)
오답노트
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net - 문제 파악 컴퓨터는 1번부터 100번까지 넘버링된다. 1번 컴퓨터에는 바이러스가 존재하고 이 바이러스는 연결된 컴퓨터에 전파된다. 임의의 개수 만큼 서로 연결된 컴퓨터가 입력될 때, 바이러스에 감염된 컴퓨터의 개수를 출력하라. - 정답 BFS에서 가장 중요한건 내가 들렸던 곳을 체크하는 것이다. 전체적인 로직은 맞음에도 이것을 제대로 처리를 안했더니 초반부터 틀렸다... #include "bits/..
https://programmers.co.kr/learn/courses/30/lessons/43165?language=cpp 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr - 문제파악 정수 배열과 타겟 넘버가 주어진다. 정수의 배열을 적절히 더하거나 빼서 타겟넘버를 만들 수 있는 경우의 수를 구하여라 - 정답 BFS/DFS 로 구분되어 있긴한데 굳이 그렇게 안풀고 그냥 재귀함수로 풀었다. 시간복잡도도 엄청 여유로운편.. #include #include using namespace st..
https://programmers.co.kr/learn/courses/30/lessons/42839?language=cpp 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr - 문제 파악 7자리 정수를 문자열로 입력된다. 이때 문자를 적절히 조합하여 소수가 되는 경우의 수를 출력하라. - 정답 재귀에서 모든 경우의 수를 볼 때, 문자열 처리를 이상하게 해서 애먹었다. 생각을 제대로 하자 #include "bits/stdc++.h" using namespace std; int arr[8]; boo..
https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net - 문제파악 수열의 개수 N과 자연수 M 그리고 N개의 수열이 주어진다. 수열의 연속합이 M이 되는 경우의 수를 출력하라 - 정답 투 포인터를 활용한다. 시작 포인터로 부터 종료 포인터까지의 합이 M보다 크거나 같을 때까지 종료 포인터를 증가 시킨다. 만약 M과 연속합이 같으면 경우의 수를 증가시키고 아니면 연속합에서 시작포인터의 요소를 빼고, 시작 포인터..
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net - 문제 파악 주어진 자연수 N을 소수의 연속합으로 나타낼 수 있다. 이때 나타낼 수 있는 경우의 수를 출력하라. 경우의 수가 없다면 0을 출력하라. - 정답 투 포인터를 이용하여 N보다 큰 연속합일 때 종료 포인터를 멈추고 시작 포인터를 증가 시킨다. 이전 시작 포인터 값을 연속합에서 빼고 다시 종료 포인터를 N보타 큰 연속합일 때 멈추는 것을 반복한다. 위 작업을 반복하여 연속합이 N이 되는 경우의 수를 출력한다. #include "bits/stdc++.h" using namespace std; int arr[4..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net - 문제파악 N개의 수열이 주어지고 수열의 연속되는 원소의 부분합이 입력으로 주어지는 S이상인 경우 중, 부분합의 길이가 가장 짧은 길이를 출력하라 - 정답 투 포인터 연습문제.. 지만 골드 문제다.. 시작 포인터와 종료 포인터가 있고 시작 포인터는 for문으로 계속 증가 시키고 종료 포인터는 문제의 조건이 성립할 때 멈춘다. 해당 문제는 시작 포인터로 부터 연속되는 원소의 부분합이..
https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net - 문제파악 포켓몬의 이름이 N개 이다솜이 알고싶은 포켓몬의 이름 또는 포켓몬의 숫자가 M개 입력된다. 이 때 이다솜이 알고 싶은 포켓몬의 이름 또는 포켓몬의 숫자를 출력하라. 포켓몬의 숫자는 처음에 입력될 때 들어온 순서다. - 정답 unordered_map 변수를 두 개 선언했지만 숫자를 물어보면 이름을 답하는건 배열로 해도 충분하다. #include "bits//..
https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net - 문제 파악 N개의 회사의 출입 현황이 문자열로 이름과 enter 또는 이름과 leave로 입력된다. 이 때 회사에 남아있는 사람을 사전 역순으로 정렬하여 출력하라. - 정답 해시를 사용했다 해시는 정렬을 할 수 없으므로 vector로 넘겨서 정렬 후 출력했다. #include "bits/stdc++.h" #include using namespace std..
https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net - 문제파악 배열에는 중복 가능한 N개의 요소가 주어진다. 그 이후에 입력되는 숫자들이 배열에 몇개가 있는지 출력하라. - 나의 접근 배열에서 찾고싶은 정수가 있다면 처음 나타는 인덱스와 마지막에 나타나는 인덱스를 빼면 된다는 발상까지는 성공했으나 구현이 쉽지 않았다. 그런데 STL에 함수가 있었다... 이분탐색 힘들게 구현하지 말고 STL을 활용하자... - 정..
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net - 문제 파악 N 개의 배열을 주어지고 이 안에서 주어지는 M개의 정수가 있는지 판별하라. 주어지는 정수가 존재한다면 1, 아니면 0을 주어지는 정수에 따라 각각 출력하라. - 정답 이분탐색 입문 문제 시작 인덱스와 종료 인덱스 그리고 중간 인덱스를 각각 초기화 시킨 다음 중간 인덱스의 값과 확인하고 싶은 값의 크기에 따라 시작 인덱스 또는 종료 인..