본문 바로가기

알고리즘5

해싱(map,set) 해싱 해싱이란 탐색법의 일종으로 비교에 의해서 검색하는 방법이 아니라 함수식을 이용하여 바로 찾아 가는 검색 방법을 말한다. 자세한건 구글 검색 링크 이러한 해싱을 간편하게 할 수 있도록 C++에서는 map,set 자료구조를 지원한다. Set set 자료구조의 주요 용도는 key값의 존재 유무를 확인할때 사용한다. #include #include using namespace std; int main(void){ set s; s.insert(1); s.insert(9); s.insert(3); s.insert(4); s.insert(7); s.insert(8); s.insert(9); s.insert(1); set::iterator it; for(it = s.begin(); it != s.end() ; i.. 2020. 1. 21.
문자열 자르기 코딩테스트 문제를 풀때마다 여기서는 이거, 이런식으로 패턴화(?)된 부분들을 정리 좀 해놓으려고 한다. 시작은 문자열 자르기(더블릿, 백준, 프로그래머스에서 주로 문제를 푸는데 프로그래머스 문제들에서 자주 사용하는거 같다.) getline() ex) string s = {010-1234-6543, 010-5678-1234,010-0000-0000} 을 ,단위로 분리하기 #include #include #include #include using namespace std; int main() { string str = "{010-1234-6543,010-5678-1234,010-0000-0000}"; str = str.substr(1,str.length() - 2); //{, } 제거 stringstream.. 2019. 11. 22.
parametric search 개요 알고리즘 풀이법 중 하나로 상황에 맞는 최소/최대 값을 구할때 사용한다 개념 2^n 성립 2를 대입 -> 성립 ..... 9를 대입 -> 성립 10을 대입 -> 성립하지 못함 n의 최대값은 9 이런식의 풀이법을 의미한다. 위의 방법대로하면 비효율적으로 보이지만 이진탐색과 결합하여 사용하는 경우 단시간안에 문제를 풀 수 있음 2019. 11. 14.
줄자접기(더블릿 10F) 문제 준성이는 1 cm 간격으로 눈금이 매겨져 있는 줄자를 가지고 있다. 그 줄자에 있는 서로 다른 눈금 6개에 한 눈금에 하나씩 점이 찍혀 있는데, 빨간 점, 파란 점, 노란 점이 각각 두 개씩 있다. 준성이는 먼저 두 빨간 점이 만나도록 줄자를 접었다. 그런 후 두 파란 점이 만나도록 줄자를 접고, 또다시 두 노란 점이 만나도록 줄자를 접었다. 줄자는 투명하여 접더라도 점들을 잘 볼 수 있다. 어떤 색깔의 두 점이 만나도록 줄자를 접었을 때, 그 다음에 접으려는 색깔의 두 점이 이미 만나고 있으면, 그 두 점에 대해서는 줄자를 접지 않는다. 예를 들어 길이 10 cm인 줄자에 아래 그림과 같이 2 cm와 7 cm 위치에 두 빨간 점이 찍혀 있고, 5 cm와 4 cm 위치에 파란 점이, 10 cm와 3.. 2019. 11. 14.

티스토리툴바