카카오 인턴십4 [2020 카카오 인턴십] 경주로 건설 문제: https://programmers.co.kr/learn/courses/30/lessons/67259 https://codingjuny.tistory.com/41 위 출처를 참고하여 "비용"으로 BFS를 돌려야한다는 아이디어를 얻었습니다. 경주로를 설치하면서 식별할 수 있는 정보는 3가지입니다. 그래서 저는 상태공간을 VISITED[DIR][N][N] 으로 선언하였습니다. VISITED[DIR][N][N] 정의: DIR 방향으로 N,N좌표에 도로를 놓는 최소 비용 방향, Y좌표, X좌표 (방향 정보가 있기 때문에 Y,X, 좌표 하나만 가지고 움직여도 경주로를 표현할 수 있습니다.) 도로를 설치하면서 모든 방향을 탐색해봐야 합니다. (단, 현재 진행하던 방향과 반대방향은 무한 루프에 빠지게 되니 그.. 2020. 8. 4. [2020 카카오 인턴십] 보석 쇼핑 문제: https://programmers.co.kr/learn/courses/30/lessons/67258 투 포인터로 해결할 수 있는 문제입니다. 핵심은 N제한이 10만이므로 선형 탐색 한 번으로 탐색을 끝내야 한다는 점입니다. 문제를 해결하는 아이디어는 다음과 같습니다. 1. left, right를 선언해 현재 내가 구매할 보석의 하한 위치, 상한 위치 저장 2. 매 루프를 돌면서 right++ 을 통해 새로운 보석을 탐색합니다. 3-1. gems[right]가 현재 내가 가지고 있지 않은 보석이라면 내가 가지고 있는 보석 리스트에 추가합니다. 3-2. gems[right]가 현재 내가 가지고 있는 보석이라면, 3-2-1. 내가 구매할 보석 리스트 중 gems[left] 보석이 2개 이상이면 lef.. 2020. 7. 25. [2020 카카오 인턴십] 수식 최대화 문제: https://programmers.co.kr/learn/courses/30/lessons/67257 시뮬레이션 문제입니다. 1. 연산자들간의 우선순위 정하기: n! 2. 1번 우선순위에 따라 계산하기 수식을 컨트롤할 자료구조를 정하는 게 중요한 문제였네요. 저는 deque를 써서 해결했습니다. 맨 처음에는 (수식어 파싱문제 = 스택)이라 생각하고 스택만 쓰다가 망했습니다. 스택을 통해 expression을 파싱하면 수식 순서가 반대로 되는데, 이 때문에 앞에서부터 계산해야 할 것을 뒤에서부터 계산하게 됩니다. 이게 문제가 되는 이유는 뺄셈의 경우 숫자의 위치가 바뀌게 되면 다른 값이 나오기 때문입니다. e.g. (520 - 60000) - 100 = -59,580 (100 - 60000) - 5.. 2020. 7. 25. [2020 카카오 인턴십] 키패드 누르기 문제: https://programmers.co.kr/learn/courses/30/lessons/67256 시뮬레이션 문제입니다. 핸드폰 자판을 어떻게 좌표화가 하는 지가 중요한 문제였네요. 1, 4, 7의 경우는 왼손이 처리하도록 3, 6, 9의 경우는 오른손이 처리하도록 그 외의 경우에는 오른손과 왼손의 거리, 왼손잡이인지, 오른손잡이인지 따진 후 L,R을 찍어주면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/kakao2020_01.cc 2020. 7. 25. 이전 1 다음
