본문 바로가기

분류 전체보기105

머지 소트, 머지 소트 트리 및 관련 백준 문제 풀이 머지 소트 트리를 이용한 백준 문제 풀이 수열과 쿼리 1 , 수열과 쿼리 3 , 트리와 색깔 , K번째 수 는 맨 아래를 참고해주세요. 코드 스포일러를 방지하기 위해 접은 글로 풀이를 남겼습니다. 알고리즘에서 c++의 algorithm 헤더에 있는 내장 sort함수는 코드의 간결성과 실수를 줄여줍니다. 그러나, 내장함수가 있다고해서 정렬 알고리즘을 구현할줄 몰라도 되는 것은 아닙니다. 아래의 버블 소트는 알고리즘 입문자들이 대부분 알고있는 정렬 알고리즘으로 O(N^2)의 비효율적인 복잡도로 작업을 수행합니다. 모든 수를 비교하면서 큰 수를 뒤로 보내는 단순한 방식으로 동작합니다. // 버블 소트 for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) {.. 2020. 8. 17.
[BOJ] 백준 10830번: 행렬 제곱 (빠른 거듭 제곱) 먼저 우리는 빠른 거듭 제곱 알고리즘을 알고있습니다. pow(a,y), 즉 a^y 를 구할때 만약 y가 홀수면 a * a^y/2*a^y/2로 분해하여 짝수 거듭 제곱의 반을 구해가면서 O(lgY)의 복잡도로 구할 수 있습니다. int pow(int a, int y) { int x = 1; while (y) { if (y & 1) { x *= a; } a *= a; y /= 2; } return x; } math.h 헤더의 내장 pow를 사용하지 않고 직접 구현하여 쓰는 이유는, 몇몇 문제에서 특정 수로 나눈 나머지 값을 요구하기 때문입니다. 이유는 답이 너무 커지거나 하는 경우에, 보통 1,000,000,007 (1e9+7)와 같은 소수로 나눈 나머지 값을 요구합니다. 소수는 어떠한 수와도 나누어 떨어지.. 2020. 8. 17.
[알고스팟] 종만북 게임판 덮기 ID: BOARDCOVER https://algospot.com/judge/submission/recent/ algospot.com :: 답안 목록 683263 JUMPGAME Moongthy cpp 800B 컴파일 실패 13분 전 algospot.com 현재 좌표 x, y 가 비어있다면 x,y를 기준으로 블록을 놓을 수 있는 경우의 수는 4가지가 있습니다. 먼저 맨 위쪽이면서 가장 맨 왼쪽에 블럭을 놓을 수 잇는 게임판 좌표 x,y를 찾아 4가지 블록에 대하여 가능한 블록으로 덮고 DFS를 진행하면 됩니다. cover 함수를 만들어서 flag가 1이면 해당 좌표에 블록을 두고 0이면 둔 블록을 해제 하는 식으로 방문 배열 역할을 하게끔 만들었습니다. (이런 구현 이슈가 있는 문제들은 모듈화 시켜놓는 것이 좋습니다.) 또한 게임판.. 2020. 8. 17.
[알고스팟] 종만북 소풍 : PICNIC https://algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 algospot.com 모든 친구가 서로 친한 친구의 쌍을 이루는 조합의 개수를 찾는 문제입니다. n이 10이므로 모든 경우를 완전 탐색을 통해 찾아 가면서 가능한 경우만 세어주면 됩니다. 예를 들어 n이 6인경우 친구관계가 모두 친하다고 가정한다면, (1,2),(3,4),(5,6) , (1,3),(2,4),(5,6) ... 등 이 있습니다. 그러나 (1,2)와 (2,1) 쌍은 같으며 (3,4),(.. 2020. 8. 17.

티스토리툴바