Be a developer

크루스칼 알고리즘을 알고 있었는데도 틀렸던 문제이다.. 아직도 그 때 코드가 왜 제대로 동작이 안되었는지 모르겠다.. 다시 생각해봐도 크루스칼 코드는 잘 만들었던 것 같은데.. 혹시나 이 문제를 다시 풀어보면서 몰랐던 부분 때문이었을까 하는 생각도 든다. 문제를 다시 풀면서 알게 된 것은 어짜피 몇 개의 다리를 ArrayList에 넣고 정렬을 하더라도 결국은 N-1개의 edge만 만들면 되기 때문에 만들 수 있는 모든 다리를 다 넣어도 된다는 것이다. 저번에 문제를 풀 때는 이러한 생각을 하지 못하고 각 섬을 연결하는 다리 여러 개 중에서 하나만 ArrayList에 넣었었다... 비록 시험에서는 틀렸지만 덕분에 크루스칼에 대해 더 알게 되었다고 생각한다. 먼저 2중 for문을 돌면서 안에서 BFS를 통해..

어떻게 풀어야 할 지는 알겠는데 이를 코드로 어떻게 짜야할지 몰라서 계속 헤매다가 다른 분의 코드를 보고 참고해서 풀었다. 처음에는 수식을 입력받은 그대로 두고 이를 통해서 괄호를 넣을 위치를 정하다보니 index를 4칸씩 5칸씩 6칸씩 뛰어다녔다. 그러다보니 코드가 너무 복잡해져서 다른 분의 코드를 참조했고, 수식을 전부다 볼 필요가 없이 연산자를 기준으로 계산을 하면 된다는 것을 알게 되었다. 그래서 연산자를 기준으로 다시 풀게 되었다. 하나의 연산자를 기준으로 괄호를 치는 경우와 안치는 경우를 나눠서 풀어야 한다는 것은 알았지만, 이를 코드로 계속 구현하려다 보니 뭔가 안 맞고 엉켰다. 특정 순서의 연산자에서 연산을 할 때, 바로 앞에서 괄호를 쳤는지, 안쳤는지를 구분해서 연산을 하려 했다. 2 *..

기본적인 DP 문제이다. 임의의 한 지점(i 번째)에 있는 집이 빨강일 때, 초록일 때 파랑일 때로 나누어서 생각한다. 1)빨강일 때: min(i-1번 째 있는 집이 파랑, i-1번 째 있는 집이 노랑) + i번째가 빨강일 때 칠하는 비용 2)초록일 때: min(i-1번 째 있는 집이 빨강, i-1번 째 있는 집이 파랑) + i번째가 초록일 때 칠하는 비용 3)파랑일 때: min(i-1번 째 있는 집이 빨강, i-1번 째 있는 집이 초록) + i번째가 파랑일 때 칠하는 비용 따라서 DP 배열을 선언할 때 2차원 배열로 선언하고 dp[n][3]으로 생선한다.(n은 집의 개수, 3은 빨강,초록,파랑) 마지막 최솟값은 n번째 집의 min(빨강,초록,파랑) 이다. 코드는 아래와 같다. import java.io..

A형 기출문제라고 한다. 처음에 큰 거 부터 넣어서 그리디로 풀려고 했는데, 모양에 따라 답이 틀려지는 것을 알게 되어서 완탐으로 풀었다. 색종이를 붙여야 하는 공간을 10*10으로 매번 찾기보다는 해당 (row,col)을 list로 가져오는 것이 더 시간상 빠를 것이라 생각했다. 그리고 완탐을 하려면 1x1의 색종이를 붙이고 모든 경우를 다 해 본후, 다시 돌아와서 2x2의 색종이를 붙이는 방식으로 붙여야 했기 때문에, dfs를 통해 풀었다. 또한, 색종이를 붙이고 난 후에는 해당 공간을 체크해야 하는데, 색종이를 붙일 공간을 2차원 배열로 가지고 있지 않고, list로 가지고 있기 때문에, check(색종이를 붙인 좌표를 체크)라는 1차원 배열만 다음 dfs로 넘겨주어도 되었다. square 함수를 ..

