분류 전체보기 (108) 썸네일형 리스트형 백준 10816번 - 숫자 카드2 문제 C++ [이진 탐색], upper_bound()/lower_bound() 📍 백준 000번 - 제목 문제 프로그래밍 언어 🧩문제 요약제시된 크기 n만큼 수가 입력된다. 이후, 타겟값이 m개 주어질때 해당 타겟값이 배열에 몇개가 들어있는지를 순서대로 출력하라. 🧾내가 작성한 초기 코드 #include #include using namespace std; int input_card[500001], find_card[500001];int countCard(const int num, int size){ cout input_card[mid]){ cout " > n ; for(i=0; i> input_card[i]; } cin >> m ; for(i=0; i> find_card[i]; } sort(input_car.. 이분탐색/이진탐색 (Binary Search) 📍이분탐색/이진탐색 (Binary Search) 이분 탐색 / 이진 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다. cf) 오름차순이든 내림 차순이든 상관 없음 변수 3개를 사용하여 탐색하는데 보통(start, end, mid)/(low, high, mid)를 사용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진탐색의 과정이다. 이진 탐색의 시간 복잡도는 O(logN)이다. 단계마다 탐색 범위를 반으로 나누는 것과 같기 때문에 위의 시간 복잡도를 가지게 된다. 💡이진탐색 알고리즘 동작 원리위에서도 언급했지만 이진 탐색은 정렬된.. 백준 1018번[brute force] - 체스판 다시 칠하기문제 C++ 초기값 설정 📍 백준 1018번 - 체스판 다시 칠하기문제 C++ 🧩 문제 요약입력이 주어질 때 8*8체스보드를 만들기 위해서 최소 몇개의 보드를 칠해야하는지 구하라. 👍 이 문제에서 배운점 😕 문제점 1.먼저 이 문제를 풀때 brute force문제인데 어떻게 풀어야할지 몰라서 감이 안잡혔다. 처음에는 체크보드와 제일 유사도가 높은 부분을 배열에서 찾아내고 그 다음 몇개를 색칠해야 할지 계산하는 식으로 문제를 풀어보려고 했는데, 비약이 너무 많았다. 하지만 다른 방법은 생각도 안나고 결국은 다른 사람들의 풀이를 살펴보았다. ✅ 해결방법 : 정상적인 체크보드와 비교하기 string WB[] = { "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBW.. 백준 11650번 - 좌표 정렬하기문제 C++ 📍 백준 11650번 - 좌표 정렬하기문제 C++ 🧩 문제 요약좌표 x,y가 주어질때 x의 오름차순으로 정렬하라. 단, x가 같은 경우 y의 오름차순으로 정렬. 🧾내가 작성한 초기 코드 #include #include #include using namespace std; bool compare(const vector a, const vector b){ if(a[0] == b[0]) return a[1] > arr; cin >> n ; for(i=0; i> x >> y; arr.push_back({x,y}); } sort(arr.begin(), arr.end(), compare); for(i=0; i 이 문제를 직관적으로 풀자면 vector + .. 백준 10814번 - 나이순 정렬 문제 C++ sort()/stable_sort() 📍 백준 10814번 - 나이순 정렬 문제 C++ 🧩 문제 요약나이와 이름이 입력될 때 나이순으로 정렬하여 출력하라. 단, 나이가 같은 경우 입력 순으로 출력. 👍 이 문제에서 배운 점 이 문제에서 아주 중요한 부분은 나이가 같은 경우 입력순으로 처리하라는 것이다. 이말은 stable하게 정렬하라는 말과 동일하다. 처음에는 sort()를 사용해도 여러 테스트 케이스에서 stable하게 출력이 되길래 별로 문제가 없다고 생각했는데,백준 히든 케이스에서 자꾸 통과하지 못했다. 그래서 찾아보니 sort()는 stable하지 못하다. ✅ stable이란? 👉 stable: 동일한 값들의 순서를 보장.일반적인 정렬 알고리즘은 동일한 값들의 순서를 보장하지 않는다. 그래서 정렬 후의 순서가 원래 순.. 백준 1436번-팩토리얼 0의 개수 문제 C++ 📍백준 1436번-팩토리얼 0의 개수 문제 C++ 🧩 문제 요약 정수 N이 입력될 떄 N!의 뒤에 있는 0의 개수를 구하는 것 . 👍 이 문제에서 배운점 이 문제를 처음에 보면 factorial을 돌려서 %10해서 갯수를 카운팅 하면 되지 않을까? 라고 모두가 생각한다. 하지만, 이렇게 풀면 당연히 시간초과에 걸리게 된다. 그럼 어떻게 문제에 접근해야 할까? 0이 언제 생기게 되는지를 생각하면된다. ✅ 0은 언제 생기는가? 팩토리얼 결과에 0이 생기는 이유는 10이 곱해지기 때문이다.👉 10=2*5니까, 팩토리얼에서 2와 5가 몇개 있는지를 따져야한다. 그런데, 여기서 주의할점은!!2가 5보다 훨씬 많이 등장한다는 것이다. 2는 짝수이기만 하면 등장한다. 그렇기 때문에 우리는 5의 개수에 집중.. 백준 1436번 - 영화감독 숌 문제 C++ 📍 백준 1436번 - 영화감독 숌 문제 C++ 🧩 문제 요약 정수 n이 주어질 때 n번째에 해당하는 종말의 수를 출력하라. 종말의 수는 666이 연속으로 들어가는 수를 의미하며, 작은 수 부터 차례대로 순서를 매긴다. ex)1번째: 666 2번째: 1666 3번째: 2666 4번째: 3666 5번째: 4666 ...10번째: 9666 11번째: 10666 ... 🧾 내가 짠 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int N, count = 0, i; cin >> N; string ter_num = "666", tmp = .. 백준 1181번 - 단어 정렬 문제 C++ 📍 백준 1181번 - 단어 정렬 문제 C++🧩 문제 요약 N개의 문자가 입력된다. 길이가 짧은 순 부터 사전순으로 나열한다. 이 문제는 간단하지만 처음에 string을 어떻게 정렬할 수 있을지 몰라서 실마리를 찾기가 어려웠다.그래서 결국 서칭을 통해 답을 얻었다. 👍 이 코드에서 배울 점 #include #include #include using namespace std; bool CompStr(string a, string b){ if(a.length() != b.length()){ return a.length()> N ; string str[20000]; for(i = 0; i> str[i]; } sort(str, str+N, CompStr).. 이전 1 2 3 4 5 ··· 14 다음
