이진 트리 중에서도 힙.힙 중에서도 최소힙을 구현한 코드C++에서 대소비교에 기본값인 less than(

문자열을 정수로?이 글에서 다루는 내용은, 문자열의 형태로 적혀있는 "112223"과 같은 문자열을 말하는 것이 아닙니다. 영어 소문자로만 이루어진 "aaabbb" 또는 대문자로만 이루어진 "ABCCDD" 같은 문자열을 정수형 변수 하나에 담는 것을 말합니다.왜?보통 해싱은 작은 크기로 우겨넣기 때문에 데이터 손실이 일어나는 형태가 많습니다. 그래서 그대로 저장하면 충돌 해결 이슈가 따라오죠. (resolving collisions in hash tables) 정수로 바꾸어서 다룬다면 문자열 비교를 길이만큼인 \(O(|s|)\) 가 아닌 정수 비교 시간인 \(O(1)\) 으로 줄일 수 있습니다. 조건만 가능하다면 데이터의 손실 없이 그대로 담을 수도 있죠.26진법소문자 26개 혹은 대문자 26개만 사용하..

성능 테스트 코드를 작성하다가, 평균을 실시간으로 구하는 방법을 글로 정리해볼까 한다. (직관으로) 어렸을 적에 이게 당연한 줄 알았다. 근데 몇개의 반례를 찾고는 틀렸다고 생각했다. 그런데 학부 시절에 교수님께서 '그런 것이 있다'고 말씀해주셨다. 이름은 Moving average이고, 한국어로는 모르겠다. 나는 데이터 범위에 따라 점진적으로 평균을 구해간다는 느낌으로 점진적 평균 또는 실시간 평균으로 부르고 싶지만, 통계쪽에서 "이동 평균"으로 부르는 모양이다. 아무튼, 본디 평균을 구하는 식은 전체 합 \(S_n\)에서 데이터의 개수 \(n\)만큼 나눈 \(S_{n} / n\) 이다.그럼 이것이 뭐가 문제인가?\(n\)개를 전부 더하거나 카운팅 하지 않으면 평균을 구할 수 없다. 어떤 실험 \(X_..

링크: https://www.acmicpc.net/problem/5535문제각 날짜마다 입을 수 있는 옷들이 있고, 다음 날과 옷의 화려함의 차이가 최대한 크도록 옷을 고르는 문제이다.날짜마다 가능한 옷을 저장해둔다. 그 날에 한해서는 옷의 종류나 순서가 중요치않길래 화려함 정도를 넣어버렸다. 이제 각 날짜마다 옷을 하나씩 고른다면, 총 D일동안 N가지의 옷을 고르므로 경우의 수는 \(O(N^{D})\) 이다. 어떤 d번째 날에 A라는 옷을 골랐다고 치자. 그럼 d+1번째 날 이후로는 d번째 날에 A를 고른 영향이 계속 생긴다.즉, d번째 날에 a를 고른 이후로는 하나의 부분 문제로 볼 수 있다. 점화식을 dp[D][N] = D번째 날에 N번째 옷을 선택했을 때의 화려함의 최대값 으로 세우면 \(O(ND..

문제2019년 초에 신년을 맞아 싱가포르 국립대학교(NUS) 천재들과의 문제 배틀이 있었다.그 중 하나로, 빨간 화살표가 가리키는 방향에는 빨간 화살표가 2개만, 회색 화살표가 가리키는 방향에는 빨간 화살표가 2개가 아니도록 화살표를 색칠하는 문제가 있었다.규칙을 만족하는 포인트를 파악해서 논리적으로 연결해나가는 것이 맞지만, 우리는 컴퓨터가 있다.무식하게 모든 경우를 전부 확인해보자. 정말 답이 하나일까? 세로 4행, 가로 5열 총 전체 20개의 칸을 모두 색칠해보는 경우는, 각 칸을 색칠한다/하지않는다 2가지의 선택이 20개 칸마다 있는 것이므로\(O(2^{20})\)이다. 색칠 후에는 각 화살표들이 모두 규칙을 만족하는 지 확인해야하므로 연산이 조금 더 붙지만, 그래도 3천만번 이하로 계산된다.이 ..

여기서 맞왜틀이란, "맞았는 데 왜 틀렸지?"에 줄임말입니다. 이 글은 알고리즘 문제 풀이(Problem Solving)를 하면서 종종 마주하는 "맞왜틀?"을 피하는 방법들을, 제가 아는 지식과 겪어본 경험을 토대로 정리해볼까 합니다. 코드의 구현과 관련한 깊은 내용들은 C/C++을 기준으로 이야기합니다. 문제를 푸는 환경 이제는 많은 문제 풀이 플랫폼과 온라인 저지 사이트들이 있습니다. 역사 깊은 UVa Online Judge부터 Algospot(알고스팟), Baekjoon Online Jubge, 프로그래머스까지 굉장히 다양하고 많아졌습니다. 각 사이트마다 채점 방식이나 결과가 다를 수 있으니, 이것을 먼저 찾아보고 이해하는 것이 좋습니다. 어떤 컴파일러로 채점하나요? 대부분의 사이트에서 C, C++..

나(I)는 8, 우리(WE)는 71이라는 말로 I=8, W=7, E=1 임을 알 수 있다. 3*3 마방진은 1에서 9 사이의 숫자를 채워서 각 행의 합, 각 열의 합, 그리고 두 대각선 위에 있는 수의 합이 모두 같게 만드는 고전 게임이다.그럼 위 문제는 아래처럼 생긴 3*3 칸을 채우는 마방진이다.정말 답이 하나밖에 없을까?코딩으로 모든 경우의 수를 전부 시도해보자!코드결과4 9 2 3 5 7 8 1 6 >> YOU = 539 total: 1 정말 답이 하나만 존재한다.

링크: https://www.acmicpc.net/problem/2517문제최선의 등수는 다시 말하면, "a[k] = 어떤 k 입장에서 왼쪽으로 자신보다 높은 실력의 개수" 이다."왼쪽으로"의 뜻은 "이전까지 등장한"과 같은 말이고, 자신보다 높은 실력의 개수는 기록을 통해서 셀 수 있다.문제는 수의 범위가 1,000,000,000 이하라서 수를 직접 저장하기는 힘들어 보인다.문제 조건 중, 참가한 선수들의 실력은 모두 다르다는 조건이 있다. 그럼 같은 의미로 그 사람의 등수를 기록하자.N은 50만 이하이므로, 등장한 등수(rank)를 1로 기록하고 k 위치에서 자신보다 높은 실력(=등수)는 세그먼트 트리로 쉽게 셀 수 있다.선수 k의 최선의 등수는 query(자신의 등수 + 1, 범위 끝) + 1이다...