본문 바로가기

Algorithm

 (55)
[BackJoon4375] 1 안녕하세요. 이번 포스팅에서는 BackJoon 4375번 문제인 1에 대한 해설을 진행해 보겠습니다. 문제는 다음과 같이 이루어져 있습니다. 우선 n이 2와 5로 나누어 떨어지지 않는다고 명시되어있습니다. 즉 주어지는 n은 10으로도 나누어 떨어지지 않습니다. 그러면 저희는 1부터 1 , 11, 111, 1111,... 11111111 등등 1로 이루어진 수를 계속 테스트하며 n과 나누어 볼 수 있습니다. unsigned long long m = 1; ... m = m * 10 + 1; 위와 같이 10을 곱하고 1을 더해주는 과정을 계속 진행해주면 1로만 이루어진 수를 작은 수부터 차례로 구해나갈 수 있습니다. 하지만 문제가 뭐냐면, 위 방식으로만 코드를 작성하게 되면 시간 초과가 나오게 됩니다. 그 이..
[C++/Algorithm] 정렬 알고리즘 이해하고 구현하기 (Merge, Quick) #2 안녕하세요. 이번에는 저번 포스팅에 이어 https://chanho0912.tistory.com/21 [C++/Algorithm] 정렬 알고리즘 이해하고 구현하기 (bubble, insertion, selection) #1 안녕하세요. 이번 포스팅에서는 기본적인 정렬 알고리즘인 버블 정렬 선택 정렬 삽입 정렬 이 세 가지에 대해 이해하고 구현해보는 포스팅을 진행해볼 예정입니다. 우선 정렬 알고리즘이 무엇 chanho0912.tistory.com Merge Sort와 Quick Sort에 대해 알아보는 시간을 가져보겠습니다. 기본적으로 위 포스팅에서 진행한 선택, 삽입, 버블 정렬은 WorstCase(최악의 경우) O(n^2)의 성능을 가집니다. 즉 우리가 처리해야 할 데이터의 개수가 n 개라고 가정하면,..
[C++/Algorithm] 정렬 알고리즘 이해하고 구현하기 (bubble, insertion, selection) #1 안녕하세요. 이번 포스팅에서는 기본적인 정렬 알고리즘인 버블 정렬 선택 정렬 삽입 정렬 이 세 가지에 대해 이해하고 구현해보는 포스팅을 진행해볼 예정입니다. 우선 정렬 알고리즘이 무엇인가에 대해 한번 짚고 넘어갈게요. 정렬 알고리즘이란? 컴퓨터 과학과 수학에서 정렬 알고리즘(sorting algorithm)이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. (출처 : https://ko.wikipedia.org/wiki/%EC%A0%95%EB%A0%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98) 즉 저희가 사용하는 List나 Array 또는 다른 자료구조의 데이터를 저희가 원하는 순서대로 배열하는 알고리즘입니다. 정렬 알고리즘은 데이터의 정규화를 위..
[C++/Algorithm] 순열과 조합 구현하기 이번 포스팅에서는 C++로 순열과 조합을 구현해보려 한다. 1. 순열 순열은 '순서'의 개념이 존재하는 조합이다 가령 [1, 2, 3] 중 3개의 원소로 만들 수 있는 모든 순열의 집합은 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] 이렇게 6개의 순열이 나올 수 있고, 간단하게 3!로 그 수를 구할 수 있다. 컴퓨터로 순열을 구현하는 방법에는 몇 가지가 있는데, 가장 기본적으로 DFS 방식, 즉 재귀적으로 방문처리를 이용하여 순열을 구할 수 있다. // Permutation DFS로 구현 #include using namespace std; void Permutation(int visited[3], vector & vec, vecto..
[C++/Algorithm] upper_bound, lower_bound 이해하기 2021년 상반기 카카오 인턴 코딩 테스트에 응시했었는데, 당시 3번 문제에 upper_bound, lower_bound를 사용했었다. 그 당시에 조금 헤맸던 기억이 있어서 이번 기회에 한번 정리해보려 한다. 우선 c++ reference(https://www.cplusplus.com/reference/algorithm/upper_bound/)를 찾아보면 Return iterator to upper bound Returns an iterator pointing to the first element in the range [first,last) which compares greater than val. The elements are compared using operator
[C++/Algorithm] priority_queue 사용법 Queue라는 자료구조는 선입 선출, 즉 먼저 들어온 data가 먼저 나가는 구조로 되어있다. PriorityQueue라는 자료구조는 이 Queue라는 자료구조의 입 출력 순서를 지키면서, Queue에 내장되어 있는 data는 자동적으로 정렬이 되어있게끔 만들어 주는 자료구조이다. 즉 선입선출 + 자동정렬이라고 간단하게 생각하면 된다. 이 PriorityQueue를 C++ stl library로 사용하려면 #include #include 위의 라이브러리를 포함하거나, queue library를 포함해주면 사용할 수 있다. 기본적인 선언부는 다음과 같다. // priority_queue 다음과 같은 간단한 코드로 예시를 들어보겠다. #include using namespace std; int main(){..
[C++/Algorithm] <bits/stdc++.h> 사용하기 코딩 테스트를 c++로 준비하는 학생들은 stl에 대해 익숙할 것이다. 필자 역시 코딩 테스트를 c++로 준비하는 입장에서 자주 쓰는 stl 함수에 대해 기본적인 문법을 까먹을 때 즈음 자주 확인한다. 보통 string, vector, queue, algorithm, map, set... 등의 stl library를 주로 사용하는데 코딩 테스트를 처음 준비하시는 입장이라면 bits/stdc++.h라는 파일을 바로 사용하기보다는 익숙해질 때 까지 수동적으로 헤더 파일을 추가하는 방법을 추천한다. 왜냐하면 어떠한 자료구조를 사용할지 고민해보고, 해당 헤더 파일에 포함되어있는 메서드를 직접 추가해보며 확인하는 과정이 꽤 중요한 공부가 된다. (처음 준비하시는 분이라면 파이썬으로 얼른 도망가세요) ... 여튼 ..

티스토리툴바