본문 바로가기

Algorithm/Programmers93

[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.
[코딩테스트 연습] 여행 경로 문제: https://programmers.co.kr/learn/courses/30/lessons/43164 DFS 문제입니다. DDijkstra님의 풀이를 통해 해결했습니다. (https://devje8.tistory.com/) 사전순으로 가장 빠른 경로를 리턴하기 위해 티켓을 '도착지' 기준으로 오름차순 정렬합니다. 티켓을 오름차순 정렬 했으므로 ticketList[N]과 ticketList[N+1]의 출발점 공항이 동일하면 ticketList[N]의 도착지 공항이 ticketList[N+1] 도착지 공항보다 알파벳 순서가 앞섭니다. 그러므로 for (int index = 0; index < ticketList.size; ++index) 으로 DFS 탐색해도 사전순 탐색이 보장됩니다. 주어진 티켓을 .. 2020. 7. 31.
[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.

티스토리툴바