상반기 삼성 코딩테스트 기출문제이다. 상반기에 단기간에 공부해서 시험치러 갔다가 결국 런타임 에러를 잡지 못하고 와서 멘탈이 나갔었다.. 평생 잊을 수 없는 문제가 될 것 같다. 그 후로 풀고 싶었지만 문제를 보고 싶지 않아서 다른 문제들을 먼저 다 풀었다. 결국 백준에 있는 다른 기출 문제들을 다 푼후에 다시 풀게 되었다. 당시에는 runtime에러를 어떻게 찾아야 할 지 감도 잡지 못했었다. 배열을 참조할 때 인덱스가 벗어났을 것이라 생각해서 1시간이 넘는 시간 동안 이를 찾다가 결국 시간 안에 풀지 못하고 나왔던 아픈 경험이었다. 그리고 다시 c++이 아닌 Java로 풀게 되었다. 문제를 한 번 봤던 탓인지 문제가 어렵지 않았다. 문제를 많이 풀어보면서 굳이 배열이 주어져도 배열에서 움직이는 것이 ..

상반기 코딩 테스트 기출문제이다. 그 때는 미세먼지 문제를 푼다고 읽어보기만 했던 문제였다. 문제 자체는 어렵지 않고, 시간 복잡도를 잘 계산해서 이동 거리를 줄이는 것이 중요한 포인트이다. 상어들을 class로 만들어서 arraylist로 저장한 후 먼저 낚시왕에게 잡히는 것들을 계산한다. 그리고 상어를 이동하는데, 이 때 거리를 줄이는 법을 생각해내야 했다. % 연산자로 가능할 것이라 생각했는데, 2 * (r - 1) or 2 * (c - 1)로 연산해야 됨을 찾아 내었다. 하지만 양 끝에서 시작하는 경우, 예를 들어 왼쪽 끝에서 오른쪽 방향을 보고 있는 상어의 경우 해당 연산만큼 % 연산을 한 후 그 값이 0인 경우에는 방향을 바꿔 준 후 이동해야 했다. 이를 빠르게 찾지 못하고 다른 방법들을 생각..

왜 상반기 기출문제를 풀 때 안풀어 보았는지는 모르겠지만, 기출 문제를 다시 한 번 풀어보는 과정에서 풀게 되었다. 안전한 곳의 수를 세면 되기 때문에, map을 입력 받을 때 그 수를 세어주었다. (2차원 배열을 다 돌면서 세지 않고 이렇게 하는 방법을 다른 문제에서 다뤄본 적이 있었다.) 일단 바이러스는 퍼져나가는 것이기 때문에 BFS로 풀어야 했고, 벽의 위치는 안전한 곳에서 3개를 고르는 조합이었기 때문에 DFS를 통해서 해결했다. 다만, DFS(재귀)를 돌면서 BFS를 돌아야 했기 때문에 시간 복잡도를 계산해보아야 했고, 충분하다는 생각이 들었다.(시뮬레이션 하는 것 말고는 다른 방법이 생각나지 않았다.) Queue를 만들어 바이러스의 위치를 넣어주고, visit를 통해서 BFS를 돌렸다. 다만..

이번 문제를 풀면서 부족했던 점들을 먼저 나열하겠다. 첫 번째, 시간 복잡도를 제대로 계산하지 못했다. 왜냐하면 풀이에 확신이 없었기 때문이다. 주어진 조건 대로 블럭을 옮기면 풀릴 것 같았지만 dfs를 통해서 풀어야 했기 때문에 시간 초과에 대한 확신이 없었다. 그래서 해당 문제 풀이를 시작하기 까지 시간이 오래 걸렸다. 5번 이동이 가능하고 한 번 이동에 4방향이 가능 하므로 4^5가 우선적으로 걸린다고 생각했다. 그리고 20 x 20 배열이므로 400 * 4^5의 시간이 걸린다고 생각했다. 여기 까지는 충분하다고 생각했지만, 여기에 각 블럭을 이동하는 데 걸리는 시간이 곱해진다면 시간 초과가 나지 않을까 하는 생각이 들었고, 좀 더 쉽게 풀어 보려는 생각도 더해졌던 것 같다. 하지만 마땅한 방법이 ..