알고리즘 썸네일형 리스트형 10597번 10597번 - 순열 장난 백트래킹 문제. 일단 나는 주어진 입력을 토대로 1에서 몇까지 수인지 구하기 위한 N값을 구했다. 그 다음 재귀 함수를 통해서 한칸만 가던지, 두칸만 가던지를 선택하는데, 이때 N보다는 작거나 같아야 하고, 이미 구한 값이면 안되기 때문에 bool 타입의 v벡터를 이용했다. 결과 값을 구했다면, 그 값이 맞는지 확인하고, 출력하는 방식으로 문제를 풀었다. 처음에 0 값을 생각하지 않아서 자꾸 0,1,2,3.. 이런식으로 문제가 풀렸었다. 체크할 때 0 값도 체크해서 AC받았다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061.. 더보기 2580번 2580번 - 스도쿠 처음에는 가로,세로만 확인하고, 3x3 구역은 따로 함수를 만들었더니 시간초과가 발생했다. 그래서 3x3 구역도 배열로 다 만들어서 if문에 의해 체크하는 식으로 만들었더니 AC를 받을 수 있었다. 로직은 garo[i][j] 는 가로 i번에서 숫자 j 가 있으면 true, 없으면 false sero[i][j] 는 세로 i번에서 숫자 j 가 있으면 true, 없으면 false sq[i][j] 는 i번 구역에서 숫자 j 가 있으면 true,없으면 false 이런식으로 배열을 선언하고, 세개 모두 해당하면 빈 숫자를 집어넣는 식으로 재귀함수를 실행했다. 구역은 맨왼쪽 위 3x3 을 0으로, 마지막 오른쪽 맨 아래 3x3 을 9로 생각하고 문제를 풀었다. 1234567891011121314.. 더보기 2458번 2458번 - 키순서 플로이드 알고리즘 문제. N제한이 500이라 시간 초과가 뜨지 않도록 아래부분도 추가했다. ios::sync_with_stdio(false); cin.tie(NULL); 로직은 나보다 키 큰 사람의 숫자, 나보다 키 작은 사람의 숫자가 총 인원과 같으면 나의 키를 알 수 있다. 따라서 플로이드 알고리즘으로 D배열을 구한 뒤, 나보다 키 큰 사람의 숫자 = D[나][다른사람] 나보다 키 작은 사람의 숫자 = D[다른사람][나] 일 때 마다 숫자를 세서 문제를 풀면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465.. 더보기 9205번 9205번 - 맥주 마시면서 걸어가기 문제를 읽으면서 x,y 범위가 막 주어지고 어떤식으로 노드를 구성해야 할까 고민했다. 좌표별로 구하려고 하면 메모리가 넘칠 것 같아서 조금 더 생각해보니 , 간단한 플로이드 알고리즘 문제였다. 왜냐하면 편의점과 출발점 도착점을 모두 합쳐서 최대 노드가 102개 밖에 나오지 않기 때문이다. 우선 입력받은 n을 통해서 n+2 개의 노드를 만들고, x,y 값들을 입력받는다. 이때 n이 0 이면 출발점, n+1 일때는 마지막 페스티벌의 도착점. 그 다음 모든 노드들이 갈 수 있는지를 체크한다, 이 때 기준은 맥주 50잔 이기 때문에 거리가 1000 이하여야 한다. 이 값들을 플로이드 알고리즘을 사용하는 D배열에 저장한다. 플로이드 알고리즘을 구하고, 시작점0 에서 끝점 n+.. 더보기 2610번 2610번 - 회의준비 문제를 풀어서 해석하면, 연결 요소의 갯수를 구하고, 플로이드 이용값을 이용하는 문제이다. 연결 요소의 갯수를 구하는 방식은 dfs 나 bfs로 구하는데, 이 문제는 dfs를 통해서 구했다. 그리고 플로이드 알고리즘을 통해 구한 값으로 의사 전달 시간 중 최대값이 최소값이 되는 값을 구할 수 있다. 의사 전달 시간 중 최대값이 최소값이란 말 때문에 나도 처음에 문제를 틀렸고, 질문 게시판에 보면 그에 따른 많은 질문이 있고, 답변도 있어서 그걸 이해하고 문제를 풀 수 있었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626.. 더보기 1613번 1613번 - 역사 단순 플로이드 알고리즘을 이용해서, 주어진 값이 연결이 되어있는지 안되어있는지를 확인하면 됐다. 양방향 간선이 아니기 때문에 간단하게 풀 수 있었는데.. 너무 복잡하게 생각해서, 경로까지 만들어서 풀려다 보니 풀리지가 않았다.. 처음에 생각을 정확하게 할 필요가 있다는 것을 느꼈다.. ### 그래도 간만에 플로이드를 이용해서 path 를 만드는 법을 공부했다. 다시 한번 만드는 방법을 공부하고, 코딩으로 구현해봐야겠다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include#include#includeusing nam.. 더보기 1219번 1219번 - 민식이의 고민 문제 푸는데 엄청 걸렸다 민식이 새끼 이 문제는 정답률이 굉장히 낮은데, 단지 싸이클의 존재여부를 파악하는게 아니라 싸이클이 목적지와 연결이 되어있는지 아닌지를 파악해야 하는 문제여서 그런 것 같다. 근데 로직적으로 다 짜고, 플로이드 알고리즘에서 자기 자신을 true 바꿔주지 않아서.. 한 30번 틀렸다.. ### 주의 사항 플로이드 알고리즘을 단지, 연결되어 있는지 여부로 쓸 때랑 모든 쌍의 최단거리를 구할 때 생각하면서 자기자신에 도달 여부를 파악해야겠다. ### 새로 배운 점 SPFA 나 벨만포드를 음수싸이클을 파악할 때 까지 (N-1)까지 돌리면 , 그 때 값들을 이용해서 싸이클에 포함되는 점을 구할 수 있다. 기본적인 로직 1. 플로이드 알고리즘을 통해서 노드끼리 .. 더보기 10217번 10217번 - KCM Travel 이 문제도 이전 문제와 마찬가지로 다익스트라를 기반으로 한차원 늘려서 문제를 풀었다. 시간제한이 10초이기 때문에 시간도 넉넉했다. dist[n][k] 라는 이차원 배열이 n노드까지 k원일때 최단거리라고 만들어서 문제를 풀 수 있었다. 그렇게 해서 다음 정점 노드의 시간값이 최소시간이고, 가격이 m원 이하일 때만 큐에 넣어서 다익스트라로 풀었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include#include.. 더보기 이전 1 ··· 15 16 17 18 19 20 21 ··· 46 다음