알고리즘/프로그래머스
-
[C++] 요격 시스템알고리즘/프로그래머스 2023. 4. 17. 21:46
HTML 삽입 미리보기할 수 없는 소스 혼자 테스트케이스 잘못짜서 30분 잘못 쓴 문제 target의 길이 최대 500,000 최대 50만이므로 target 의 시작과 끝점을 1씩 더해주는 방식으로 하게되면 무조건 시간초과가 난다. 그렇기때문에 O(n) 혹은 O(nlogn) 으로 처리해야한다. 구간의 첫번째를 기준으로 오름차순 정렬하고 아닐 경우 두번째를 기준으로 오름차순 정렬 하게 sort 함수를 커스텀했다. (C++ 내장 라이브러리 sort 함수는 시간복잡도가 O(nlogn) 이므로 입력값에 의해 시간초과가 날 일은 없으니 걱정말자.) 이후 끝점의 최솟값을 갱신하며 끝점의 최솟값보다 클 경우 미사일이 더 필요한 것이므로 answer를 더해주고 최솟값을 갱신해주는 방식으로 해결했다.
-
[C++] 프로그래머스 연속된 부분 수열의 합알고리즘/프로그래머스 2023. 4. 13. 14:24
HTML 삽입 미리보기할 수 없는 소스 투포인터를 사용하면 쉽게 풀 수 있는 문제
-
[C++] 프로그래머스 무인도 여행알고리즘/프로그래머스 2023. 1. 27. 10:41
HTML 삽입 미리보기할 수 없는 소스 1. (0,0) 부터 시작하여 (0,1) (0,2) (0,3) ..... (1,0) (1,1) 과 같이 문자열 배열을 순회하며 'X' 가 아닐경우 bfs 탐색을 시작한다. 2. 탐색했던 섬을 다시 탐색하지 않기 위해서 bfs 탐색을 할때 bool check[101][101] 배열의 인덱스를 탐색시 true 로 바꿔준다. 3. 탐색이 끝나면 결과값을 answer 벡터에 저장 4. answer를 오름차순 정렬
-
[C++] 백준 26091 현대모비스 소프트웨어 아카데미알고리즘/프로그래머스 2023. 1. 15. 18:22
HTML 삽입 미리보기할 수 없는 소스 팀이 두명이고 능력치가 M 이상이면 한 팀으로 구성할 수 있을때 최대 개수로 팀을 만들려면 어떻게 해야할까?? 지금은 직관적으로 그리디 + 정렬 + 투포인터를 사용하면 된다고 생각이 들지만 두달전에는 못 했을 생각이다. 그렇다면 그리디 + 정렬 + 투포인터를 생각하는 과정은 어떻게 될까?? 1. 최대 개수로 팀을 만드는 것 == 능력치의 합이 최대한 M에 가깝게 만든다 (그리디) 2. 능력치의 합이 최대한 M 에 가깝게 만다는법 == 현재 팀을 구성하지 않은 사람들 중 가장 낮은 능력치 + 현재 팀을 구성하지 않은 사람들 중 가장 높은 능력치 (정렬) 3. 팀을 구성하려면 두명이 필요하다 == 투포인터 위와 같은 방식으로 흐름을 정리하며 푸는것을 습관화하자