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

Algorithm143

[Tree] 길 찾기 게임 - 2019 KAKAO BLIND RECRUITMENT 필자의 풀이보다 더 괜찮아보이는 코드를 발견해서 이를 공유하고 설명해보겠다. 해결 방법1 처음은 nodeinfo를 x좌표를 오름차순으로 정렬한다. 그리고 아래의 2가지 규칙을 기반으로 재귀 방식으로 트리를 만들어나가는 방법이다. 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다. 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다. 트리를 만들기 위한 첫 단계는 전체 트리의 루트 노드를 찾는 것으로, 루트 노드는 y 좌표가 최댓값인 노드이다. nodeinfo는 x좌표를 기준으로 정렬되어 있기 때문에 nodeinfo에서 루트 노드를 기준으로 왼쪽 요소들의 x좌표는 모두 루트 노드의 x좌표보다 작.. 2022. 6. 19.
[String] 매칭 점수 - 2019 KAKAO BLIND RECRUITMENT 해결 방법 이 문제는 특별한 알고리즘을 요구하지는 않고, 문자열 파싱과 구현만 잘 해준다면 해결할 수 있다. 웹 페이지의 url은 meta 태그의 content 속성에 있다는 사실, 외부 링크는 a 태그의 href 속성에 있다는 사실, 그리고 단어는 알파벳을 제외한 다른 모든 문자로 구분한다는 사실을 잊지 말도록 하자. 구현 방식은 문제 설명에서 자세히 나와있으므로 이제 틀리기 쉬운 테스트케이스를 짚어보겠다. - 링크점수 또는 매칭점수를 float형으로 두고 계산하면 테스트케이스 8번에서 막히기 쉽다. 정밀도(유효자릿수)가 더 높은 double형을 사용하자. float의 유효자릿수는 7이고, double의 유효자릿수는 15이다. - 웹 페이지의 url을 추출하기 위해 "content="를 기준으로 찾는 .. 2022. 6. 7.
[시뮬레이션] 프렌즈4블록 - 2018 KAKAO BLIND RECRUITMENT 해결 방법 필자는 아래 이미지처럼 2차원 벡터를 이용하여 아래 블록부터 각 열 벡터에 저장했다. 아래 블록부터 저장하면 블록을 삭제하는 과정이 편리하기 때문이다. 또, 블록의 삭제는 화살표의 역방향으로 진행하는게 편리하다. 보드를 탐색해나가며 같은 종류의 2x2 블록들을 찾아서 boolean 2차원 배열에 삭제할 블록들을 표시해두고, 나중에 일괄적으로 삭제하는 방법을 이용하면 삭제할 수 있는 블록이 겹치더라도 연산이 간단해진다. 삭제할 수 있는 블록이 겹칠 수 있으므로 같은 종류의 2x2를 발견하자마자 지우는 것은 절대 안된다. 주기마다 삭제한 블록의 개수를 누적시켜주면 문제는 해결된다. 소스코드 #include #include #include using namespace std; vector vboar.. 2022. 6. 5.
[n진수] n진수 게임 - 2018 KAKAO BLIND RECRUITMENT 해결 방법 10진수 i를 n진수로 변환한 값을 문자열 형태로 반환하는 converter함수를 만들어 두었다. 16진수 이하의 변환은 16진수 기준으로 변환해도 모두 적용되므로, 2진수든 8진수든 모두 16진수 변환 방법을 써도 된다. 0부터 n진수로 변환한 값들을 임의의 문자열에 계속 추가해두면 되는데, 최종 문자열의 길이는 t*m이면 충분하다. 이제 이 문자열을 참고하여 튜브 차례에 해당하는 문자들을 추출하면 문제가 해결된다. 소스코드 #include #include using namespace std; char hexa[17] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}; string converter(int n, int i.. 2022. 5. 31.
[그리디] 셔틀버스 - 2018 KAKAO BLIND RECRUITMENT 해결 방법 이 문제의 핵심은 막차의 만원 여부이다. i) n, t를 이용하여 버스의 timetable을 만든다. ii) 크루의 timetable을 정렬한다. iii) 버스의 timetable과 크루의 timetable을 차례대로 비교해가며 탑승할 수 있는 크루를 먼저 온 순서대로 태운다. 단, 막차는 몇 명이 타는지 카운트해야 한다. iv) 막차가 만원이 아니라면, 즉, 카운트한 값이 m과 다르다면 콘은 그대로 막차를 타고가면 된다. v) 막차가 만원이라면, 즉, 카운트한 값이 m과 일치하다면 콘은 막차에서 가장 늦게 탄(우선순위가 가장 낮은)사람의 도착시간보다 1초 일찍 오면 된다. 소스 코드 #include #include #include using namespace std; string time_c.. 2022. 5. 28.
[집합] 뉴스 클러스터링 - 2018 KAKAO BLIND RECRUITMENT 해결 방법 i) str1, str2에 있는 대문자를 모두 소문자로 전환한다. ii) str1, str2에 대하여 각각 연속된 두 영문자씩 쪼개어 벡터에 넣어준다. iii) 두 벡터의 크기가 모두 0인 경우와 두 벡터 중 하나의 크기가 0인 경우를 반영한다. iv) 두 벡터의 교집합 요소를 찾는다. 값이 같은 요소가 있기 때문에 방문 배열을 활용한다. v) 합집합 요소의 개수를 찾는다. 합집합 요소는 두 벡터의 크기의 합에서 교집합 요소의 개수를 뺀 값이다. -> n(A∪B)=n(A)+n(B)-n(A∩B) 소스 코드 #include #include using namespace std; vector s1; vector s2; int inter; // 교집합 요소의 개수 bool check[1001]; //s.. 2022. 5. 24.
[Linked List] 표 편집 - 2021 카카오 채용연계형 인턴십 해결 방법 이 문제는 연결리스트를 이용하여 풀 수 있다. 굳이 포인터를 사용하지 않고도 배열을 이용하여 연결리스트를 구현할 수도 있다. 또, 'Z' 명령은 최근에 삭제했던 행을 복구하는 명령이므로 Stack이 필요하다. 주의할 점이 있다면, 맨 앞에 있는 요소는 앞 노드로 연결하는 링크가 없고, 맨 뒤에 있는 요소는 뒷 노드로 연결하는 링크가 없음을 고려해야 한다. 그리고 'U', 'D' 명령의 경우에는 이동할 칸 수를 나타내는 정수가 나오는데, 이 정수는 한 자리 숫자가 아닐 수도 있기 때문에 모든 자리 수를 추출해야 한다. 노드를 삭제하는 경우에는 기존 노드의 앞, 뒤 노드를 서로 이어주면 되고, 노드를 복구하는 경우에는 제거되었던 노드의 앞, 뒤 노드를 해당 노드로 이어주면 된다. 소스 코드 아래 .. 2022. 5. 22.
[BFS] 거리두기 확인하기 - 2021 카카오 채용연계형 인턴십 해결 방법 맨해튼 거리의 개념을 모르더라도 단순히 BFS 알고리즘으로 해결할 수 있다. 자신을 제외한 응시자들 중에서 BFS 거리가 2이하인 응시자가 있다면 거리두기를 준수하지 않은 것으로 판단하면 된다. 주의할 점이 있다면 이 문제는 테스트케이스 5개가 있기 때문에 queue와 방문 배열을 초기화하는 작업이 필요하다. 그리고 연산 횟수를 줄이기 위해 거리두기 준수 여부를 나타내는 변수를 활용하여 거리 두기를 준수하지 않다는 사실이 확정났다면 해당 케이스에 대해서는 추가적인 연산을 수행하지 않도록 했다. 또, BFS 깊이가 3을 넘어가는 경우에는 queue에 구조체를 넣지 않았다. 소스 코드 #include #include #include #include using namespace std; struct.. 2022. 5. 17.
[시뮬레이션] 수식 최대화 - 2020 카카오 인턴십 해결 방법 (i) 문자열을 파싱하여 정수 부분과 연산자 부분을 따로 추출하여 벡터에 저장한다. (ii) 우선 순위를 배정한다. 우선순위에 대한 경우의 수는 6이기 때문에 6가지 경우만 시뮬레이션 하면 된다. (iii) 남아 있는 연산자들 중 가장 우선 순위가 높은 연산자를 찾아서, 해당 연산자에 대한 연산을 수행한다. (iv) 연산 결과는 합쳐서 정수 벡터에 반영하고, 사용한 연산자는 연산자 벡터에서 제거하고, 남은 해당 연산자 카운트를 1 감소시킨다. 이렇게 하면 연산마다 정수 벡터와 연산자 벡터의 크기는 각각 1씩 줄어들 것이고, 모든 연산을 수행했을 때는 정수 결과값 하나만 남게 된다. (v) 모든 경우에 대한 정수 결과값들의 최댓값을 구한다. 소스 코드 #include #include #inclu.. 2022. 5. 14.

티스토리툴바