본문 바로가기

Algorithm283

[BOJ]1865번: 웜홀 www.acmicpc.net/problem/1865 라이님 블로그(blog.naver.com/kks227/220796963742)의 풀이를 참고하여 해결했습니다. 임의의 정점에 대해 모두 벨만포드를 돌 수 없으므로 그래프를 BFS 탐색을 통해 컴포넌트로 나눠주고, 각 각의 컴포넌트에 대해서만 한 번씩 벨만포드를 돌면 됩니다. 하나의 컴포넌트라도 컴포넌트내에 음의 싸이클이 있다면 YES, 아니면 NO를 출력하면 됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1865.cc 2020. 9. 11.
[2020 카카오 기출] 동굴 탐험 programmers.co.kr/learn/courses/30/lessons/67260 jacob님의 풀이(velog.io/@jacob0122/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8F%99%EA%B5%B4-%ED%83%90%ED%97%98)를 참고하여 해결했습니다. BFS로 풀이를 했고, 특정 노드간에 생기는 선-후 관계를 before[], nxt[]로 표현했습니다. 또한 임의의 노드 A를 방문할 수 있었지만, 노드A와 선-후 관계에서 '선'에 위치하는 노드를 아직 방문하지 않은 경우 노드A를 waitingList라는 set에 넣어서 '선'에 위치하는 노드를 방문할 때 노드 A도 방문할 수 있도록 해줍니다. 이런식으로 BFS를 특수하게.. 2020. 9. 10.
[2020 카카오 기출] 외벽 점검 programmers.co.kr/learn/courses/30/lessons/60062 문제 해설(tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/)을 보고 해결했습니다. 가장 중요한 건 원형으로 되어 있는 곳을 어떻게 탐색할 지 방법을 찾는 거 같습니다. 해설에 나와 있는 대로 인덱스를 하나씩 밀면서 뒤로 있는 인덱스값에는 + N만큼 더해줘서 아래처럼 원형으로 되어 있는 효과를 만드는 게 중요합니다. N = 12 [1, 5, 6, 10] [5, 6, 10, 13] [6, 10, 13, 17] [10, 13, 17, 18] 그리고 나서는 dist의 크기 제한을 보면 8로 크기가 작습니다. 그래서 비트 바스킹을 통해 (예시 5명) 00000 ~.. 2020. 9. 10.
[코딩테스트 연습] 땅따먹기 programmers.co.kr/learn/courses/30/lessons/12913 dp + 슬라이딩 윈도우로 해결할 수 있습니다. 현재 칸에서 어떤 칸을 밟을지 결정할 때는 오직 '이전 칸'의 정보만 가지고 있으면 되므로 dp테이블은 dp[2][N] 크기만 가져도 됩니다. dp 점화식은 dp[i+1][N] = max(dp[i][0], dp[i][1], dp[i][2], ... , dp[i][N-1]) + score[i+1][N] 입니다. 즉, N열이 아닌 이전 칸 중에 최댓값 + 이번 칸의 값을 더하면 점화식이 됩니다. 코드: github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG12913.cc 2020. 9. 10.

티스토리툴바