자료구조 학습의 시작 안녕하세요. 보통 프로그래밍 언어를 1~2개 익히시고, 조금 다뤄본 뒤에 '다음엔 뭐 공부해야 하지?'라고 하면 나오는 게 아마 대부분 자료구조 및 알고리즘일 것입니다. 자료구조 및 알고리즘은 괜찮은 기업들의 코딩 테스트를 위해서 필수적으로 익히셔야 할 내용입니다. 굳이 취업이 아니더라도, 프로그래머를 평생 직업으로 삼고자 한다면, 언젠가 반드시 알아야 할 사항이니 이번 기회에 꼭 익히시길 바랍니다. 사람에 따라 다르긴 하겠지만, 저 같은 경우에는 프로그래밍 언어를 익히고 충분히 활용해보지 않았는데 자료구조 및 알고리즘을 배울 때 조금 어렵긴 했으나, 그나마 정리된 개념들을 쉽게 다루고자 노력하려고 합니다. 참고로, 이 글에서는 자료구조의 깊은 부분은 제외하고 필수적으로 알아야 할 ..
소개 정렬 알고리즘 중 대표적인 알고리즘인 퀵 정렬을 소개하고자 한다. 퀵 정렬을 소개하기에 앞서, 대표적인 알고리즘들의 시간/공간 복잡도 표를 확인하면 다음과 같다. 평균 최악 메모리 버블 정렬 n^2 n^2 1 선택 정렬 n^2 n^2 1 삽입 정렬 n^2 n^2 1 퀵 정렬 n log n n^2 n log n 병합 정렬 n log n n log n n 힙 정렬 n log n n log n 1 퀵 정렬은 이름 그대로 '빠른 알고리즘'이라는 의미인데, 실제로 위 알고리즘들 중에서는 일반적으로 가장 빠른 알고리즘이라고 한다. 여기서 약간 의아할 수 있는 부분이 '병합, 힙 정렬이 최악의 경우에 퀵 정렬보다 시간 복잡도가 높은데, 어떻게 가장 빠른 알고리즘이지?'라는 생각이 들 수 있는데, 그 이유는 다음..
지문 H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요. 제한사항 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다. 논문별 인용 횟수는 0회 이상 10,000회 이하입니다. 입출력 예 citationsreturn ..
지문 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 입출력 예 numbersreturn [6, 10..
지문 카카오톡에 뜬 네 번째 별! 심심할 땐? 카카오톡 게임별~ 카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다. 갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다. 다트 게임은 총 3번의 기회로 구성된다. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수1 , 점수2 , 점수3 )으로 계산된다. 옵션으로 스타상(*) , 아차상(#)이 ..
지문 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도의 각 가로줄에..