Algorithm/Programmers93

• 

  [2020 카카오 기출] 블록 이동하기 문제: https://programmers.co.kr/learn/courses/30/lessons/60063 시뮬레이션 문제입니다. 따져줄 게 참 많아보이는 문제입니다만 아래 두 가지에 대해서만 잘 정하고 풀면 됩니다. 1. 상태를 어떻게 저장할 지 2. 다음 좌표 탐색을 어떻게 할 지 우선 편의를 위해 블록의 2칸 중 한 칸을 HEAD, 다른 한 칸을 TAIL이라고 하겠습니다. 우리는 (HEAD_Y, HEAD_X, TAIl_Y, TAIL_X)로 4개의 정보가 필요하지만 이는 (HEAD_Y, HEAD_X, HEAD가 TAIL과 연결되어 있는 방향) 3개 정보로 똑같이 표현할 수 있습니다. 그래서 상태를 어떻게 저장하느냐에 대해서는 (HEAD_Y, HEAD_X, Direction)으로 표현하겠습니다. (b.. Algorithm/Programmers 2020. 8. 11.

• 

  [2020 카카오 기출] 기둥과 보 설치 문제: https://programmers.co.kr/learn/courses/30/lessons/60061 sooooooyn님의 솔루션으로 해결하였습니다. (https://sooooooyn.tistory.com/32) 기둥과 보를 설치/삭제 시에 어떻게 따져주는 지에 따라 난이도가 달라지는 문제입니다. 서치했던 솔루션 중에 굉장히 심플한 솔루션이라고 생각합니다. 간단하게 두 가지로 모든 경우를 처리합니다. 1. stick[N][N], paper[N][N] 으로 기둥과 보를 표현 2. 삭제 입력이 들어오면 일단 삭제 시켜본 후에, 삭제 시킨 좌표와 연관이 있는 기둥이나 보가 설치 불가능하다고 판정이 나는 경우 롤백시킵니다. 코드: https://github.com/cottory/algorithm/blob.. Algorithm/Programmers 2020. 8. 11.

• 

  [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, 좌표 하나만 가지고 움직여도 경주로를 표현할 수 있습니다.) 도로를 설치하면서 모든 방향을 탐색해봐야 합니다. (단, 현재 진행하던 방향과 반대방향은 무한 루프에 빠지게 되니 그.. Algorithm/Programmers 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 탐색해도 사전순 탐색이 보장됩니다. 주어진 티켓을 .. Algorithm/Programmers 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.. Algorithm/Programmers 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.. Algorithm/Programmers 2020. 7. 25.