104%

며칠만에 bfs 다시 풀려고하니까 어떻게 해야되는지 까먹어서 조금 고민했던 문제.. 틀린 원인 까지 분석해보겠다 우선 문제 자체는 기본적인 bfs문제이다. 비 방향 그래프가 주어지고 1번컴퓨터와 연결된 모든 컴퓨터의 개수를 세는 문제이다.(1번컴퓨터 제외) 문제를 보자마자 dfs 혹은 bfs를 적용하면 쉽게 풀릴것 같았고, 그중에서도 bfs를 쓰는게 더 빨리 답을 찾을수 있을것 같았다. 대충 알고리즘 동작 방식은 문제에 주어진 입력을 W[i][j]의 인접행렬로 바꾸고 그리고 나서 bfs를 시작하는데 1번컴퓨터 부터 bfs를 시작하게끔 설계했다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495..

계단 오르기 성공 풀이문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB166596265466238.207%문제계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째, 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서..

엄청난 시간초과 재시도 후에 겨우 성공.. 우선 문제를 어떻게 풀었는지 설명하고 나서 시간초과가 난 원인까지 분석을 해보겠다. 처음에는 이문제를 그냥 DFS로 풀어봤는데 시간 초과가 났다 그냥 DFS로 풀게되면 너무나 많은 경로를 탐색하기 때문에 당연히 시간초과가 날수밖에 없다. 상하좌우 4방향으로 이동이 가능하고 칸수가 최대 500x500 = 250000개이므로 4의 250000승이라는 어마어마한 경로의 경우의수가 존재하기 때문에 그냥 DFS로는 절대 풀수 없는 문제이다. 그래서 DP로 풀어야 하는데, DP로 풀때도 주의사항이 있다. 우선 코드를 먼저 보면 123456789101112131415161718int dfs(int x, int y){ if (dp[x][y] != -1) return dp[x]..

dfs는 데이터의 개수가 조금만 커져도 시간초과가 날 확률이 높은 방법이다. 왜냐하면 50x50칸의 2차원 배열이 있을때 0,0에서 50,50으로 가는 경우의 수를 찾을때 dfs를 사용해야 하고, 상하좌우 네방향으로 이동 가능하다고 했을때4의(50x50)승이라는 어마어마한 연산의 횟수가 발생한다. 물론 범위 벗어나는거 제외하고 이러다보면 저것보단 적겠지만, 어쨌든 그래도 엄청난 연산횟수라는것은 부정할수없다. 그렇기 때문에 우리는 같은 계산을 피해야 한다. 그것이 바로 동적계획법(Dynamic Programming)이고 다른말로 메모이제이션이라고도 한다. 즉 DFS는 DFS인데 예전에 구해놨던 값이 있으면 그 값을 쓰겠다는 뜻이다. 예를 들어 0,0에서 1,1을 거쳐 50,50으로 가는 경로가 있다고 하자..

이 문제는 BFS를 연습하기 가장 좋은 문제인것 같다. 오랜만에 넣자마자 성공.. 문제를 풀면서 느낀건데 BFS와 큐 벡터등 기초적인 내용을 잘 익힐수있는 문제라고 생각한다. 문제 예시가 너무 잘나와있어서 문제 해석에는 별로 어려움이 없었다. 풀이과정을 대충 설명하자면 우선 M x N 의 칸을 배열로 매칭시켜야 한다. 그리고 나서 각 나눠진 영역에 대해서 BFS를 돌려야 한다. DFS도 해보진 않았지만 시간제한이 1초이기때문에 왠지 시간초과가 날것같지만 해보진 않았다. DFS같은경우에는 모든 경우를 탐색할수있지만 한곳을 계속해서 파내려가므로 시간이 오래걸릴수있다는 단점이 있다. 그래서 이문제는 BFS 로 접근하는게 맞는것 같다. 우선 정사각형을 2차원 배열에 맵핑 시켜야 하는데, 아래 코드가 그 코드이다..

이 문제는 DFS 기초 문제이다. 하지만 재귀로 풀려고했을때 처음에는 시간 초과가 나서 약간 삽질을 좀 했다.. 문제는 우선 1->2->3으로 갈수 있을때 1->3으로도 갈수있으므로 W[1][3]도 갈수있다고 1로 체크해주는 문제이다. 즉 중간에 몇개를 거쳐서라도 갈수 있으면 그 경로는 갈수있다고 체크를 해준다. 워셜-플로이드 알고리즘으로도 풀수 있지만 나는 dfs를 연습하고 싶어서 굳이 dfs로 풀었다. 첫번째 예제로 설명을 하자면, 1->2 , 2->3 , 3->1로 갈수있는 경로가 있다. 먼저 첫번째 정점인 1번 정점에서 갈수있는 경로를 모두 조사한다. for(int i=1; i

김지민은 세계적인 기타 플레이어이다. 불행하게도 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 세계적인 기타리스트인 김지민은 되도록이면 돈을 적게쓰려고 한다. 김지민은 6줄 패키지를 살 수도 있지만, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다. 끊어진 기타 줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.입력첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어..

우리가 자료구조와 알고리즘을 이해할때 두가지 방식이 있다. 1.코드레벨로 내려가서 구현에 초점을 맞춘 이해2.어떤식으로 동작하는지에 대해 도식화 하는 방법 개인적으로 1번방식보다는 2번방식이 더 좋다고 생각한다 그 이유는 어차피 내가 지금 쓰려고 하는 알고리즘 및 자료구조는 이미 검증된 라이브러리로 누군가 완벽하고 쓸만하도록 만들어 놨다. 우리가 할일은 어떤 자료구조와 어떤 알고리즘이 어떤 상황에서 가장 효율적인가 비교할수 있고 상황에 맞는 것을 가져다 쓸수 있는 능력을 길러야 한다. 2학년 자료구조와 알고리즘 수업을 들을때 교수님들이 항상 코드레벨보다는 동작 과정에 대해 초점을 맞추고 수업을 하셨는데 그때는 왜 그런 방식인지 몰랐지만 지금 와서 다시 생각해보면 아주 좋은 방식으로 수업을 하셨다고 생각이..