▼ Why ? 이제 해시함수를 이용하여 해결하는 문제를 기초적인 단계부터 풀어보려고 한다. ▼ 학급 회장 문제 정보 학급 회장을 뽑는데 후보로 기호 A, B, C, D, E 후보가 등록을 했습니다. 투표용지에는 반 학생들이 자기가 선택한 후보의 기호(알파벳)가 쓰여져 있으며 선생님은 그 기호를 발표하고 있습니다. 매개변수 s에 투표용지에 쓰여져 있던 각 후보의 기호가 선생님이 발표한 순서대로 문자열로 주어지면 어떤 기호의 후보가 학급 회장이 되었는지 반환하는 프로그램을 작성하세요. 반드시 한 명의 학급회장이 선출되도록 투표결과가 나왔다고 가정합니다. 제한사항 문자열 s의 길이는 100을 넘지 않습니다. 입출력 예 어떻게 해결해야 할까? 기호 A, B, C, D, E를 키(key)로 받고 투표 횟수를 값(..
▼ Why ? 해시 테이블을 이용하여 해결하는 알고리즘 문제를 풀기 전에, 해시 테이블이 무엇인지와 해시 함수를 통해 발생하는 충돌을 해결하는 방법에 대해 공부해보려고 한다 ▼ 해시 테이블 Hash Table ? 해시함수(Hash function)를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 삼아 데이터의 값(value)을 키(key)와 함께 저장하는 자료구조를 "Hash table" 이라고 한다 이때 데이터가 저장되는 곳을 버킷(bucket) 혹은 슬롯(slot)이라고 한다 Hash Table의 시간 복잡도 해시테이블의 탐색, 삽입, 삭제의 시간복잡도는 평균적으로 O(1)이다 충돌이 빈번하게 일어나면 최악의 경우엔 O(n)의 시간복잡도로 수렴 ➜ 실무에선 적재율(Load fact..
▼ Why ? 이번 문제도 구현 - 시뮬레이션 유형의 문제로, 문제가 주어준 상황에 맞게 올바른 결과값을 출력하도록 구현해내면 된다. 하지만 지금까지 풀었던 구현 유형의 문제들은 하나의 개체만을 생각했지만, 이 문제 [키패드]는 두 개의 개체(왼손, 오른손)를 신경 써야 하기 때문에 소스 코드로 구현하는데 좀 더 까다로울 것 같아 해결해보려고 한다. ▼ 키패드 문제 정보 스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다. 이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다. 맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다. 엄지손가락은 상하좌우 4가지 방향으로만 이동할..
▼ Why ? 이번 문제도 구현 - 시뮬레이션 유형의 문제이고, 격자 밖으로 나가는 경우만 고려하면 됐던 이전 문제들과 달리 장애물이 추가되었기 때문에 구현할 때 고려해야 할 부분이 좀 더 추가된 문제이기에 한 번 풀어보려고 한다. ▼ 공원 산책 문제 정보 지나다니는 길을 'O', 장애물을 'X'로 나타낸 직사각형 격자 모양의 공원에서 로봇 강아지가 산책을 하려합니다. 산책은 로봇 강아지에 미리 입력된 명령에 따라 진행하며, 명령은 다음과 같은 형식으로 주어집니다. ["방향 거리", "방향 거리" … ] 예를 들어 "E 5"는 로봇 강아지가 현재 위치에서 동쪽으로 5칸 이동했다는 의미입니다. 로봇 강아지는 명령을 수행하기 전에 다음 두 가지를 먼저 확인합니다. 주어진 방향으로 이동할 때 공원을 벗어나는지..
▼ Why ? 이번 문제도 구현 - 시뮬레이션 문제이고, 이전에 풀었던 문제 [청소 로봇]처럼 개체를 직접 이동시키는 상황을 구현해내는 유형이다. 주어진 상황에 맞게 알고리즘을 구현해내는 능력을 키우기 위해 계속해서 관련 문제를 풀어보려고 한다. ▼ [로봇의 이동] 문제 정보 이차원 배열 격자판 0행 0열에 로봇이 3시 방향을 보고 있습니다. 로봇은 다음 규칙에 따라 이동합니다. 'G' 명령을 주면 보고 있는 방향으로 한 칸 이동합니다. 격자 밖으로 나가는 명령은 하지 않습니다. 'R' 명령을 주면 오른쪽으로 90도 회전합니다. 'L' 명령을 주면 왼쪽으로 90도 회전합니다. 매개변수 moves에 로봇에 명령을 내린 문자들이 차례대로 나열된 명령 문자열이 주어지면 이 명령 문자열을 로봇이 모두 수행했을 ..
▼ Why ? 이전 문제 [안전지대]와 같은 구현 - 시뮬레이션 문제이고, 이번 문제는 이전 문제와 달리 실제로 개체를 움직이는 상황이 주어져 그 개체의 위치를 파악해야 한다는 점 때문에 풀어보았다. ▼ 청소 로봇 문제 정보 n*n 크기의 이차원 배열 격자판 0행 0열이 청소 로봇의 시작위치입니다. 청소 로봇은 다음 규칙에 따라 이동합니다. 'U' 명령은 로봇이 위쪽으로 한 칸 이동합니다. 'R' 명령은 로봇이 오른쪽으로 한 칸 이동합니다. 'L' 명령은 로봇이 왼쪽으로 한 칸 이동합니다. 'D' 명령은 로봇이 아래쪽으로 한 칸 이동합니다. 만약 로봇이 명령을 수행할 경우 격자판 밖으로 나가는 경우라면 로봇은 해당 명령을 수행 하지 않고 무시합니다. 매개변수 n에 격자판 크기가 주어지고, moves에 청..
