1. 단어정렬(1811)
https://www.acmicpc.net/problem/1181
1181번: 단어 정렬
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
www.acmicpc.net
강의를 참고하여 정렬 식을 사용해 풀어보았으나, 시간 초과의 문제로 다른 방법을 찾아보았습니다.
파이썬에 기본적으로 탑재되어있는 set, sort 함수를 이용해서 풀었습니다.
2. 수 정렬하기2(2751)
https://www.acmicpc.net/problem/2751
2751번: 수 정렬하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
여기서도 시간초과의 문제가 계속해서 발생하는 것을 확인했습니다.
그래서 정렬하는 코드를 직접 만드는 것이 아닌, sort함수를 가져와 사용했습니다.
중복되는 수가 없다고 했으니, 간단하게 나타낼 수 있었습니다.
3. 수 정렬하기 3(10989)
https://www.acmicpc.net/problem/10989
10989번: 수 정렬하기 3
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
www.acmicpc.net
이번 문제의 해결방안은 메모리 사용을 줄이는 것입니다.(+중복가능)
기존의 방법처럼 입력되는 모든 수를 리스트에 넣어서 돌리는 것은 당연히 메모리 초과로 이어집니다.
그래서 10001개의 빈 리스트를 생성하고, 0~10000사이의 숫자가 나올때, 리스트에다가 나온 횟수를 입력해줍니다.
그러면 num_list는 각각의 숫자가 나온 횟수를 의미하게 되고, 이를 출력하므로써 메모리 문제를 해결했습니다.
4. 알고리즘 수업 - 선택정렬 1(23881)
https://www.acmicpc.net/problem/23881
23881번: 알고리즘 수업 - 선택 정렬 1
첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 10,000), 교환 횟수 K(1 ≤ K ≤ N)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)
www.acmicpc.net
선택정렬의 기본 개념을 응용해서 풀이했다.
루프를 진행하면서 원소의 자리 교체가 이루어지는 경우 cnt + 1을 하여 cnt와 교환 횟수 K가 같아지는 시점에 answer의 값을 변경해 주었습니다.
마지막 주차가 끝날때까지 열심히 해준 1조 팀원들 고생했습니다..!!
'FOSCAR-(Autonomous Driving) > 알고리즘 스터디' 카테고리의 다른 글
| [2023 알고리즘 스터디] 2조 박주빈 5주차 - 백준 23882, 10989, 2751, 11650 (1) | 2023.02.27 |
|---|---|
| [2023 알고리즘 스터디] 4조 이은선 5주차 - 백준 2075 (0) | 2023.02.26 |
| [2023 알고리즘 스터디] 3조 박제형 5주차 - 정렬 (1) | 2023.02.25 |
| [2023 알고리즘 스터디] 3조 선병범 4주차 - DFS & BFS 알고리즘 (1) | 2023.02.20 |
| [2023 알고리즘 스터디] 2조 김준명 4주차 - 백준 1388 2606 1260 11725 (1) | 2023.02.19 |
