시간제한 메모리제한 정답 비율 1 초 12 MB 39.455% 문제 N×N의 표에 수 N^2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. 아래와 같이 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다. 12 7 9 15 5 13 8 11 19 6 21 10 26 31 16 48 14 28 35 25 52 20 32 41 49 입력 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. 출력 첫째 줄에 N번째 큰 수를 출력한다. 예제 입력 5 12 7 9 15 5 1..

우리는 컴퓨터로 알파벳을 유용하게 표현하기 위해 extended ASCII code 를 이용해 8bit (1byte)에 저장해 사용한다. 예를 들어 문자 'A'는 ASCII code로 '65'이고, binary code로 나타내면 '01000001'이다. 이를 표로 나타낸 이미지를 아래에 가져와보았다. 만약에 우리가 "BCCABBDDAECCBBAEDDCC"라는 20개의 문자를 별도의 압축 과정없이 전 컴퓨터에게 전송한다 생각해보자. 한 문자는 8bit이므로, 이 문자들은 총 160bits를 사용한다. 이 문자중에는 반복해서 등장하는 알파벳이 존재하기 때문에, 반복하는 각각의 문자를 'Encoding'하여 binary code를 압축시키면 8bit전체를 사용할 필요가 없다. 앞 문장에선 5가지의 알파벳이 ..

정리안된 블로그라 부끄럽지만 첫 개발 대외활동 지원이라 그 후기를 남겨본다. 작년엔 졸업 작품을 만들고 졸업전시위원회에 참여하게 되서 개발을 공부할 시간이 없었지만 완전히 전향하기로 마음먹은 지금부터 각잡고 개발을 공부하고 여러 프로젝트를 해보고자 멋사에 지원했다. 일단 서류는 합격했다. 나는 프론트엔드로 지원했고, 인스타그램을 살펴보니 프론트엔드 > 백엔드 > 기획/디자인 순으로 경쟁률이 높았다고 한다. 서류는 붙었으니 다음으로 남은 관문은 면접인데, 지인분께 수소문한 결과는 해커톤과 스터디 모든 활동에서 팀 플레이가 강조되다보니 그에 맞춰 답변을 예상하면 될것이라고 한다. 어떻게 서류에 붙어서 감사할 따름.. 멋쟁이 사자처럼 대학을 위해 준비했던 서류의 질문은 아래와 같다. 1. 다양한 IT동아리 중..

시간제한 메모리제한 알고리즘 분류 2 초 128 MB 수학 문제 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다 입력 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다. 출력 입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다. 예제 입력 13 예제 출력 3 처음 시도한 코드 (런타임 에러 및 틀렸습니다!)..

유클리드 호제법 학교에서 수학을 배울 때 정수 단원에서 잠깐 소개되었었던 그 이론을 다시 알아보고, 백준 문제와 함께 천천히 익혀보자. 두 개의 양수 a와 b의 최대공약수를 구하려면 "a와 b를 소인수분해"하면 된다. 이 때 손으로 하나하나 인수분해하며 푸는 방법도 있지만, 사람이 계산할 수 없을 만큼 매우 큰 두 수의 최대 공약수를 구해야한다면 컴퓨터를 이용해야한다. 이를 위해 PS에선 "유클리드 호제법"을 사용한다. 유클리드 호제법에 대한 이론적인 설명은 다음과 같다. (출처: 수학독본, 한길사) 두 양수 a, b가 있고 a>=b일때, a를 b로 나눈 몫을 q, 나머지를 r이라고 하자. a = b*q+r 00이라면 위 식에서 r = a - b*q 이고, a와 b의 임의의 공약수 e가 있다고 할 때 우..

아래 링크 강의를 수강하고 정리하였습니다. 기초 학습 단계로 부정확한 정보가 있을 수 있습니다. https://youtu.be/yWWbLrV4PZ8 / 나동빈님의 실전 알고리즘 강좌 34강 https://www.youtube.com/watch?v=UcjK_k5PLHI / 코드없는프로그래밍님의 String 강좌 https://youtu.be/GTJr8OvyEVQ / Tushar Roy - KMP Pattern matching 문자열 매칭 알고리즘이란, 특정한 글이 있을 때 그 글안에서 주어진 문자열을 찾는 알고리즘이다. 이전까지 문자열을 찾는 경우에는 브루트포스처럼 O(nm)의 시간을 소요해 문자열을 찾았었다. 이 과정에 KMP 문자열 매칭 알고리즘, 라빈-카프 문자열 매칭 알고리즘을 도입해 매칭에 소요하..