기술 블로그

https://www.acmicpc.net/problem/16958 다익스트라 : https://hsdevelopment.tistory.com/389 # jh05013 # 복습 # 구현 # 생각 # 필수 # 아이디어 # 맨하탄 # 맨하튼 # 거리복습 필수 다익스트라 플로이드 코테 코딩 추천 bfs로 풀려다가, visit 방문 처리가 복잡할 것 같아서 다익스트라로 풀었다. vector p하고 우선순위 큐인 pq의 first, next 구분을 잘 하자. 또한, 무작정 텔레포트 시간을 넣는 것이 아니라 실질적인 거리와의 비교를 통해 더 작은 것을 넣어야 한다. 그런데, 다익스트라로 푸니 시간이 무려 1132ms나 걸렸다. 플로이드 와샬도 868ms나 걸렸다. 하지만 채점 현황을 보니 0ms 코드도 있었다. 더..

https://www.acmicpc.net/problem/16954 # 복습 # 추천 # bfs # 필수 # 코딩 # 코테 # 구현 # 생각 3차원 방문 visit 배열을 활용하는 문제이다. 주의할 점은 현재 위치에 서 있을 때는 방문 처리 여부와는 상관 없이 무조건 queue에 넣어야 한다. 이유는 어떠 한 경우에서 (r, c)에서 현재 위치에 서 있었을 때, 방문 처리를 하면, 다른 경우에서 (r, c)에 대해 그 자리에 있을 수 없다. 이 외에는 방문 처리를 이동 방향에 따라 표시해준다. visit[행][열][이동 방향] = 어느 방향에서 (행, 열)로 왔는지 방문 처리 123456789101112131415161718192021222324252627282930313233343536373839404..

https://www.acmicpc.net/problem/18291 https://www.acmicpc.net/problem/1629 n이 4일 경우, 1001110110111111 이렇게 4개를 생각할 수 있다. 여기에서 시작과 끝을 제외하면, 00100111 이고, 이것은 bit 연산을 생각할 수 있다. 즉, bit가 2일 때, 나올 수 있는 총 경우의 수는 2^2이고, 2^(n-2)이 답임을 알 수있다. (예시)000100010001011110101111비트 수 = 3, 총 개수 = 2^3 하지만 숫자가 워낙 클 경우 단순히 2^(n-2)의 작업을 할 때, Stack Over Flow나 O(n)의 시간이 걸리게 된다. 하지만, 나머지를 적용할 수 있고, O(log n)의 알고리즘이 있다. 여기에서 ..

https://www.acmicpc.net/problem/11967 # 복습 # 추천 # bfs # 필수 # 코딩 # 코테 # 구현 # 생각 처음에는 단순히 현재 위치(x, y)에서 킬 수 있는 방을 모두 키고, 모두 방문하는 식으로 구현하였으나, 틀렸다. 왜냐하면, 불을 켜도 방문할 수 없는 방이 있기 때문이다.(상, 하, 좌, 우로만 이동) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104..

https://www.acmicpc.net/problem/18430 # 탐색 # dfs # 복습 # 구현 # 브루트포스 # 추천 # 코딩 # 코테 # 백트래킹 # back 백트래킹 문제이다. 현재 좌표에서 방문하는 경우, 방문하지 않는 경우까지 모두 고려해준다. 나머지는 주석 참고 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116..