오답노트

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/13414 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net - 문제파악 K명 수강가능한 강의에서 L명(L명 중에 같은 사람이 있을수도 있다)이 수강신청하려고 한다. 수강신청은 다음과 같은 규칙이 있다. 첫째 수강신청을 하면 대기열에 올라간다. 둘째 대기열에 올라간 사람이 다시 수강신청을 누르면 대기열에서 마지막으로 밀려난다. 세번째 대기열에 올라간 사람들중 순서가 가장 빠른 순으로 K명 수강신청이 완료된다. 수강신청 버튼을 누른 학생들의 학번..

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

해시란? 임의의 길이의 데이터를 특정 길이의 데이터로 대응시키는 자료구조를 뜻한다. 예를들어 어떤 학생의 학번과 이름을 컴퓨터에게 기억하게 하고 싶은데 만약 학번이 너무 길다면 학번의 일부분만을 이용해 Key를 만들어 학생의 이름을 저장한다. 그리고 STL에서는 해시 자료구조들을 지원하고 있다. 1. unodered_set unodered_set : unodered_set은 선언부에서 입력된 자료형을 Key로 가지는 해시 자료구조이다. 특징으로는 중복을 허용하지 않는다. #include #include using namespace std; void unordered_set_func() { unordered_set unset; unset.insert(10); unset.insert(100); unset.i..