알고리즘(17)
-
[ C++ 백준 1644 ] 소수의 연속합
96%에서 자꾸 틀려서 뭐가 문제일까 고민해봤더니 2를 넣었을 때 0이 나왔다. 소수의 연속합! 꽤나 간단한 문제이다. 여태까지 공부한 내용들을 합치면 되었는데 일단 에라토스테네스의 체를 이용해 입력된 N까지의 소수를 구한다. int primeNumArr[4000001]; vector primeNums; // 소수 구하기 void primeNumSieve(int n) { // primeNum 배열 초기화 for (int i = 2; i
2023.10.24 -
[ C++ 백준 2473 ] 세 용액
이 블로그 글은 문제에 대한 해설이 아닌 글쓴이가 이 문제를 푼 과정을 설명하는 글입니다. 문제에 대한 해설을 보길 원한다면 다른 글을 권장합니다. 골드 이상 난이도 백준 문제를 풀 때는 알고리즘 분류를 보고 푸는 편이다. 정렬, 이분 탐색, 두 포인터를 사용해서 푸는 거라는 힌트를 받을 수 있다. 문제를 간단하게 요약하자면 여러 용액이 입력되고, 서로 다른 3개의 용액을 선택해서 합했을 때 0에 가장 가까운 용액을 만들어내는 세 용액을 찾는 프로그램을 작성하면 된다. 그렇다면 어떻게 풀 수 있는가? 알고리즘 분류를 보면 정렬, 이분 탐색, 두 포인터를 사용하라고 나와있다. 어떻게 풀어야 할까? 일단은 용액 3개를 선택해야 된다는 게 문제였다. 용액 2개라면 간단하게 두 포인터를 이용해서 풀 수 있었는데..
2023.10.22 -
[ 백준 ] solved.ac 플레 도전기
여기서 solved.ac란? 간단하게 이야기해서 백준 문제풀이한 것을 토대로 티어 같은 것을 나타내주는 웹사이트이다. 현재 강산의 티어? 2023 - 10 - 19일 기준 강산의 solved.ac 티어는 골드 2, 1345포인트이다. solved.ac의 랭크 포인트는 상위 100문제의 난이도 합 유저의 CLASS 총 푼 문제의 갯수 로 나타내진다. CLASS 5까지는 점수가 CLASS 하나 오를 때마다 50점씩 오른다 CLASS 1 = +0 CLASS 2 = +50 CLASS 3 = +100 CLASS 4 = +150 CLASS 5 = +200 인 것 같다. CLASS 6부터는 10점씩 오른다. maybe? 플레를 가는 가장 쉬운 방법 클래스 5를 찍는다. 플레1 ~ 골드5 사이 문제들을 왕창 푼다! 일..
2023.10.19 -
[ 잡지식 ] Knuth shuffle, Fisher-Yates shuffle 어원
잡지식 이 알고리즘 이름이 무슨 의미가 있을 지 궁금한 저같은 사람들을 위한 내용입니다. Fisher-Yates Shuffle algorithm Fisher-Yates Shuffle algorithm라는 이름은 이 알고리즘을 고안한 로날드 피셔(Ronald Fisher)와 프랭크 예이츠(Frank Yates), 둘의 이름을 합쳐서 만들어졌다. Knuth Shuffle algorithm Knuth Shuffle algorithm는 컴퓨터 사용을 위해 설계된 피셔-예이츠 셔플의 최신 버전은 1964년 Richard Durstenfeld 에 의해 소개되었다. 그리고 Donald E. Knuth의 책 "The Art of Computer Programming" 에서 "algorithm P(shuffling)" ..
2023.03.11 -
[ C++ 알고리즘 ] Shuffle algorithm
무작위로 요소를 여러 개 뽑을 때 같은 요소가 안 뽑히도록 할 수 있는 알고리즘을 알아보자 ( 중복 제외 랜덤 요소 뽑기 ) Shuffle 알고리즘 간단한 방법 1 ~ 10까지의 수 중에서 중복 없이 3개의 값을 출력해보자 [ 코드 ] 더보기 간단한 예제 #include using namespace std; int main() { srand((unsigned int)time(NULL)); int nums[10]; // 배열 안에 1~10까지의 값을 넣어준다 for(int i = 0; i < 10; i++) { nums[i] = i + 1; } // 배열을 섞어준다 for(int i = 0; i < 100; i++) { int randomIndex = rand() % 100; int randomIndex2..
2023.03.11