본문 바로가기
[Math] 로그 로그 로그는 지수를 표현하기 위해 사용한다. $2^x = 4$에서 x를 구하는 것은 아주 쉽다. 답은 2다. 하지만 $2^x = 10$일 때 x는 어떻게 구할까? x의 값이 3 보다 크고 4보다 작다는 것은 알 수 있지만 정확하게는 알 수 없다. 그래서 로그가 필요하다. 로그를 활용해서 x를 표현해보면 $log_210$이다. 이것을 이해할 때는 '2를 거듭제곱하여 10이 되게 만드는 수'라고 하면 된다. 참고로 작게 쓰는 숫자를 밑이라고 하고, 크게 쓰는 숫자를 진수라고 한다. 밑과 진수의 조건 로그는 지수에서 파생되었기 때문에 지수의 성질을 잘 이해하면 로그의 성질은 저절로 알 수 있다고 한다. $log_ab$일 때 a > 0, a != 1, b > 0을 만족해야 한다. 지수가 유리수일 때부터 정의되려..
[백준 C++] 6549번 히스토그램에서 가장 큰 직사각형(스택, 라인 스위핑) 히스토그램에서 가장 큰 직사각형 기록을 확인 해보니 정확하게 23일 전에 분할정복으로 해결하려고 했다가 시간초과 문제를 도저히 해결할 수 없어서 포기했던 문제다. 풀지 못했던 문제를 시간이 지남에 따라 풀 수 있게 되는 것도 알고리즘 공부의 쏠쏠한 재미인 듯 하다. 히스토그램에서 '가장 큰 직사각형'이 되기 위해서는 각 높이(height)를 가지고 만들 수 있는 가장 큰 직사각형 중 가장 큰 값이어야 한다. 각 막대는 자신보다 작거나 같은 최초의 막대를 왼쪽과 오른쪽에서 각각 하나씩 찾아야 한다. 왼쪽과 오른쪽 값을 찾는 것이 이 문제의 시간 복잡도를 결정짓는다. 나도 처음에 생각했던 Brute Force로 한다고 하자. 최악의 경우에 각 막대는 가장 왼쪽까지, 그리고 가장 오른쪽까지 탐색해야 결과를 얻..
[백준 C++] 1931, 4307번 회의실배정, 개미 - 그리디 알고리즘 회의실배정개미 이 링크에는 그리디 알고리즘(탐욕법)을 활용해 풀 수 있는 문제들이 몇가지 있다. '동전 0' 문제는 전에 풀어서 이번에는 풀지 않았고, 'ATM'과 '로프'는 상대적으로 난이도가 낮았으므로 따로 포스팅을 하지 않고, '회의실배정'과 '개미' 문제를 풀면서 그리디 알고리즘을 어떻게 적용시킬 것인지 고민해봤다. 그리디 알고리즘 그리디 알고리즘은 문제를 해결하기 위해 문제를 여러 개의 조각으로 나누고, 각 조각의 답을 바탕으로 답을 찾는다는 점에서 동적계획법과 비슷한 점이 있다. 하지만 동적계획법은 문제 해결을 위해 (거의) 모든 선택지를 고려해보고 그 중 답에 해당되는 것을 고르는 것인 반면, 그리디 알고리즘은 조각에 해당하는 작은 문제를 풀 때마다 최선의 방법만을 선택하기 때문에 최선이 아..
[Programmers C++] Winter Coding(재시도) 윈터 코딩 프로그래머스에서 주최하는 겨울 인턴 프로그램 코딩 테스트에 참가한 적이 있다. 알고리즘을 막 배우기 시작했던 단계였으며, C++은 아직 하지도 못했던 터라 Javascript로 참가했었다. 결과가 너무 처참해서 아직도 기억이 난다. 두 시간동안 세 문제를 풀어야 하는데, 두 번째와 세 번째 문제는 봐도 아무것도 모르겠어서 첫 번째 문제라도 풀어야겠다 싶어서 두 시간동안 그것만 풀었는데 그것마저 못 풀었다. 그 이후로 '이래서는 안되겠다' 싶어서 BOJ도 열심히 풀고, C++ 공부도 하고, 알고리즘과는 관련없지만 정보처리기사 준비를 위해 운영 체계 공부도 하며 겨울 방학을 알차게 보냈다. 방학이 끝나가는 지금 겨울 방학 동안 한 것의 성과를 확인하기 위해 겨울 인턴 프로그래밍 코딩 테스트 문제를..
[백준 C++] 7576, 7569번 토마토, 토마토 토마토토마토 두 문제 모두 BFS를 활용해서 풀 수 있기 때문에 이번 기회에 BFS를 연습했다. 비슷한 아이디어로 풀 수 있는 문제들이다. 두 문제 모두 상자에 있는 모든 토마토가 익는데 며칠 걸리는지 알아내는 문제다. 첫 번째 토마토 문제의 경우에는 상자가 하나 밖에 없으므로 상자의 가로, 세로 사이즈만 알면 풀 수 있지만, 두 번째 토마토 문제는 상자가 여러 개 있을 수 있기 때문에 가로, 세로 뿐만 아니라 높이도 알아야 한다. 그래서 조금 더 복잡하고 실수하기 쉽다. 두 문제의 공통적인 접근법은 다음과 같다. 1. 가로(M), 세로(N), 높이(H)는 int 타입으로 할당해 입력받는다. 하지만 칸 안에 토마토가 익었는지(1), 익지 않았는지(0), 아예 토마토가 없는지(-1)에 대한 정보는 int에..
[백준 C++] 1890 점프 점프 (0, 0)에서 (N - 1, N - 1)로 가는 경로의 수를 파악하는 문제다. 각 칸에는 그 칸으로부터 몇 칸을 움직일 수 있는지 정해져있으며, 오른쪽이나 아래로만 움직일 수 있다. 한 번에 움직일 수 있는 거리는 0보다 크거나 같고, 9보다 작거나 같다. 한 번에 움직일 수 잇는 거리가 0이 될 수도 있다는 점을 못봐서 한번 틀렸었다.(메모리 초과)또한 가능한 경우의 수가 최대 $2^{63} - 1$이라고 제한을 줬으며, 중간값이 이 값보다 커질 가능성은 없으므로 cache는 long long 타입으로 해도 충분했다.그 이외에는 주의할 사항이 없다. 123456789101112131415161718192021222324252627#include using namespace std;#define ..
C++ 토막 지식(19.01.16) - class Class private and public객체지향의 핵심 특성은 데이터 은닉화(data hiding)이다. 데이터 은닉화는 클래스 외부의 함수가 클래스 내부에 있는 정보에 접근하지 못하도록 막아주는 것이다. 보안 상의 문제 때문에 은닉화를 한다기보다는 클래스 외부에서 그 데이터로 접근할 필요가 없을 때 은닉함으로써 프로그래머가 실수를 저지를 가능성을 줄여준다. private 과 함께 선언된 변수나 함수들은 클래스 내부에서만 사용할 수 있고, public 과 함께 사용된다면 이와 반대로 외부에서도 접근할 수 있다. 클래스를 초기화 할 때는 Initializer List가 선호된다. 예를 들어 이중 연결 리스트를 위한 노드를 만든다면 다음과 같이 생성자를 만들어 초기화를 할 수 있다. 12345678910..
[백준 C++] 피사노 주기와 행렬 제곱을 활용한 피보나치의 수 구하기 피보나치 수 3피보나치 수 6 백준 블로그를 참고했다. N 번째의 피보나치 수를 구해야 할 때 N 의 수가 충분히 작다면 재귀함수나 반복문, 메모이제이션을 활용해서 문제를 풀면 된다. 하지만 '피보나치 수 3' 나 '피보나치 수 6' 처럼 N의 범위가 1,000,000,000,000,000,000 까지라면 위에서 언급한 방법으로는 시간을 맞출 수 없다. 그래서 두가지 방법을 활용할 수 있는데 하나는 '파사노 주기이며 다른 하나는 행렬의 제곱이다. 피보나치 수 3피보나치 수 3은 N의 범위가 1,000,000,000,000,000,000 까지고 결과값을 1,000,000으로 나눈 값을 출력해야 한다. 피보나치 수를 M 으로 나눈 수는 항상 주기를 가지게 되는데, 이를 피사노 주기(Pisano Period)..

티스토리툴바