반응형 [백준]214 [BaekJoon/백준] 1927번 C++ 최대 힙, 최소힙 이러한 용어가 쓰이는 힙정렬 알고리즘에 대한 문제였다. 힙 부모의 값이 자식의 값보다 항상 크다 / 또는 작다. => 최대힙/최소힙 힙에서 부모와 자식 관계는 일정하지만, 형제 사이의 대소관계는 일정하지 않다. C언어로 힙정렬을 구현했을 때의 코드를 살펴봤는데 진짜 기억이 하나도 안나고...이해도 안되고... 하 ... 쉬고싶다... 어느정도 감은 잡았는데, 문제를 구현하는데 있어서 끙끙대다가.. 풀이를 찾아봤다. 찾아보니 최소힙 / 최대힙 구현을 C++의 STL인 priority_queue 를 사용하여 구현할 수 있다고 한다. 참고 : twpower.github.io/93-how-to-use-priority_queue-in-cpp 이를 이용해서 구현해봤다. #include #inclu.. 2021. 3. 31. [BaekJoon/백준] 1764번 C++ 두 문자열 목록 중 겹치는걸 찾는 문제다. 찾기를 시도할 때 find 함수를 시간복잡도 O(N)으로 하게 되면 총 시간복잡도가 O(N^2)이 되어서 시간초과가 날 것이다. 이 문제는 이진탐색 = 이분탐색을 시도해야한다. 실수할 수 있는 점은, '문제에서 출력 결과를 사전순으로 요청한 것' 여기서 나도 틀렸다. #include #include #include using namespace std; vector str; vector result; int N, M; bool compare(string a, string b) { return a < b; } bool bin_search(int n, string key) { int pl = 0; int pr = n - 1; int pc; do { pc = (pl +.. 2021. 3. 30. [BaekJoon/백준] 1697번 C++ 처음에 동적할당으로 문제를 풀어보려 했으나, 어려웠다. 양방향에 대한 계산이 필요했기에 어려움을 많이 겪었고 알아보니 이러한 문제에서 DP 접근은 좋지 않다는 것을 알았다. ( 관련 참고 : www.acmicpc.net/board/view/41340 ) 풀이를 검색해보게 되었다. 이 문제는 BFS 알고리즘을 적용하여 풀 수 있는 문제였다. BFS는 처음이였다. 그래서 알고리즘도 알아보고, 흐름도 이해해보게 되었다. ( 관련 참고 : 1. gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html 2. m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230944971&proxyReferer=https:%2F%2Fwww.googl.. 2021. 3. 28. [BaekJoon/백준] 1620번 C++ C++ 을 연습하는 중인데 이 문제 덕분에 pair와 vector에 대해 조금 더 공부하고 이해하는 시간을 가질 수 있었다. 다만 덕분에 시간을 좀 많이 투자했다 ㅜㅜ 이 문제는 아무런 조치 없이 선형검색으로 하다가는 시간초과가 나게 된다. N , M의 범위가 100,000 이기 때문에 주어진 2초 안에서 얼핏보면 O(n)에서시간초과가 일어나지 않을 것 같지만 테스트케이스 단위가 아니라 한번에 받는 것이기 때문에 아마 주어진 시간은 모든 검색에 대한 사항인 것 같고, 게다가 문자열의 길이가 20이기 때문에 시간복잡도가 상당히 길어질 것이라는 것을 종합적으로 생각해줘야 한다. 이 문제는 검색에 있어서 문자열 검색 : O(log n) 숫자 검색 : O(1) 로 구현하면 된다. 문자열 검색을 위해서 vecto.. 2021. 3. 26. 이전 1 ··· 21 22 23 24 25 26 27 ··· 54 다음 반응형
