BBTY의 공부 기록 BBTY의 공부 기록

집합 관련 문제를 풀다 알아두면 좋을 STL인 것 같아 포스팅 하려 한다. 선언은 set 이름; e.g) set st; 삽입은 st.insert(s1); 제거는 st.erase(s1); map과 비슷함. 반복자를 이용한 begin, end, find 등의 활용 가능. 처음에 정렬 기준을 세울 수 있음. set st(pred); 가장 큰 특징은 중복이 허용 되지 않음.

https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 감기 때문에 평소보다 머리도 안 돌아가고.. 고생고생해서 하나 풀고 자려 했는데 이게 웬걸 틀림... 그래도 힘내서 풀고 새로운 내용이라 포스팅까지 하자는 생각으로 글을 쓴다. 사실 이거 왜 시간 초과가 떴는지는 모르겠다. 사고과정은 다음과 같다. a, b, c, d, e ab, bc, cd, de ... 이런 식으로 하나씩 map에 넣으면서 중복이 아닌 것만 세준다. 반복문도 하나인데 시간 초과 나옴.. 왜인지 모르겠..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 음.. 사실 이거 굳이 포스팅 하려고 하지는 않았는데.. (너무 쉽게 풀려서) 구글링을 해보니 다들 이진탐색으로 풀어서 '뭐지?' 싶어서 더 쉽게 풀고 싶은 다른 사람들에게 도움이 될까 하여 적는다. 처음에는 map를 선언하여 찾았다. 근데 사실 시작 전부터 안될 것 같긴 했다 ㅋㅋㅋ.. value가 같은 ..

이틀동안 이것저것 알아본다고 PS에 손을 대지 않았다. 이틀 안했다고 그새 뻑뻑해진 느낌.. 하루도 거르지 않는 습관을 들이자. https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net map 사용 문제이다. 풀고난 후의 관전 포인트는 '처음에 map을 선언할 때 key와 value의 자료형을 어떻게 지정할 것인가'인 듯 하다. 처음 풀 때도 정답은 나오기는 했다. 그러나 이 문제는 시간 ..

백준 7785번을 풀다가 화가 머리 끝까지 났다. 분명 답은 맞는데 시간 초과가 뜨는 것. 그런데 구글링을 한 결과 심지어 코드가 거의 흡사한데도 내 것만 시간 초과가 떴다. 약 20분 가량 코드를 브루트 포스 마냥 한 부분씩 수정하면서 뭐가 차이인지 실험해봤다 ㅋㅋㅋㅋㅋ 결국 얻은 해답은 endl과 "\n"의 차이였다. endl은 버퍼에 저장 했다가 출력할 때 한꺼번에 쏟는 방식이라 더 느리다는 것이다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 진짜 개어이없음.. 이거 하나로 속도 차이가 이렇게 난다는 것도 신기하기도 하고.. 아무튼 다시는 이런 실수 하지말자는 취지에서 글을 썼다.

https://www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 백준 11005번을 푸는데, char 배열의 한계를 느꼈다. 처음에 배열을 생성하고 문제를 풀려 했는데 당최 배열의 끝을 얼마로 지정해야 하는지 모르겠는 것이었다. 또, 얼마를 할당해야 하는지를 알 수는 있으나 그걸 알기 위해 반복문을 하나 더 써야해 비효율적이라는 생각이 들었다. 그래서 자동으로 동적할당을 해주는 문자열이 뭐가 있을까 찾아보니 C++에는 string이 있었다. 거의 써본 적..

백준 단계별로 풀어보기에서 집합과 맵 부분의 14425번을 풀다가 처음으로 손도 못대고 막혔다. 맵을 쓰지 않으니 시간 초과가 나고.. 맵을 쓰자니 C++에서 어떻게 구현을 하는지도 모르겠고 STL도 어떻게 쓰는지도 모르겠고.. 옛날에 자바할 때 한 번 써본 기억이 있는데 너무 오래 전이라 지금은 개념정도밖에 기억나지 않는다. 그래서 이왕 이렇게 된 김에 정리도 하고 STL도 암기하자는 생각으로 글을 쓴다. 문제 링크: https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검..

C++의 map 자료구조에 대해 공부하다 원리가 Hash임을 알게 되었고, 원리를 정확히 알고 쓰자는 생각으로 짧게 정리해보려 한다. 원소의 값에 의해 원소가 저장되는 위치가 결정되는 자료구조. 검색, 삽입, 삭제 등의 연산을 평균적으로 상수 시간에 할 수 있음. O(1) 해싱(Hashing) - 매핑의 전체 과정 키(Key) - 매핑 전 원래 데이터의 값 해시함수(Hash Function) - 임의의 길이의 데이터를 특정 길이의 데이터로 변환하는 함수 해시값(Hash Value) - 매핑 후 데이터의 값 해시함수를 통해 해시값을 할당할 때, 중복되는 인덱스값을 사용하게 되면 해시충돌이 일어남. 해결 방법 1 - 체이닝(Chaining) 같은 인덱스로 해싱되는 노드..