본문 바로가기

Algorithm/programmers42

2020 Kakao internship 67259 - 경주로 건설(다익스트라, 0-1 bfs) c++ - N by N의 벽이 중간중간 존재하는 경주로에서 상하좌우로 도로가 놓이는데 N, N까지 도달할 수 있는 최소비용의 도로를 놓아야된다. - 출발지와 도착지가 정해져있는 구간의 최소비용을 구하는 로직으로는 다익스트라 알고리즘이 있어서 바로 그 알고리즘으로 접근하였다. (개인적으로 하는 알고리즘 스터디에서 어떤 분이 0-1 bfs 라는 로직을 사용한 것을 보았는데 이를 이용하면 O(V + E)복잡도로 풀 수 있다. 다익스트라는 우선순위큐를 이용할 시에 O((V+E)logV)이다. - 주의할 점으로는 코너가 발생할시 건설비용이 100이 아니라 600이 되는데, 그 것을 모든 칸의 건설비용을 계산 할 때 이전에 있었던 칸의 방향정보를 가져와서 지금 방향과 비교해서 수평이면 100, 수직이면 600으로 계산하는.. 2021. 9. 6.
2020 Kakao internship 67258 - 보석 쇼핑(슬라이딩 윈도우) c++ - 특정 범위의 보석을 모두 챙기는데 모든 종류의 보석을 챙기는 가장 짧은 범위를 찾는 문제이다. - 문제에서 보석 배열 길이가 10만이므로 10만^2 = 100억이므로 nlogn 이하 로직을 사용해야한다. 그렇기 때문에 어떤 범위가 이동하면서 그 범위 안의 구간합 등이 조건에 성립하는지를 O(N)으로 구할 수 있는 슬라이딩 윈도우 방식으로 접근하였다. - 전체 보석 종류 갯수를 구한다. 그 종류 갯수는 어떤 범위가 모든 보석종류를 모두 포함하는 최소길이의 범위가 될 것이다. 인덱스 0부터 모든 보석종류를 포함하는지를 map을 통해서 체크한다. map을 사용하는 이유는 2개 이상의 같은 종류보석이 들어있을 수 있기 때문이다. 모든 종류 보석이 있는 범위가 구해지면 거기서 1칸씩 전진하면서 전진하는 방향 .. 2021. 9. 6.
2020 Kakao internship 67257 - 수식 최대화(파싱, 완전탐색, 배열) c++ 풀이 - 연산자 혹은 괄호 문제만 나오면 스택으로 풀 생각만 했는데, 그렇게 안 풀어도 되는 문제였다. - 모든 연산자 우선순위 조합에 대해서 최대값을 구하는데 vector erase연산으로 계산된 피연산자를 벡터에서 제거해나가는 방식으로 풀었다. - 연산자랑 피연산자를 따로 분리했는데 strtok을 사용했다. strtok은 여러개의 delimiter에 대해서 분리가 되도록 짤 수 있어서 stringstream과 함께 자주 사용한다. 개인적으로 분리자 단위가 공백문자면 stringstream을 주로 사용하고 여러개이면 strtok을 자주 사용한다. #include #include #include #include using namespace std; vector order{'+', '-', '*'}; // 연산.. 2021. 9. 6.
2020 Kakao internship 67256 - 키패드 누르기(배열, 구현) c++ 풀이 -단순 구현이다. 각 버튼마다 좌표값을 구해서 배열에 저장한뒤 그 좌표값으로 손가락과의 거리를 계속 구하는 식으로 빠르게 구현했다. #include #include #include using namespace std; // 147 왼쪽 369오른쪽 2580 가까운 손가락 or hand string solution(vector numbers, string hand) { // numbers 1000 string answer = ""; vector fingerPos(2); // L, R 위치 vector board(13); // 번호별 좌표 fingerPos[0] = {3,0}, fingerPos[1] = {3,2}; // *, # board[0] = {3, 1}; for(int i = 1; i len2) {.. 2021. 9. 6.

티스토리툴바