talALGO

리스프

Common Lisp로 구구단을 외자

삶에 지쳤다면 구구단이나 외며 시간을 보내자. 별로 어려운 일이 아닐것이다... Common Lisp과 함께한다면. 1단계: mult-table-1 파라미터 level에 해당하는 곱셈 표를 출력하는 mult-table-1 함수를 만들자. 아래와 같은 출력을 갖는다. CL-USER> (mult-table-1 8) 8x1=8 8x2=16 8x3=24 8x4=32 8x5=40 8x6=48 8x7=56 8x8=64 8x9=72 우선

백준

BOJ 18119 단어 암기

출처 : https://www.acmicpc.net/problem/18119 첫번 째 생각 : 완전 나이브 O(단어 개수 * 단어길이 * 쿼리 개수) 이러면 왠지 메모리에서 크트 당할꺼 같아서 좀 더 생각 해봄 두번 째 생각 : 어떤 알파벳에 대해서 내가 알고있다, 모르고 있다만 알고 있으면 대니깐 각 단어에 대해서 알파벳에 대해서 1(알고있다), 0(모르고

코드포스

Codeforces Round #485 (Div.2)

이번꺼는 버추얼후기. A. Infinity Gauntlet map을 적극 활용하자. map이 없다고? 거짓말하지마세요 그런언어가 어딨어. source : https://codeforces.com/contest/987/submission/65464832 B. High School: Become Human xy 과 yx을 직접 구해서 비교하려면 당연히 터진다. 양 변에 로그를 씌워서 ylogx와 xlogy를 비교하자. source : https://codeforces.com/contest/987/submission/65465055 C.

코드포스

Codeforces Round #601 (Div.2)

A. Changing Volume abs(a-b)를 5로 최대한 채우고, 나머지를 2로 최대한 채우고, 마지막을 1로 채우는 그리디. source : https://codeforces.com/contest/1255/submission/65352313 B. Fridge Lockers 구데기문제. 원래 조건이 2<=n<=1000, 1<=m<=2000 이었는데 m>n 일때 정해에서 잘못된 답을 내놓는 것이 대회중에 발견되어서 중간에 급하게

알고리즘

Radix Sort

오랜만에 나는 야호다. 오늘은 라딕스 소트라는걸 배워보자. 본인은 매우 애용한다. Counting Sort Radix Sort를 배우기 전에 우리는 Counting Sort에 대해 알아보아야 한다. 만약 다음과 같은 문제가 주어졌다고 하자. 1000만 개의 숫자가 주어진다. 각 숫자는 0 또는 1이다. 이를 정렬하라. 비교기반 정렬을 때리면, $$O(nlogn)$$으로 매우 오랜시간이 걸린다. 하지만 우리는

BOJ 13512 트리와 쿼리 3

ㅎㅇ! 오늘은 트리와 쿼리 3을 들고 왔다! 문제: 트리와 쿼리 3 HLD를 안다면, 크게 어려워할 문제는 아닐거라 생각한다. HLD에서 dfs ordering과 chain의 생성을 담당하는 부분(위 글에서 dfs2 함수)을 잘 살펴보면, 1에서부터 모든 정점 v까지의 경로에 포함되는 정점들의 order는 깊이가 깊어짐에 따라 순 증가함을 알 수 있다. 이를 이용해

BOJ 13510 트리와 쿼리 1

ㅎㅇ! 오랜만에 글 쓴다. 사실 그동안 센트로이드 디컴퍼지션 짜다가 짜증나서 얼른 이 문제로 갈아 탔다. 각설하고, 트리와 쿼리 1을 푸는 방법을 알아보자. 선행지식: Heavy Light Decomposition 문제: BOJ13510 우선, HLD 문제 잘 푸는 사람이 이 글을 볼 리는 없다는 가정하에 글을 쓴다. HLD를 배웠다면 HLD의 작동 메커니즘이 간선이 아닌, 노드

자료구조

hash table을 구현해 보자

이제 학교에서 해우면서 PS에서 사용하는 자료구조 포스팅은 이게 아마 마지막일듯 싶다. Q. ??? 너는 학교에서 rb-tree도 안배움?? A. 배웠다. 근데 못짠다. 그리고 PS에서 실제 구현하는 사람이 있을까 싶다.... 우리는 map이 있자나!!!! 그리고 내가 rb-tree를 못짜고 map을 사용하는 방법도 모르기에 hash table을 구현해서 문제를 비벼오고 있다. Q. 이글에선 충돌 어떻게 처리할거임? A.

백준

BOJ 17143 낚시왕

