본문 바로가기
  • 실행력이 모든걸 결정한다
반응형

Algorithm143

Hash 고득점 kit 풀이 완료, 후기 Programmers 의 Hash 고득점 kit를 모두 풀이 하여 포스팅 해보았다. Hash 함수의 정의는 입력 메시지를 고정된 길이의 출력값으로 압축 시키는 함수이다. (출처-국방과학기술용어사전) 포스팅한 Hash 문제들의 소스코드를 봤듯이, 입력된 문자열을 간단한 정수 출력값으로 변환 시켰다. 정렬같은 경우처럼 문자열들에 대한 계산이 필요할 때, 문자열을 계산할 때마다 각 문자들까지 처리해주는 것보단, 사전에 이 문자열을 나타내는 값 하나로 압축해두는 것이, 이후 계산 시 시간복잡도를 줄이는데에 매우 효과적인 것을 느꼈다. 해시를 이용할 때 주의할 점이 있다. 서로 다른 문자열인데도 해시값이 같을 때, 심각한 리스크가 생길 수 있다. 이를 방지하기 위해서 해시값이 같을 때에는 직접 두 입력값을 2차적.. 2020. 9. 8.
[Hash, 난이도 중상] 프로그래머즈, 베스트앨범 이 문제에서는 문자열을 해쉬 값으로 바꿀 수 있어야 하고, 3중 정렬을 해야 한다. 정렬이 조금 까다로운 점 외에는 특별한 수학적 논리력은 요구되지 않는다. 아마 여러 요소를 가지는 벡터의 정렬에 익숙하다면 이 문제는 간단히 풀 수 있을 것이다. main문 위에 있는 compare, compare2 에 대해서 설명 하겠다. 둘다 비교함수이다. compare 같은 장르끼리는 벡터 안에서 서로 인접하게 한다. (장르 구별은 해시값으로 한다.) 같은 장르 안에서는 앨범이 조회수가 높은 순으로 정렬 시킨다. 조회수가 같다면 고유번호가 낮은 순으로 정렬 시킨다. 이렇게 3중 정렬만 해줘도 나중에 처리가 쉬워진다. compare2 장르의 총 조회수가 높은 순으로 정렬 시킨다. 이렇게 2중 정렬을 해주면 장르의 총 .. 2020. 9. 8.
[Hash, 난이도 중] 프로그래머즈, 위장 이 문제는 해쉬를 이용할 수 있어야 하며, 수학적이면서 논리적인 접근이 약간 필요하다. 2차원 문자열 벡터 clothes에서 각 행은 [의상의 이름, 의상의 종류]가 들어있는데 우리는 의상의 이름에는 관심을 가지지 않고, 종류별로 의상이 몇개있는지만 알아내면 간단한 수식을 통해 문제를 해결할 수 있다. 만약 스파이가 아래와 같은 의상들을 가지고 있다고 가정해보자. 같은 종류 안에서도 서로 다른 이름을 가지고 있다. 안경 - 2개 마스크 - 1개 코트 - 3개 바지 - 1개 여기서 스파이는 하나 이상의 의상을 입고 있어야 하며, 매번 의상을 한 부위라도 다르게 입고 있어야 한다. 충격적이게도, 스파이는 안경만 끼고 옷을 홀딱 다 벗고 있어도 된다는 것이다. 이정도 또라이면 스파이인걸 눈치 못채는게 이상하다.. 2020. 9. 7.
Programmers 스킬 체크 레벨3 합격! 보통의 기업 코딩 테스트를 진행하기에 무리가 없다고 하니, 높은 수준의 문제를 내는 기업 코딩 테스트를 진행하기에도 무리가 없을 실력으로 올려야겠다. 2020. 9. 4.
[Hash, 난이도 중] 프로그래머즈, 전화번호 목록 전화번호부에 적힌 전화번호를 담은 배열 phone_book이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성하는 문제이다. 여기서 제한 사항을 보면 phone_book의 길이는 1 이상 1,000,000 이하이고 각 전화번호의 길이는 1 이상 20 이하이다. phone_book의 길이를 N, 전화번호의 최대 길이를 E이라고 하자. 해쉬를 안쓰고 전화번호 자리수까지 일일이 매칭한다면 시간 복잡도는 O(N^2*E) 까지도 나올 것이다. 아무리 해쉬를 쓴다고 해도, 접두어의 여부를 확인하기 위해 전화번호들을 모두 하나씩 매칭하는 방법을 쓰려면 시간 복잡도가 O(N^2) 이 나오므.. 2020. 9. 3.
Programmers 코딩테스트 고득점 Kit 포스팅 예정 코딩테스트 고득점 Kit에는 여러 알고리즘별로 2~6문제 씩 총 36문제가 있다. 코딩테스트에 자주 나오고 사람들이 많이 틀리는 유형으로 간추린, 퀄리티와 난이도를 겸비한 문제들이라고 한다. 이 문제들을 모두 직접 풀어본 후 개인적 난이도를 평가하고, 풀이법과 소스코드와 함께 포스팅할 것이다. SQL 고득점 Kit도 데이터베이스 카테고리에 포스팅할 계획이다. 2020. 9. 3.
[Hash, 난이도 중하] 프로그래머즈, 완주하지 못한 선수 참가자, 완주자들의 명단이 모두 주어졌을 때, 완주하지 못한 선수를 출력하는 문제이다. 완주자 = 참가자 - 1 이다. 즉 완주하지 못한 선수는 항상 1명이라는 것이다. 왼쪽 열부터 참가자, 완주자, 리턴값(완주하지 못한 선수) 이다. [leo, kiki, eden] [eden, kiki] leo [marina, josipa, nikola, vinko, filipa] [josipa, filipa, marina, nikola] vinko [mislav, stanko, mislav, ana] [stanko, ana, mislav] mislav 이 문제의 취지에 맞게, 해시값을 이용하여 문자열 매칭을 하였다. 해시를 이용하여 풀었더니 정확성 만점, 효율성 만점을 받았다. 그런데 이 문제를 푼 후, 다른사람들이.. 2020. 9. 2.
[동적계획법, 난이도 중] 백준 9251번 LCS 두 수열의 부분수열을 찾는 문제이므로 2차원 DP방식을 이용하였다. 예제 입력 1에서 주어진 입력은 ACAYKP CAPCAK 이다. 동적계획법을 이용하여 길이가 작은 문자열~긴 문자열들 순으로 수행해나가면 된다. 맨 처음, 2번째 문자열에서 길이가 1인 "C"를 1번째 문자열과 비교해 나갈 것이다. A 와 C -> 0 AC 와 C -> 1 ACA 와 C -> 1 ACAY 와 C -> 1 ACAYK 와 C -> 1 ACAYKP 와 C -> 1 그 다음, 2번째 문자열에서 길이가 2인 "CA"를 1번째 문자열과 비교해 나갈 것이다. A 와 CA -> 1 AC 와 CA -> 1 ACA 와 CA -> 2 ACAY 와 CA -> 2 ACAYK 와 CA -> 2 ACAYKP 와 CA -> 2 이 순서로 수행해 나간.. 2020. 9. 1.
[동적계획법, 난이도 중] 백준 1699번 제곱수의 합 n을 제곱수들의 합으로 나타낼 수 있는 경우가 여러개 있을 때, 가장 적은 제곱수들을 가지는 경우를 찾으면 된다. 정수 i보다 낮은 정수 j에 제곱수 하나를 더하여 i를 만들 수 있을 때, j값으로는 i-1^2, i-2^2, i-3^2.. 등이 올 수 있다. 각 j값들을 제곱수들의 합으로 표현할 수 있을 때, 이 제곱수 항의 각 최소 개수들의 최솟값에, 특정 제곱수를 의미하는 1을 더하면 이 문제의 답이 나온다. 여기서 특정 제곱수란 j에 어떤 제곱수를 더하여 i를 만드는 그 '어떤 제곱수'를 말한다. 예를 들어서 14를 만들고자 할때 14보다 낮은 정수에 제곱수를 하나 더하여 14를 만들 수 있는 경우는 13+1^2, 10+2^2, 5+3^2 이렇게 3가지 경우가 있다. 14를 제곱수의 합으로 표현 할.. 2020. 8. 31.

티스토리툴바