코테에서든, 자료구조에서든 정렬은 항상 빼놓지 않고 등장하는 중요 요소입니다. 또한 많은 알고리즘의 기본 base로 깔고 가는 개념이기도 하죠. 자료구조 수업에서도 정렬을 구현하는 수많은 방법을 배우고, 그 방법을 익히는 것도 중요하지만, 이 글에서는 정렬 방법에 대해서는 다루지 않습니다. 이번 포스트에서는 정렬 개념을 어떤 방식으로 문제에 적용시키는지, c++에서는 어떻게 정렬하는지 정도를 설명해 드리겠습니다. www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acm..
게임 이론(스프라그-그런디 이론)을 공부할때 유용하게 참고했던 블로그들입니다. 새로 공부를 하실 분들은 참고하시길 바랍니다 ;D https://ohgym.tistory.com/21 nim game과 grundy number nim game과 grundy number를 익히기 전에 이와 같은 필승 전략 게임이론이 적용되기 위한 전제조건부터 알아보자. Impartial game 두 플레이어가 게임을 하는데 아래 조건을 만족해야 한다. 모든 정보가 공개된 게.. ohgym.tistory.com https://tataky.tistory.com/2 BOJ 게임 문제 스페셜 최근 BOJ에 정체불명의 게임 문제들이 많이 추가되었다. 님 게임 문제뿐 아니라, 그리디하게 풀 수 있거나 자료구조를 이용하는 문제도 있고, ..
문제를 풀다보면 때때로 기댓값을 묻는 문제들이 있습니다. 제목은 기댓값 알고리즘이지만 사실 거창한 알고리즘은 없고, 기댓값 문제의 접근방식과 대략적인 용어설명을 하려고 합니다. 사실 처음들었을때 기댓값이라는건 약간 생소할 수 있습니다. 하지만 대다수의 확률을묻는 문제들이 dp로해결하는것 과 같이, 기댓값문제들도 거진dp로 해결할 수 있습니다. 제일 쉬운 예제를 한번 보면, https://www.acmicpc.net/problem/13250 13250번: 주사위 게임 효빈이는 1부터 6까지 수가 적혀있는 6면 주사위를 가지고 있다. 매번 주사위를 던질 때마다 주사위의 윗 면에 적힌 수 만큼 사탕을 받게 된다. 효빈이가 적어도 N개의 사탕을 받기 위해 주사위를 던져야 하는 횟수의 기댓값을 구하는 프로그램을 ..
본 포스팅은 구종만님의 블로그를 스크랩한 글임을 밝힙니다. http://theyearlyprophet.com/heavy-light-decomposition.html Heavy-Light Decomposition Heavy-Light Decomposition @jongman 팔로우하기 트윗하기 [처음으로] [모든 글 보기] [같은 카테고리의 글 보기: 알고리즘] 작년에 1년동안 쉬면서 한 여러 가지 일 중 하나가, 오랜만에 다시 프로그래밍 대회에 참가하는 것이었다. 비록 연습만 열심히 하고 대회에 제대로 참가하진 못했지만, 최근 나온 문제들을 풀어볼 기회가 되어서 좋았다. 최근 문제 출제 경향은 과거에 비해 꽤 바뀌었음을 느꼈는데, 기존에 출제되지 않았던 테크닉들 theyearlyprophet.com 1/..
