본문 바로가기

분류 전체보기25

Hash c++ 개념 정리 Hash Hash는 기본적으로 임의의 길이의 문자열을 받아 고유한 key값을 생성한다. 그리고 그 key값에 value를 저장한다. 이렇게 저장을 할 때 같은 key값이 나올 수도 있다. 그래서 그러한 경우에는 Chaning 방법을 써서 해결하면 된다. Chaning이란 연결리스트를 통해 바로 뒤로 이어서 저장을 한다. 해싱함수 #define MAX_TABLE 10000 // 내가 필요한 만큼의 테이블 크기로 잡아주면 된다. int hashing(string input){ // 정수로 바꿔 주는 함수이다. int div = 401; // 이렇게 정수로 바꿀때 특정한 소수들을 이용하면 최대한 key값이 겹치지 않게 만들 수 있다. int i = 0; int len = input.length(); while.. 2023. 4. 14.
백준 1269번 (대칭 차집합) c++ 문제 문제 풀이 두 가지 방법으로 이 문제를 풀 수 있다. 1. Map을 사용하는 방법 2. Hash를 사용하는 방법 Map이란? map은 각 노드가 key와 value로 이루어진 트리이다. 중복을 허용하지 않는게 특징이다. 그리고 map은 검색, 삽입, 삭제 등이 O(logn)인 레드블랙트리로 구성되어 있다. map map1; map은 기본적으로 key를 기준으로 오름차순으로 정렬을 한다. 만약 내림차순으로 사용하고 싶다면 map map1;로 사용하면 된다. Map 삽입 그리고 map을 삽입할 때 가장 중요한 점은 pair 객체로 넣어야 한다는 것이다. map1.insert(pair(1, 2)); Map 검색 map은 기본적으로 데이터를 찾을 때 iterator를 사용한다. 그래서 map의 멤버함수인 .. 2023. 4. 14.
백준 1065번(한수) c++ 문제 문제풀이 문제에서 N은 1000 이하의 자연수이다. 그러면 총 세가지의 경우로 나눠 생각할 수 있다. 1 ~ 9 / 10 ~ 99 / 100 ~ 999 로 나눌 수 있다. 그런데 1 ~ 9는 하나의 숫자 밖에 없기 때문에 자동적으로 한수가 된다. 그리고 10 ~ 99 또한 두가지 숫자 밖에 없기 때문에 무조건 등차수열이 될 수 밖에 없다. 그러면 우리는 100 ~ 999의 경우만 생각을 하면 된다. hun = i / 100; ten = (i % 100) / 10; one = i % 10; int fir = hun - ten; int sen = ten - one; if (fir == sen) { stan++; } 이렇게 각 자리의 수를 구한 뒤, 각 자리 끼리 차이를 구하여 만약 차이가 같다면 cou.. 2023. 4. 9.
백준 1018번 (체스판 다시 칠하기) c++ 문제 브루트포스를 통해 이문제를 해결하면 된다. 먼저, 이렇게 W와 B로 시작하는 체스판을 만들어놓고 string w_start[8] = { "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW" }; string b_start[8] = { "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB" }; W와 B로 시작하는 것 중 어떤 것이 더 유리한지 count를 센다. int w_check(int col, int row){ int count = 0; int w_col = 0; i.. 2023. 4. 9.

티스토리툴바