프로그래민👨‍💻

위상정렬을 이용한 그래프 문제였다. 이 문제는 부품사이의 순위가 존재하고 서로 이어보면 DAG를 형성할 수 있기에 위상정렬을 사용해보았다. 큰부품 -> 작음부품이렇게 바라보도록 그래프를 그리고, 갯수만큼 곱해주면서 위상정렬을 돌면 최소부품이 몇개 필요한지 찾을 수 있는 간단한 문제였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 ..

위상정렬을 이용하여 풀었던 그래프문제이다. 이 문제를 맨처음 접했을 때 각 노드끼리의 순위가 존재하고 싸이클이 없기에 위상정렬을 사용해보았다. 맨처음 문제를 접근을 다음과 같이해보았다. 만일 1등, 2등, 3등, 4등이 존재한다면 4등->3등, 3등->2등, 2등->1등 이런식으로 그래프를 그려보았다. 하지만 이 문제는 순위가 뒤바뀌는 경우가 있는데 맨처음 내가 적용한 방식은 순위가 뒤바뀌는 것을 처리해주지 못하기에 그래프를 새롭게 그려보았다. 즉, 4등->3등, 4등->2등, 4등->1등, 3등->2등, 3등->2등, 2등->1등과 같이 순위가 낮은것이 자기보다 높은 순위를 모두 볼수 있도록 그래프를 그리는 방식을 수정하였다. 이런 방식을 통해 순위가 바뀌는 경우도 처리해주었고, 그래프를 새로그린다음에..

플로이드와샬과 DFS를 같이 활용하는 문제이다. 내용자체를 이해하는데 좀 어려웠던 문제였다. 이 문제에서 결론적으로 구하는 것은 1. 서로 연결되어 있는 노드 중에서 2. 다른 노드로의 최대거리가 가장 작은 노드를 대표로 선정 하는 문제이다. 이러한 과정에서 1번을 해결하는 데에 DFS, 2번을 해결하는데 N값이 100이하이기에 플로이드와샬을 사용하였다. 전체적인 로직을 정리하자면 다음과 같다. N이 100이하이기에 플로이드와샬을 이용하여 전체 노드의 최단 경로를 map[][] 에 저장 1~N까지의 노드를 각각 확인하여 다른 노드로의 최대값을 maxDistanceToOther에 저장 그 후 1~N까지의 노드중 방문안한 노드에 대해 graph를 이용하여 DFS DFS를 돌면서 maxDistanceToOth..

다익스트라를 활용하는 문제였다. 최단 경로 문제이지만 이 문제는 N의 최대값이 1000이기에 플로이드와샬 기법보다는 다익스트라가 적합할 것 같아서 다익스트라로 접근하였다. 이 문제는 경로가 주어지고 특정 목적지를 왕복하는 문제였다. 따라서 두가지로 나누어 풀어보았다. 첫번째로 시작점에서 목적지까지의 다익스트라, 두번째로 목적지에서 시작점까지의 다익스트라, 이 두가지를 구하여 시작점을 바꿔가며 최대값을 확인하여 답을 풀었다. 즉 max(distanceFromStart[end] + distanceFromEnd[start]) 값을 구하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35..

플로이드와샬을 활용하는 문제였다. 기존 플로이드와샬 문제와는 접근법을 다르게해야 풀 수 있는 문제였다. 이 문제 같은 경우는 단방향에서 양방향으로 바꿔야하는 길의 수, 즉 단방향으로 연결되어 있는 곳에 반대 반향의 길을 연결해야하는 갯수를 체크해야하는 문제이다. 이 문제 같은 경우는 N의 최대값이 250이기에 최단거리를 구하는 플로이드와샬 기법을 활용할 수 있다. 다만, 기존의 플로이드와샬 문제와는 다르게 경로의 비용 선정에 있어서 조금 다른 부분이 필요하다. 즉, 구해야하는 것이 단방향에서 반대방향의 갯수이기에 단방향이 입력으로 들어왔을 때 반대방향에 대해서 1, 그외에는 0으로 설정해주는 것이 필요하다. 다시말해 기존 경로에 대해서는 0, 새로 생성할(단뱡향에서의 반대방향)경로에 대해서는 1로 설정을..

