알고리즘 (8) 썸네일형 리스트형 [백준] 1427번 소트인사이드 C++ 문제풀이 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 String으로 수를 받은 후 하나씩 슬라이싱해서 벡터에 저장했다. sort함수를 이용해 정렬하고 결과를 출력하는 간단한 문제였다. 소스 코드 #include #include #include #include using namespace std; vector num; bool compare(int a, int b) { return a > b; } int main() { string N; cin >> N; for (int i = 0; i < N.size(); i++) { st.. [백준] 15686번 치킨 배달 C++ 문제풀이 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 풀이 완전탐색 문제였다. 맨 처음에는 재귀부분에 visited 배열을 만들어서 방문을 안 한 경우에 대해서 재귀를 수행했는데 시간초과가 나왔다. for (int i = 0; i < chicken.size(); i++) { if (visited[i] == false) { visited[i] = true; ch_chck.push_back(chicken[i]); dfs(cnt.. [백준] 1713번 후보 추천하기 C++ 문제풀이 https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 문제 풀이 추천인을 담은 배열과 추천수를 저장하는 배열을 만든 후, 추천인을 담은 배열의 크기가 N보다 커지면 추천수 배열을 검색해 추천수가 가장 적은 학생을 제거하는 방식으로 코드를 작성했다. 사실 이런식으로 푸는게 맞나 싶다 ㅋㅋ... 소스코드 #include #include #include using namespace std; vector rec; // 추천인을 담은 배열 int r.. [백준] 3425번 고스택 C++ 문제풀이 https://www.acmicpc.net/problem/3425 문제 풀이 몇가지 문제의 주의점을 설정하고 문제를 풀었다. 1) 모든 수행이 종료됐을 때 스택에 저장되어 있는 숫자가 1개가 아니라면, "ERROR"를 출력 -> cnt라는 변수를 통해 해결 2) DIV와 MOD계산에서 +와 - 부호를 잘 확인 -> 첫 번째, 두 번째 숫자의 부호를 확인 3) 연산 시 배열의 크기를 주의 4) 조건에 맞지 않으면 바로 중단 후 "ERROR"출력 구현 문제인 만큼 코드가 너무 길다. 처음에는 int를 이용해 풀었는데, IntegerOverflow 에러가 나와서 long long을 이용해 문제를 해결했다. 소스코드 #include #include #include using namespace std; typed.. [백준] 1920번 수 찾기 C++ 문제 풀이 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 문제 풀이 처음에는 algorithm의 sort()랑 find()를 이용해 답을 구하려 했는데 역시나 시간초과가 나왔다. sort() 와 BinarySearch를 이용해서 풀려고 했는데 또 시간초과가 나왔다. 결국 MergeSort와 BinarySearch를 직접 구현해 문제를 해결하였다. 소스코드 #include #include #include u.. [백준] 2164번 카드2 C++ 문제 풀이 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 풀이 자료구조 Queue를 이용해서 해결했다. 한 번의 반복에서 하나의 값은 바로 pop해주고, 다음 값은 push를 해준 후 pop을 했다. 소스코드 #include #include using namespace std; queue que; int main() { int N; cin >> N; for (int i = 1; i 1) { que.pop(); que.push(que.front()).. [백준] 11866번 요세푸스 문제 0 C++ 문제 풀이 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 풀이 자료구조 Queue를 이용해 K번째 숫자를 출력한다. 계속 틀리게 나와서 뭐가 문제인지 몰랐는데 쉼표 뒤의 띄어쓰기를 고려하지 않았다 문제 출력을 잘 확인해야겠다. 소스코드 #include #include using namespace std; queue que; int main() { int N, K; cin >> N >> K; for (int i = 1; i [백준] 1181번 단어 정렬 C++ 문제 풀이 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 풀이 정렬 문제이다 보니 시간복잡도가 nlgn인 합병정렬(MergeSort)를 이용해 문제를 해결하려고 했다. 단어의 길이에 따라 정렬하고 길이가 같은 단어들의 비교인 경우에는 string의 compare 함수를 이용해 정렬을 했다. 출력의 경우 조건문을 붙여 중복된 단어의 출력을 피했다. 소스코드 #include #include using namespace std; string .. 이전 1 다음
