짱아의 개발 기록장

'최소'라는 조건이 있었기 때문에 바로 bfs로 풀어야 한다고 생각했다. 풀고 나서 다른 분들의 풀이를 보니, 굳이 bfs 뿐 아니라 dfs로 푸신 분들도 있으셔서 상관은 없는 듯 싶다. 일단, 초기 동전의 위치를 큐에 넣어주고 1) 네 방향에 있어서 각각의 동전의 위치가 범위를 벗어나는지, 한 개만 벗어나는지, 범위를 안 벗어나는지를 판단한다. 2) 두 동전 모두 범위를 벗어나면, continue 3) 한 개만 벗어나면 -> cnt가 10이 넘지 않는지 확인후 cnt를 반환해준다. cnt가 10이 넘으면 -1을 반환 4) 범위를 벗어나지 않으면 -> 이동한 곳이 벽인지 아닌지를 확인해주고 큐에 넣는다. 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20..

이 문제는 처음에 딱 읽었을 때 bfs로 풀면 간단하겠다라고 생각했지만, 통신탑과 간선의 개수가 각각 최대 100,000 인것을 보고 bfs로 풀다가는 백퍼 시간초과가 나겠구나 싶었다. 그리고 다른 방법을 고민하다가 도저히 아이디어가 생각나지 않아, 문제 유형을 검색해보니 바로 "유니온파인드"를 이용하는 문제였다. 끊을 간선을 제외한 모든 간선을 먼저 연결해주고 끊을 간선들을 역순으로 하나씩 연결해주며 값을 계산해나가면 된다. 예를 들어, a->b a를 b와 연결해준다면 a의 부모 노드를 찾고 b의 부모노드를 찾아서 연결해주고 b의 부모노드의 값에 a의 부모노드의 값을 더해주면 된다. (cost[b] += cost[a] 이런식으로 구현했다.) 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 1..

투포인터를 활용해 푸는 문제이다. 2020카카오인턴 기출 문제 3번인 보석쇼핑과 매우 유사한 문제이다. 유사 문제 https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 위 문제에 대한 코드도 블로그에 정리해 두었다. https://jungahshin.tistory.com/10?category=830724 2020 카카오 인턴 코딩 테스트 - 3번. 보석쇼핑(c++) 이 문제는 투포인터를 이용하면 쉽게 풀 수 있는 문제이다. 문제에서 gems 배열의 크기가 100,..