CodeLog

Code Log에 무려 마지막 글을 쓴 지 3년만에 돌아왔다. 알고리즘 공부와 코딩테스트 관련 글을 정리하던 대학생 코드에이블은 원하는 회사에 합격해서 지금은 웹 개발자로 성장중이다. 바쁜 업무에 적응하느라 잠시(잠시라고 하기에는 꽤나 긴 시간동안) 접어두었던 블로그 포스팅을 다시 시작했다. 현재 회사와 업무에 매우 만족중이지만- 개발자로서 계속 성장하고 도전하고자 알고리즘과 코딩테스트를 다시 공부해보겠다는 계획을 세웠기 때문이다. 현직자지만 코딩테스트는 기초부터 탄탄하게 다시 해볼 생각이기 때문에 프로그래밍 공부 방법이 궁금한 개발자 꿈나무 분들도 참고하면 좋을 것 같다. 너무 오랜만에 들어왔는데 생각보다 그동안 많은 분들이 찾아주셔서 다시 열심히 적어봐야 겠다는 의욕이 생겼다 -!(감사합니다-) 1...

백준 알고리즘 문제 원본 보기 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝..

백준 알고리즘 문제 원본 보기 문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 입력 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) 출력 강의실의 개수를 출력하라. 예제 예제 입력 1 예제 출력 1 3 1 3 2 4 3 5 2 아이디어 우선 가장 적은 강의실을 사용하여 수업을 배치..

백준 알고리즘 문제 원본 보기 문제 병든 나이트가 N × M 크기 체스판의 가장 왼쪽 아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다. 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다. 체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자. 입력 첫째 줄에 체스판의 세로 길이 N와 ..

백준 알고리즘 문제 원본 보기 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어 한다. 미르코를 도와 그가 만들고 싶어 하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라. 예제 예제 입력 1 예제 출력 1 30 20 예제 입력 2 예제 출력 2 102 210 예제 입력3 예제 출력3 2931 -1 예제 입력4 예제 출력4 80875542 88755420 아이디어 어..

백준 알고리즘 문제 원본 보기 문제 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.) 백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다. 여러분은 여학생의 수 N, 남학생의 수 M, 인턴쉽에 참여해야 하는 인원 K가 주어질 때 만들 수 있는 최대의 팀 수를 구하면 된다. 입력 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ ..

저번 포스팅 #1 에서 언급했듯이 이번 포스팅은 알고리즘 유형 학습 중 첫 번째 알고리즘인 '그리디 알고리즘(Greedy Algorithm)'의 개념과 문제를 풀기 전 알아야 하는 사전 지식에 대하여 작성해보려 한다. 1. 그리디 알고리즘(탐욕법, 탐욕 알고리즘) 그리디 알고리즘은 Greedy(탐욕, 욕심쟁이)라는 이름처럼 지금 당장 최적인 답을 선택하는 과정을 반복하여 결과를 도출하는 알고리즘이다. 그리디 알고리즘은 말 그대로 각 단계에서 미래를 생각하지 않고, 그 순간 가장 최선의 선택을 하는 기법이기 때문에 종합적인 결과에 대해서는 최적의 해를 보장할 수 없다. (지역적(local)으로는 최적의 선택이지만 이를 반복하더라도 전체적(global)으로는 최적의 해가 아닐 수 있음) 2. 그리디 알고리즘..

대학교 마지막 학기를 남기고 나의 대학 버킷리스트 중 하나인 알고리즘 공부를 시작했다. 학교를 다니며 C언어, C++, Java, Python 등 다양한 언어와 자료구조를 공부했지만 '알고리즘'을 공부하는 것은 이번이 거의 처음이라고 할 수 있다. 알고리즘이 무엇인지는 대학교 3학년 ICPC라는 국제 대학생 프로그래밍 대회를 나가면서 알게 되었다. 사실 나는 프로그래밍 대회가 기본적인 프로그래밍 언어 활용 능력을 가지고 문제를 해결하는 대회인 줄 알았기에 ICPC 예선에서 풀 수 있는 문제가 많지 않았다. 프로그래밍 대회나 코딩테스트를 위해서는 프로그래밍 언어뿐만이 아닌 알고리즘에 대한 공부가 필요하다. 얼마 남지 않은 대학 생활이 끝나기 전 알고리즘 공부를 진행하고 학습 내용을 기록하고자 블로그 포스팅..