본문 바로가기

프로그래밍

 (100)
[C++] 백준 10989번: 수 정렬하기 3 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 수의 개수가 1천만인데 반해 수의 범위 구간은 [1, 10000]이다. 메모리 제한이 8MB라서 1천만개의 숫자를 모두 저장하면 메모리 초과가 발생한다. 10000까지 표현 가능한 데이터 타입 중 가장 작은 바이트 단위를 가진 short(2바이트)를 이용해도 19MB이다. 그래서 찾아보니 Counting Sort를 이용해야 한다고 한다. https://bowbowbow.tistory.com/8 Counting So..
[C++] 백준 15663번: N과 M (9) https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 조합 만드는 유형의 시리즈 중 한 문제인 것 같다. 재귀함수를 이용하여 간단하게 풀 수 있었다. 입력되는 숫자 중 중복되는 것에 대해서는 map를 활용하여 해당 숫자의 갯수를 저장했다. vector에 출력할 숫자들을 하나씩 넣어가며 그 크기가 M이 됐을 때 출력하는 방식으로 코드를 작성했다. #include using namespace std; #define TC(T) int T; c..
[C++] 백준 13549번: 숨바꼭질 3 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 과거에 이 문제와 유사한 문제를 풀어본 적이 있다. 이 문제는 일반적인 Queue를 사용하는 BFS가 아닌 Priority Queue를 사용해야 한다. 시간이 짧을 수록 먼저 계산돼야 하기 때문이다. 이 문제에 대한 답안을 제출하면서 여러 번 AC를 못 받았는데, 처음에는 Priority Queue를 안 썼고 두 번째에는 +를 -로 적는 오타가 있었고 세, 네번째..
[C++] 백준 1967번: 트리의 지름 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 이전에 풀었던 같은 이름의 문제(https://www.acmicpc.net/problem/1167)와 많이 유사한 문제다. 이 문제를 풀려고 오랫동안 고민했지만 풀이가 떠오르지 않아서 다음 블로그를 참고했다. https://lmcoa15.tistory.com/56 백준 1967번 - 트리의 지름 https://www.acmicpc.net/problem/1967 트리의 개념을 이해한 뒤에 DFS를 이용하여 문제를 해결하면 된다. 정답률이 40프..
[C++] 백준 1865번: 웜홀 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 음의 가중치를 갖는 그래프에서 최단거리를 계산하는 문제다. 알고리즘 분류는 벨만-포드라고 되어 있지만, 플로이드-와샬을 이용해 문제를 풀었다. 아마 시간복잡도는 비슷하지만 코드는 훨씬 간결할 것이다. 플로이드-와샬 알고리즘에 대한 설명은 다음 블로그를 참고했다. 24. 플로이드 와샬(Floyd Warshall) 알고리즘 지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나의 정점... blog.naver..
[C++] 백준 2263번: 트리의 순회 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 지난 1학기 자료구조 중간고사에서 유사한 문제가 출제 됐었다. in-order와 post-order를 주고 이를 만족하는 트리 그리기였나 그랬다. 하지만 충분한 시간 동안 고민해 본 결과, 어떻게 풀어야 할 지 몰라서 다음 블로그를 참고했다. 백준 2263번 트리의 순회 문제 링크입니다: https://www.acmicpc.net/problem/2263 직접 트리를 그려본 다음에 유도를 해보는 것이 제일 적절한 해법인 것 같습니다. 후위 순회를 기준으로 생각해보면 맨 마지막에 위치한 노드가 ja..
[C++] 백준 1918번: 후위 표기식 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 지난 1학기에 자료구조 수업에서 스택을 배우면서 같이 배웠던 내용이다. 강의자료 PDF를 다시 열어 참고했다. 위에 설명된대로 코드를 작성하면 AC를 받는다. 나는 첫 번째 제출에서 오타가 생겨서 한 번 더 시도해서 AC를 받았다. #include using namespace std; #define TC(T) int T; cin >> T; while(T--) #define FAST_IO cin.tie(NULL); ios::sync_with_stdio(f..
[C++] 백준 16928번: 뱀과 사다리 게임 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 풀이과정 오답: 틀렸습니다. (22%) 1. 크기가 100인 int 배열 step을 정의한다. 여기에는 각 위치에 도달하기까지 최소 횟수가 저장된다. 2. 재귀함수를 이용하여 모든 경우를 탐색한다. 2-1. 위치 1부터 시작하여, 6칸 이내에 있는 사다리와 뱀을 타고 각각 이동하고 그 위치에서 6칸을 이동한다. 2-2. 만약 새로 이동할 위치에 해당하는 step 배열 값이 현재의 step에 1을 더한 값보다 작다면 이..

티스토리툴바