기술 블로그

https://www.acmicpc.net/problem/16932 처음에 2중 for문으로 모든 점을 탐색하여 '0'인 곳을 찾아 '1'로 바꿔 준 후 DFS를 실행하였다. 그런데 시간 초과가 떴고, 생각해보니 미리 DFS로 그룹화 시켜 그 개수를 배열에 저장해 활용하는 것이 시간 단축에 크게 도움 되었다. 코드가 조금 복잡해 보이는 건 착각이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103..

https://www.acmicpc.net/problem/16985 서울대학교 3/1 알고리즘 특강 문제 → https://www.acmicpc.net/contest/view/395 서울대학교 3/2 알고리즘 특강 문제 → https://www.acmicpc.net/contest/view/396 이 문제는 보자마자 Backtracking(next_permutation, 5중 for문), Bruteforce, BFS, Simulation의 짬뽕 문제임을 느꼈다. 우선, 총 5개의 층이 있고, 각각 4가지의 모습(회전)이 가능하므로, 4^5가 가능하다.(4*5 아님.) 그리고 총 5개의 층들을 배치시키는 경우의 수 5! 그리하여, BFS를 돌리면 총 6개의 방향으로 5*5*5의 칸들을 고려하면, 5*5*5*..

https://www.acmicpc.net/problem/13414 #include : https://hsdevelopment.tistory.com/251 어려웠다. 문제를 읽고, 이건 map을 이용할 수 밖에 없는 느낌을 받았고, 계속 map을 요리하면서(insert, erase의 활용 등등..) 그리고 vector도 요리하면서(unique 등등등...) 풀려고 몇 시간 동안 고민하였으나 결국 풀지 못 했다. 그래서 다른 분의 코드를 참고하였다. 참고하니, 내가 놓치는 부분들이 있었다. 1. map의 insert, count, erase 연산은 느리다. 그래서, 배열 형식으로 Key, Value를 저장해줘야한다. 2. K가 vector v의 v.size()보다 클 경우, 같은 경우, 작은 경우 이렇게 ..

https://www.acmicpc.net/problem/1181 C++의 map을 이용하였다. 자동으로 중복 제거 및 정렬을 해주기 때문이다. 위에서 말한 '중복 제거'라는 것은 map은 Key의 중복을 불허하기 때문에 Key값을 string으로 해주었다. 즉, string으로 해주면 다시 추가될 일이 없기 때문이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include #include #include #include #include #include #include #include #include #include #pragma warning(d..

https://www.acmicpc.net/problem/16931 쉬운 문제인줄 알았는데, 계속 제출해봐도 틀렸다고 떴다. 맞은 사람들의 코드 길이를 보니 무척 짧았다. 결국 생각해보니 해결 방법은 높이(height)를 갱신하면서, 높이 차이(Map[행][열] - height)를 이용한다. 틀린 코드 : 노가다식 하드 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596#include #include #include #inclu..

https://www.acmicpc.net/problem/16930 백준 boj 16930 bfs 시간초과 queue push 아이디어 생각 재채점 후 시간 초과가 발생했다. 계속 시간 초과가 발생하길래 다른 분의 코드에서 힌트를 얻어서 구현봤다. 최대한 덜 queue에 push하려고 했었지만, 다시는 푼 시간 초과 코드에서 결국 줄이지 못 했던 것 같다. 핵심은 T[y][x]가 INF일 때만 queue에 push하는 것이다. 즉, 아직 방문하지 않은 곳만을 탐색하는 것이다. 물론 그 전에 T[y][x]가 T[r][c] + 1보다 이상이어야 한다. T[y][x] < T[r][c] + 1일 때는 break해야 한다. 이미 최소 시간이 보장된 길인데, 굳이 탐색할 필요가 없다. 제일 처음 풀었을 당시 맞았던..

https://www.acmicpc.net/problem/16929 계속 예제 2번과 출력이 다르길래 생각해보니 cnt 변수를 전역 변수로 쓰는 바람에 52번 째 if 조건문에 통과되었다. 재귀 함수 매개변수로 써야 했는데, 실수 하였다. 그리고 visit를 어디서 어떻게 활용하느냐도 중요하다. cnt를 전역 변수로 말고, 매개 변수로 쓰고 제출하니 맞았다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include #include #include #include #..

https://www.acmicpc.net/problem/16928 굉장히 쉬운 문제인줄 알았다. 그런데 계속 틀리길래 생각보다 좀 고민했다. 틀린 이유1. 66번 째 줄의 continue;를 안 써준 것→ 예를 들어 2에서 98로 갈 수 있을 때, 1 → 2 → 98이 하나의 과정이기 때문에 98만 Queue에 push하면 된다. 굳이 2까지 Queue에 push할 필요가 없었다. 즉, 둘 중 하나만(뱀, 사다리의 이동 또는 단순 주사위의 이동) push 해야함. 2. 처음에 61번 째 줄에 if (move != -1 && !visit[move])로 썼었음→ !visit[move]를 쓸 필요가 없었다. 뱀이나 사다리로 통해 더 최소한의 방법으로 이동할 수도 있기 때문이다. 즉, BFS와 뱀과 사다리의 ..