Knapsack을 활용한 문제이다. Knapsack dp문제를 활용하여 접근해보았다. dp[N][cost]를 생성하고 메모리가 기준값을 넘을 때 마다 cost값을 최솟값으로 갱신하는 방법으로 접근해보았다. 맨처음 이 문제를 접근했을때 cost값대신 메모리 값으로 접근하였는데, cost 값기준으로 접근하는 것을 생각해내는데 오래걸렸다. 다만 cost값을 기준으로 접근하니깐 문제를 수훨하게 풀 수 있었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 pac..

유명한 Knapsack 문제이다. Knapsack 대표적인 문제이다. 보통 Knapsack 문제를 접근할때는 크게 두가지 방법이 있다. 크게 브루트포스와 dp로 접근할 수 있다. 브루투포스로 접근은 단순하게 고르고, 안고르고를 반복하며 재귀호출하는 방식이다. 이 방식은 시간복잡도가 2^N 이기에 대다수의 문제에서 적용이 힘들다. 이 문제또한 N의 최대값이 100이기에 적용이 불가하지만 한번 코드는 작성해보았다. 1. 브루트 포스(시간초과) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 package algostudy2..

dp와 dfs를 같이 활용한 문제이다. 저번에 풀었던 1520번 내리막길과 비슷한 문제이다. 마찬가지로 dfs를 도는데 최대 n의 크기가 500이 되므로 중간에 이차원 dp 배열을 통해 메모이제이션을 활용하는 전략을 사용했다. 이 문제도 마찬가지로 dp 이차원 배열을 -1로 초기화 시키고 dfs 의 반환값을 dp[i][j]로 반환하면서 dp값을 찾는 방식이다. 다만 이 문제에서 유의할점은 각 위치에서의 최대값을 찾는 것이기 때문에 dp를 갱신할때 dfs+1 (현재포함)한 값과 비교하여 최대값을 찾는 방식으로 구현해야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 ..

dfs와 dp를 같이 활용하는 문제였다. 맨처음 문제를 보았을때 백트래킹으로 접근해보았다. 하지만 M과 N이 최대 500을 가지고 있기에 시간초과를 우려하게 되었다. 따라서 메모제이션을 활용할 수 있는 dp를 같이 접목해보았다. dp[i][j]라는 배열을 두고 i,j에서의 M,N을 도달하는 방법의 수를 가지도록 설계를 하였다. 즉 dfs를 돈 경험이 있는 i,j 위치를 탐색해야할때 다시 dfs를 도는 것이 아니라 dp[i][j] 값만을 반환하도록 메모이제이션을 활용해주었다. 이 때 주의할점은 이차원 dp 배열의 초기값을 -1로 하는 것이랑 dfs 메소드가 dp[i][j]를 반환하도록 설계하는 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2..

누적합과 슬라이딩 윈도우를 이용하는 문제였다. 우선적으로 모든 시청자들의 시간을 배열에 누적해주었다. 그 다음 접근법을 고민해보았다. 이 문제 같은 경우 광고시간이 크기 N으로 고정이기 때문에 이것을 전체 배열길이에서 만큼 한칸씩 밀면서 움직여보며 답을 찾는 방법인 슬라이딩 윈도우를 적용시켜보았다. 기본적으로 아이디어는 맞았지만 문제를 풀면서 주의할점이 여러가지 있었다. 첫째, 시간을 초로 바꿔서 푸는 부분 둘째, 동영상 재생시간 = 재생 종료된 시간 - 재생 시작된 시간 이므로 재생종료시간을 포함 X 셋째, 슬라이딩 윈도우 크기 만큼의 배열 합 값이 int 범위를 넘어갈 수 있는 부분 위의 부분을 고려하여 반례들을 해결할 수 있었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..