티스토리

코딩무식자 전공생
검색하기

블로그 홈

코딩무식자 전공생

jow1025.tistory.com/m

코딩초보 대학생의 공부일지와 일상을 담은 블로그입니다. jow1025@naver.com

구독자
18
방명록 방문하기
공지 댓글은 수시로 확인하고있습니다 모두보기

주요 글 목록

  • [백준 1956] 운동 문제 출처: https://www.acmicpc.net/problem/1956 풀이사소한 오타 하나때문에 15번정도 제출오류가 났던 문제입니다.풀이 방법순으로 적어보면,1. map을 INF로 초기화해놓는다.2. 플로이드와샬을 돌려서 map에 각 노드에서 각 노드로 가는 최단거리를 저장한다.3. 각 노드에서 노드로 가는 길 중 INF가 아닐때만(길이 있을 때만) 사이클의 최단길이를 비교합니다.4. map[i][j]!=INF&&map[j][i]!=INF이면 사이클이 존재하는 것이고, 결국 temp가 INF라면 사이클이없으므로, -1을출력합니다. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#i.. 공감수 0 댓글수 0 2020. 2. 11.
  • [백준 1389] 케빈 베이컨의 6단계 법칙 문제 출처: https://www.acmicpc.net/problem/1389 풀이문제 조건에맞게 예제를 그려서 보면 문제에서 원하는 답은 어떤정점에서 각 정점으로 가는 최단거리의 합이 가장 작은 정점임을 알 수 있습니다.문제를 읽어보면 플로이드와샬 알고리즘으로 풀 수 있음을 짐작 할 수 있습니다.플로이드 와샬 알고리즘으로 풀 때 한 노드에서 다른 노드로 가는 길이 없을 때를 0이아닌 INF로 채워넣고 푸는 방법과 0으로 초기화시켜놓고 푸는방법이 있는데, 0으로 초기화 시켜서 풀 경우, "길이 없음"과 최단거리의 의미가 충돌되므로 출발->도착 하는 지점이 없을 경우는일단 map[i][j]를 출발->거치고->도착하는 값으로 설정시켜줘야합니다. 저는 INF로 채워놓고 풀었습니다.(취향 차이인 것 같습니다.).. 공감수 0 댓글수 0 2020. 2. 5.
  • [백준 2458] 키 순서 문제출처: https://www.acmicpc.net/problem/2458 풀이https://www.acmicpc.net/problem/10159 와 거의 동일한 플로이드와샬 알고리즘문제입니다 ! 키를 비교할 수 있는 학생의 수는 그 학생보다 키가 작거나 키가 크거나, 이 둘중 하나는 무조건 해당되야합니다.즉, 비교하고자 하는 학생(X)은 X를 거치는 학생과 X에서 뻗어나가는 학생의 수가 총원이되어야합니다. X가 모든학생이 연결되어있어야 한다는것입니다. X와 연관이없는(x와 이어지는 노드가 없는 경우) 학생이 한명이라도 있다면, 문제의 조건을 어긋나게됩니다.! 코드> n >> m; for (int i = 0; i > a >> b; map[a][b] = 1; } for (i.. 공감수 1 댓글수 1 2020. 1. 24.
  • [백준 10159] 저울 문제출처: https://www.acmicpc.net/problem/10159 풀이대충 그래프 문제이니, 예제를 그래프로그려봅니다. 그리고 보기의 답을 보면, x와 비교할 수없는 물건의 갯수는 x에서 다른 노드로 가는길과 다른 노드에서 x로 가는 길이 없을 때만 해당합니다. 결국, 플로이드와샬로 해결됨을 알 수 있습니다. 부끄러운 얘기지만, 플로이드 코드를 작성해놓고 카운팅을하는 반복문작성에 시간을 많이 잡아먹었습니다. 헷갈리더라구요. 플로이드알고리즘이 코드도 직관적이고 이해도 쉬운만큼, 그냥 눈으로만 보고 넘어갈 때가 있었는데 이번에 많이 반성했습니다. 배운 개념은 꼭 복습을 하는 습관을 가집시다.. 코드> n >> m; for (int i = 0; i > a >> b; .. 공감수 0 댓글수 0 2020. 1. 24.
  • [백준 11403] 경로 찾기 문제출처: https://www.acmicpc.net/problem/11403 풀이플로이드 와샬 알고리즘은 매우 직관적이고 쉬운 알고리즘으로써, 이 문제에 적용할 수 있습니다.직관적으로 생각해보면, a=b, b=c 일때 a=c라는 삼단논법의 논리를 이용하자면,출발하는길->거치는길이 있고, 거치는길에서 도착하는 길이 있으면, 출발하는길->도착하는길이 존재할 수 있습니다. 따라서 이 논리를 플로이드와샬 구현에 그대로 대입하면됩니다. 코드> n; for (int i = 0; i > map[i][j]; //i=거치는길,j=출발,k=도착 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++.. 공감수 0 댓글수 0 2020. 1. 15.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.