본문 바로가기

Algorithm283

[BOJ]5719번: 거의 최단 경로 문제: https://www.acmicpc.net/problem/5719 jaimemin님 블로그의 솔루션을 참고해서 해결했습니다. (https://jaimemin.tistory.com/617) 다익스트라를 진행하게 되면 src => dst 방향으로 최종 노드까지 최소 간선비용으로 갱신이 됩니다. 이 점을 이용해서 다익스트라 진행 중, 최소 간선 비용이거나, 최소 간선 비용과 비용이 같은 경우 before라는 벡터를 선언해 저장해줍니다. //before[NODE]: 최소 간선 비용으로 정점 NODE로 들어오는 정점들을 저장한 벡터 //ex. before[NODE] = {1,2,3,4} 이면 // 1번 정점 => NODE, 2번 정점 => NODE, 3번 정점 => NODE, 4번 정점 => NODE ve.. 2020. 7. 28.
[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.

티스토리툴바