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

Algorithm/Hash(Table)5

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.
[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.
[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.

티스토리툴바