The Way
5월 18일 백준 본문
* 코드는 맨 아래에 있습니다
쉬운 문제는 거의 다 푼 것 같다. 이제 난이도 있는 문제들이 슬슬 나올.. 것 같다.
# 백준 1406번: 트리의 지름
# 백준 1967번: 트리의 지름
트리의 지름을 구하는 좋은 알고리즘이 있다.
여기에 잘 설명되어 있음
# 백준 11650번: 좌표 정렬하기
# 백준 11651번: 좌표 정렬하기 2
pair은 문제의 조건대로 비교 연산자가 잘 정의되어 있으므로 사용하면 된다
11651번의 경우 연산자 정의를 새로 하기보단 순서를 바꾸어주면 된다.
# 백준 10814번: 나이순 정렬
stable_sort 문제이다.
그런데 한쪽이 string이라 약간 번거로운 면도 있고, swap시 시간도 오래 걸릴 것 같아서
string은 따로 저장하고, string의 index를 저장한 뒤 pair<int, int>를 sort 해주었다.
index순이므로 그냥 sort를 사용해도 된다. 속도나 메모리 측면에서 우월하다.
# 백준 10825번: 국영수
정렬 기준이 복잡해진다. 이럴 때는 새로운 비교 함수를 하나 만드는 것이 편하다.
# 백준 11652번: 카드
적당한 알고리즘이 떠오르지 않는다. 역시 정렬한 뒤 O(n)에 세주는 것이 최고.
# 백준 11004번: K번째 수
partial sort를 사용하면 O(n)에 풀 수 있다.
scanf + std::sort를 사용해도 풀린다. 1488MS.
scanf + partial sort를 사용하면 1132MS.
cin + partial sort를 사용하면 788MS.
(물론 cin.tie(NULL); cout.sync_with_stdio(false); 를 해주어야 한다)
찾아보니 algorithm에 nth_element라는 함수를 제공한다. 사용하면 796MS.
내가 짠 코드가 그리 비효율적이진 않았나보다.
그리고 동일한 코드인데 다른 사람은 660MS까지 뜨는 것 같다. 무슨 차이인지 도통 모르겠다.
# 백준 1377번: 버블 소트
어떤 값이 출력되는지가 상당히 비직관적이다. 한 눈에 딱 들어오지 않는 사람은 꼭 차례차례 써보자.
써보면 알겠지만, 왼쪽으로 가장 많이 이동한 원소의 이동거리 + 1이 출력된다.
# 백준 11724번: 연결 요소의 개수
# 백준 1707번: 이분 그래프
dfs, bfs 중 편한거 아무거나. 난 dfs가 더 편해서 그거로 했다.
# 백준 10451번: 순열 사이클
탐색의 일종이지만 훨씬 쉽다.
edge 정보를 따로 저장할 필요도 없고, 경로가 딱 하나라 stack도 필요 없다.
1167.cpp'PS > 백준 온라인 저지' 카테고리의 다른 글
| 1월 3일/4일 백준 (2618, 1315) (0) | 2019.01.04 |
|---|---|
| 1월 2일 백준 (14502, 1735, 10026, 14888) (0) | 2019.01.02 |
| 5월 17일 백준 (0) | 2018.05.18 |
| 5월 16일 백준 (0) | 2018.05.16 |
| 5월 15일 백준 (0) | 2018.05.15 |
