본문 바로가기

내 이야기

 (70)
BOJ 4948 베르트랑 공준 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net BOJ 상으로는 수학 카테고리에 있는데 이게 왜 수학 카테고리에 있는지는 모르겠는 문제, 에라토스테네스의 체를 쓸 수 있다면 매우 간단한 문제이다. 임의의 자연수 n ~ 2n 사이의 소수의 개수를 구하는 문제이다. 그런데 문제 하나에 1~123456 사이의 임의의 값이 입력되기도 하고, 한 번에 여러 개의 질문이 들어온다. 때문에 1~246912 사이의 모든 소수를 구해놓고, 구간 안에 들어있는 소수 개수를 세는 방식으로 해결한다. 알고리즘은 간단하다. ..
BOJ 1715번 카드 정렬하기 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제가 복잡해 보이지만 사실 문제를 단순화하면 리스트 내의 가장 작은 두 수의 합 을 반복적으로 구하는 문제이다. 처음에는 삽입 정렬을 이용해서 처리하려 했으나 시간이 초과되어 우선순위 큐를 이용해야 한다는걸 뒤늦게 깨닳은 문제였다. 우선순위 큐는 평소 힙을 이용해서 구현하나, 최초에 삽입정렬로 구현하는 탓에 구현시간이 몇분 남지 않아 그당시 바로 떠올랐던 멀티셋을 이용해 구현했다. 구현은 너무나도 간단하다. (입력 함수를 나누고, 의미없는 개행을..
BOJ 1931번 회의실 배정 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 회의실에서 소화 가능한 회의의 개수의 최댓값을 묻는 문제이다. 회의 시간이 아닌 회의 개수 이므로 임의의 시점에서 회의실에 들어갈 수 있는 회의 중 가장 빨리 끝나는 회의를 탐욕적으로 선택하면 끝. 심지어 회의 번호를 기억할 필요도 없이 단순 횟수만 출력하면 되기 때문에 비교적 간단하게 구현할 수 있다. 위의 BOJ 예시를 그래프로 나타내면 아래와 같다. 이 그래프를 이용하여 설명을 진행한다. 몇 가지 규칙을 정하고 그 규칙 대로만 (=알고리즘) 이 문제를 해결하기로 한다. (규칙 A) 현재시간 커서 이후에 시작 예정인 회의 중 가장 빠르게 종료 예정인 회의를 회의실에 투입한다..
BOJ 1005번 ACM Craft 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 특정 건물의 선행 건물의 제한이 없으며, 후행 건물 또한 제한이 없기 때문에 단순 트리로는 해결이 불가능하다. 그래프를 이용해야 하며 그래프의 노드가 1000개, 간선이 100000개 이므로 완전 탐색을 한번 돌려도 시간은 충분하다. 즉 완전 탐색을 한번 돌면서 각 노드에 소요시간을 저장해 두기만 해도 해결 가능한 정석에 가까운 문제라는 생각이 들었다. 처음에는 단방향 그래프와 너비 우선 탐색을 이용해 구현하였으나, 이후 포스팅을 준비하면서 내 설명 능력에..
BOJ 5638번 수문 5638번: 수문 첫째 줄에 수문의 개수 n이 주어진다. (1 ≤ n ≤ 20) 다음 n개 줄에는 각 수문 Gi의 유량 (m3/hour) Fi와 피해 비용 Ci가 주어진다. 다음 줄에는 테스트 케이스의 수 m (1 ≤ m ≤ 50)이 주어진다. 다음 m개 www.acmicpc.net 각 수문의 유랑과 비용을 이용해, 조합 가능한 유량의 최소비용을 테이블에 저장하여 풀 수 있는 문제였다. 다만 약간의 함정이 2곳에 있었다. 수문의 정보가 다음과 같이 주어진다면, 배출 가능한 유량과 비용의 테이블을 만들 수 있다. 여기서 요구되는 배출 가능 유량이 4000이라면? 첫 번째 함정이라고 느낀 부분이다. 이 부분은 당연히 200 비용으로 처리되어야 하고, 실제 구현을 해보면 간단하게 처리할 수 있다. (cpp 1..
30살에 시작하는 게임 개발 28살의 약간은 늦은 나이에 첫 취직을 했다. 29살의 마지막 날에 퇴사를 했다. 회사를 다니는 동안 소프트웨어를 전공하고 배운 자신과, 하드웨어 회사인 우리 팀 사이에서 여러 가지 내적 갈등이 있었다. 처음에는 스스로와의 타협이 있었다, 연봉은 나에게 과분한 수준이었으니까. 몇 개월이 지나자 알고리즘 문제를 하드웨어 때문이라고 합리화하는 자신을 보게 되었다, 실제로 모든 데이터가 완벽하지는 못했으니까. 몇 개월이 지나, 친구들과 술 한잔 할 기회가 있었다. 그 자리에서 1년 만에 매너리즘에 빠져가던 스스로에게 놀라 메이저 IT 기업의 공채에 도전하기 시작했다. 코딩 테스트는 신분증이 제대로 인식되지 않았던 한 번을 제외하고는 문제가 없었다. 하지만 모두 면접에서 떨어졌다. 2점대 극초반의 형편없는 학점..

티스토리툴바