본문 바로가기
반응형

알고리즘/BOJ

14889번 14889번 - 스타트와 링크 2017년 하반기 삼성전자 sw 역량테스트 문제이다. 나는 이때 직접 시험을 봤는데.. 그때 대충 팀 나누는 거 까지는 감 잡았는데 그 뒤로 멘붕이었는데.. 다시 풀어보니 너무 쉬운 문제였다.. 다만 처음에 팀을 두개로 안나누고, 한개의 팀으로 풀려다 보니 시간초과가 나는 부분이 있었다. 그 부분은 재귀함수에서 변수를 하나 추가해주는 방식으로 풀 수 있었다. 여기서 막혔었다. 팀을 두개로 나눠서 풀면, 복잡한 생각없이 풀 수 있는 문제였다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include#include usin.. 더보기
10026번 10026번 - 적록색약 간단하게 적록색약이 아닐때, 적록색약일 때 dfs를 두번 돌리면 된다. map 을 다시 새로 만들거나 해도 되는데, 그냥 dfs2 라는 함수를 만들어서 문제를 풀었다. BFS 로도 풀 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104#include#include using namespace std;int dx[4] = { 0,0,1,-1 };int dy[4].. 더보기
5214번 5214번 - 환승 처음에 V의 값이 꽤나 크긴 했지만, vector 를 이용한 연결리스트로 bfs를 구현하면 될 줄 알았다. 하지만 처음에는 중복값이 연결리스트에 들어왔고, 그래서 풀지 못했다. 그래서 인접 행렬을 이용해서 풀었더니 메모리 초과가 발생했다. 그래서 그 다음에는 map 을 이용해서 간선의 중복을 없애고 풀었지만, 시간초과가 발생했다. 그래서 다른 분들 풀이를 보니, 너무나 쉽지만 생각지 못했던, 하이퍼 튜브를 정점으로 만들어서 연결해주는 방법을 사용했다. (기존 노드 말고 새로운 더미 노드를 생각해내는 방법을 잊지말자!) 그렇게 문제를 풀게 되면 하이퍼 튜브를 거쳐 가기 때문에, 한 정점에서 다른 정점으로 이동하는데 2만큼이 필요하게 된다. 그래서 마지막 답을 구할 때, 최단 거리를 2로.. 더보기
1058번 1058번 - 친구 처음에 문제를 읽고 무슨말인가 했지만 그냥 어떤 한 정점에서 거리가 2이하인 값들의 총 갯수들 중에서 최대값을 구하는 문제였다. 그래서 모든 정점을 비교할 필요가 있었기 때문에 플로이드 알고리즘을 이용했다. 그리고 마지막에 자기 자신으로 가는 값을 하나 빼줬다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include using namespace std; int D[51][51];const int INF = 987654321;int main(){ int n; scanf("%d", &n); for (int .. 더보기
5567번 5567번 - 결혼 그래프 문제, 음의 가중치가 없고, 모든 간선의 가중치가 동일하기 때문에 BFS를 이용해서 문제를 풀 수 있었다. 친구의 친구까지 결혼식에 초대할 수 있으므로, 1번 정점에서 가중치가 2이하인 것들 중, 방문할 수 없는 것들은 제외한 값을 출력하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include#include#includeusing namespace std; int main(){ int n, m; scanf("%d %d", &n, &m); vector v(n + 1); while (m--) { int a, b; scanf("%d %d", &a, .. 더보기
5719번 5719번 - 거의 최단 경로 이 문제 푸는데 계속 틀려서, 틀린 테스트 케이스를 찾아보면서 고쳤다. 처음에는 정점을 삭제하는 방식으로 구했더니, 예외가 발생했고. 그래서 간선을 삭제하는 방식으로 풀었더니 또 다른 예외가 발생했다.. 단순히 다익스트라를 한번 돌리고, 다시 돌려서 다른 값이 나온다고 정답이 아니었다. 갈 수 있는 최단거리를 모두 가보고, 간선을 삭제하고, 그 다음에 다익스트라로 마지막 답을 구하는 순서로 풀어야 했다. 그래서 처음에 다익스트라를 돌리고, 그 때 간선들 모두 삭제하고, 다익스트라 돌리고, 삭제하고 이런 방법으로 했는데.. 삭제 할때도 막 삭제하면 안되는 반례가 존재했다. 어떤 정점에서 나가는 간선이 여러개 일때는, 그 정점을 기준으로 시작점 쪽으로의 간선은 더 이상 지우면 .. 더보기
2211번 2211번 - 네트워크 복구 다익스트라를 이용해서 최단 거리를 구하면 된다. 슈퍼컴퓨터로 부터 모든 노드들의 최단거리를 구하면 주어진 조건에 맞게 된다. 그리고 BFS,다익스트라,벨만포드는 전부 parent 배열을 만들어서 , dist 값이 갱신될 때 parent 값들을 넣어주면 실제 경로를 구할 수 있다. 몇몇 사람들은 MST ( 최소 스패닝 트리) 로 접근한 사람들도 있는데... 2번 조건 때문에 안되는 것 같다. 모든 노드들의 합이 최소라고 해서, 그 노드들이 슈퍼컴퓨터로 부터 최단거리로 연결한다고 보장할 수 없기 때문이다? 사실 정확히 확신은 안가지만, 다익스트라로 확실히 풀 수 있다. ##추가로 밑에 코드에서 ans를 통해 간선의 갯수를 구했는데.. n개의 정점에서 최소의 간선은 n-1입니다.(.. 더보기
10282번 10282번 - 해킹 양의 가중치를 갖는 그래프에서 최단거리를 구하는 것과 똑같은 문제이다. 따라서 다익스트라 알고리즘을 사용하여 문제를 풀 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include#include#include using namespace std;const int INF = 987654321;int main(){ int tc; scanf("%d", &tc); while (tc--) { int n, d, c; scanf("%d %d %d", &n, &d, &c); vector v(n+1); vector di.. 더보기
반응형

티스토리툴바