문제 : https://www.acmicpc.net/problem/17143 아마 코테시즌이 되면 백준에 질문이 가장 많이 올라오는 문제가 아닐까싶은 문제, 낚시왕이다. 개인적으로 기출로 나왔던 시뮬레이션 문제들이 대부분 디스크립션을 한 번에 알아보기 힘들어서 늘 몇 번씩 읽어봤었는데 이 문제는 바로 로직을 구성할 수 있을 정도여서 코드를 짜는데 그렇게 오래걸리지는 않았다. 이런 시뮬레이션 문제에서

이중 연결 리스트를 구현해 보자

씹어먹는 C를 배우는 중에 연결 리스트를 구현하는 예제가 있었다. 구조체와 동적 할당을 배우기 아주 좋은 예제다. 하지만 나는 이미 STL의 뽕맛을 본 몸이라서 그냥 연결 리스트로는 만족할 수가 없었다. 그래서 STL list 의 흉내라도 낸, 양쪽에서 삽입/삭제가 O(1)에 가능한 이중 연결 리스트를 구현해 보았다. 리스트가 잘 작동하는지

자료구조

stack을 구현해 보자

스.택.을.구.현.해.보.자 알지? 연결리스트로할꺼임ㅋ 코드부터 보자 그리고 당연한 이야기겠지만 마지막에는 문제를 통해서 아래 코드를 검증해 볼 것이다. struct node { int num; struct node * pre; }; struct node *f, *r; void push(int); struct node pop(); int isempty(); void push(int num) { struct node *temp; temp

배열과 포인터

수많은 사람들의 머리를 터뜨려버린 배열과 포인터의 관계에 대한 나의 장렬한 전쟁기록을 남겨두기 위해서 이 글을 쓴다. 결론은 뻔하지만 배열은 배열이고 포인터는 포인터라는 것이다. 이 부분에 대해서 글을 쓴 어느 블로그에 들어가도 나와 있는 결론이다. 하지만 이걸 마음속 깊이 깨닫기 위해서는 누구나 머릿속에서 전쟁을 한번쯤 치르게 된다. 만약 이게 술술 이해되는

백준

BOJ 17835 면접보는 승범이네

출처 : https://www.acmicpc.net/problem/17835 아 이거 사실 증명 안하고 예전에 풀었던거 비슷하게 감으로 떄려 맞췄다. 그래서 정당성에 대한 설명은 못하겠고 풀이방법만 적을게.(누가 증명좀 ㅎ) 1. 역방향 그래프를 만든다. 2. 출발지는 면접장 전체다. -> pq, memo에 면접장 전부 반영해준다. 3. 다익스트라를 돌린다. 4. 그럼 memo[i]가

팁

[숏코딩] 함수 반환값 이용하기

숏코딩에서는 함수 반환값을 많이 사용한다. 이 글에서는 함수의 반환값을 이용하는 여러 예를 소개하고자 한다. 파일 끝날 때까지 입력받기 while(~scanf("%d",&n))printf("%d",n); scanf는 성공적으로 입력받은 인자의 개수를, 첫 번째 인자를 받기도 전에 input failure이 일어나면 EOF를 반환한다. * 파일의 끝에서 scanf()가 EOF 반환 * EOF = -1 * -1 은

자료구조

Splay Tree

나는 야호다. 오늘은 Splay Tree에 대해 설명하겠다. Splay Tree는 무엇인가 Splay Tree는 균형이진탐색트리(Balanced Binary Search Tree, BBST)의 한종류이다. Splay Tree라는 이름이 붙은 건 Splay라는 재밌고도 신기한 연산을 사용하여 amortized $$O(log n)$$의 시간복잡도를 유지하기 때문이다. 설명에 앞서 균형이진탐색트리에 대해 잠깐 알아보고 가자. 이진탐색트리는 특정 데이터의 삽입, 삭제,

C언어

Fast I/O

그 누구보다 빠르게

리스프

Common Lisp을 위한 정규표현식

CL-PPCRE cl-ppcre는 PCREPerl Compatible Regular Expression를 커먼 리습에서 쓸 수 있도록 구현한 것이다. ppcre는 순수하게 리습으로 구현되어있어 다른 네이티브 라이브러리에 의존하지 않는다(PPCRE의 첫 글자인 P는 portable의 머리글자인데, 바로 이러한 이유이다). 그럼에도 불구하고 커먼 리습의 컴파일러 매크로를 이용하므로, 상당히 좋은 성능으로 동작한다. 커먼 리습 생태계에는 정규표현식을 처리하는 다양한 다른 라이브러리가

자료구조

Persistent Segment Tree

다음과 같은 문제를 생각해보자. 크기가 N인 배열에서 주어지는 [l,r] 범위들의 합을 각각 구하여라. 어디서 본 것같지 않은가? 그렇다. hld 글을 시작했던 그 문제이다. 저 글에서 우리는 이 문제에 update를 얹고 배열을 트리형태로 바꾸었을 때 어떻게 처리해야할 지를 다루었는데 이번에는 문제를 약간 바꿔보겠다. 크기가 N인 배열에서 주어지는 [l,r] 범위의

알고리즘

키타마사 법

나는 야호다. 오늘은 키타마사법에 대해 배워보도록 하겠다. 선형점화식을 풀자 PS를 하다보면 점화식을 풀 일이 종종 생긴다. 그 중에서 가장 많이 나오는 점화식은 당연히 다음과 같은 선형점화식의 꼴일 것이다. $$ \begin{aligned} a_n&=c_1 a_{n-1}+c_2 a_{n-2}+... +c_m a_{n-m}\\ &=\sum c_i a_{n-i} \end{

C언어

포인터의 형변환

요즘 해야 하는 공부는 산더미인데 그건 안 하고 맨날 C,C++ 문법을 공부중이다. 사실 그것도 나태하게 하고 있는 중이다. 엠생이다. 하지만 머릿속에 넣는 게 아예 없는 건 아니므로 그 중 하나를 여기에 남긴다. 앞으로도 그런 게 있으면 남기겠다. C문법 같은 건 인터넷에 잘 정리된 글이 수없이 많으므로(나는 씹어먹는 C를

팁

이맥스로 리스프 개발환경 구축하기

이맥스여야만 하는가? 리습 프로그램을 짜는 개발 환경으로는 이맥스가 거의 유일하다. 물론 다른 에디터들에도 리습을 위한 플러그인들이 존재하고, LispWorks라는 어썸한 IDE도 있지만, 다른 에디터를 위한 플러그인들은 이맥스에서 제공하는 것에 비해 빈약한 편이고, LispWorks는 상용 프로그램인데다 이맥스와 별 다르지 않은 환경을 제공한다. 그럼 어째서 이맥스가 그토록 특별한 리습 개발 환경이 될 수

수학

Fast Fourier Transformation

나는 야호다. 오늘은 FFT에 대해 알아보겠다. 이의 이론적 배경을 위해서는 선형대수학에 대한 지식이 다소 필요할수 있으므로 알아서 잘 알아듣길 바란다. (설명은 할것이니 걱정안해도된다.) 선형대수학 기본 본인이 선형대수학에 자신이 있다면 이 부분은 과감히 넘겨도 좋다. 벡터에 대해서 들어본 적이 있는가? 보통 벡터라고 하면 떠올리는 게 고등학교 기하와 벡터에서 배우는 그 벡터일것이다.

코드포스

Codeforces Round #598

A. Payment Without Change 요약 : q개의 케이스가 주어지고 각 케이스마다 n의 가치를 가진 동전 a개와 1의 가치를 가진 동전 b개가 주어진다. 이 때 이 동전들의 가치의 합을 정확히 S로 만들 수 있는가? min(S/n,a)*n + b >= S 인 경우 가능하고 그 외의 경우 불가능하다. S를 넘지 않는 선에서

트러블슈팅

Virtual Box Ubuntu16.04 CPU 제한 풀기

ploffer11이다. Virtual Box 성능이 마음에 안들어서 CPU 개수를 보니 1개였다. 늘리려고 보니까 fix되서 움직이지도 않는다. 뭐가 문제인가? 크게 세가지의 에러 원인이 있는거 같은데 일단 대표적인 두개만 언급할 것이다. 1. Hyper - V 2. WSL 3. BIOS  - 이걸 잘 모름 여기 보던가 https://stackoverflow.com/questions/44562907/cant-enable-multiple-cpu-on-virtualbox 1, 2번에

수학

넥슨 코딩테스트 기출 - ANUMBER

이번 포스팅에서는 넥슨 게임프로그래밍직군 테스트에 나왔던 문제인 A-NUMBER라는 문제의 풀이에 대해 포스팅 하고자 한다. 문제가 제법 어렵지만 차근차근 풀다보면 또할만하다. 제곱한 수의 끝에 자기 자신이 나오려면? 우선 가장먼저 해결해야될 문제는1~21억사이의 숫자 x에 대해 F(x)가 참인지 판별하는 방법이다. 정수를 문자열로 바꾼뒤 비교를 해도 되겠지만 얼핏봐도 꽤나 시간이 많이