본문 바로가기

BOJ

백준 6087 / 레이저 통신 하다가 로직이 너무 무식한데? 싶으면 빨리빨리 손절하고 다시 세우자 최단경로가 아닌 방향을 최소 몇번 꺾어야 되는지 묻는 문제이다. 방법이 도무지 떠오르지 않아 다른 사람들의 코드를 참고했다. (ㅠㅠ) 로직은 이렇다. 첫번째 C(시작점)에서 4방향으로 벽이나 밖에 부딪힐때까지 선을 긋는다. (선을 그으면서 dist를 체크해준다.) 선이 그어진 부분에서 다시 4방향으로 선을 긋는다. (이미 선이 그어진 곳이라면 긋지 않는다.) 이를 반복하면 갈 수 있는 모든 빈칸에 dist가 체크되는데 도착점의 dist에서 1를 빼주면 답이다. 결국 거울의 개수를 생각하면서 푸는 문제가 아닌, 몇번의 직선으로 도착점에 도달할 수 있는 가에 대한 문제로 생각해서 풀면 더욱 쉽다. 코드 123456789101112131415..
백준 4991 / 로봇 청소기 총 n개의 쓰레기를 치우는 최소거리는 치우는 순서에 따라 다르다. 그렇기에 1,2......, 최대 10번째 쓰레기를 치우는 순서를 모두 정한 후 최소값을 구하면 된다. 총 10!(>300만)개의 경우의수가 생기니 next_permutation 안에서 bfs를 매번 돌리면 시간초과가 뜬다. 해결법은 로봇청소기와 쓰레기 n개 사이의 거리를 모두 구해놓는 것이다. 쓰레기가 10개라고 가정하면 로봇청소기와 쓰레기 사이의 거리 : 10개 쓰레기와 쓰레기 사이의 거리 : 10C2개 총 55개의 거리를 BFS로 구하면 된다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565..
백준 9328 / 열쇠 난 아직 멀었다는 생각이 들었다. 쉽게 풀 수 있는 문제를 어렵게 접근했던 것 같다. 처음엔 문제의 조건 그대로 구현하려했다. BFS를 돌리되, priority_queue를 이용하여 획득한 파일의 개수, 좌표, 획득한 키(string으로 저장), 획득한 파일의 좌표 를 계속 넘기며 정답을 찾으려 했다. 50%에서 자꾸 메모리 초과가 나서 다 지우고 로직을 새로 세웠다. 문제는 쉽다. 우선, 상근이는 빌딩 밖으로 나갈 수 있기 때문에 맵 주변에 빈칸을 생성해준다. 열쇠나 파일을 찾을 때마다 다시 0,0,으로 돌아와 bfs를 돌리면 된다. 문을 열거나 파일을 찾으면 맵을 빈칸으로 갱신하고 다시 0,0으로 돌아온다면 그 문을 지나가거나 파일이 있던 곳에 접근할 수 있다. 열쇠를 획득하는 건 map을 사용했다...
백준 9376 / 탈옥 이 문제를 단번에 풀었다면 나는 당장 하산했을 것이다. 처음 문제를 풀었을 때 여러가지 해결법이 떠올랐다. 그중 가장 그럴 듯 했던건 모든 문의 좌표를 받고 0개를 열었을 때, 1개를 열었을 때, 2개를 열었을 때 ...... n개를 열었을 때 탈옥에 성공하는 문의 최소개수를 구하는 방법이었는데. 한 케이스당 bfs를 2번씩 해야되니 시간초과에 걸렸다. 맵이 작았으면 괜찮았을 텐데.. 이 문제의 해결법은 이렇다. 죄수1과 죄수2 그리고 맵 밖에 있는 사람이 있다고 가정하자. (문제에 힌트가 있다. 상근이는 어디에나 있을 수 있다고..) 맵도 바꿔준다. 맵의 가장자리 부분에 빈공간(.)를 추가시켜준다. 그리고 죄수1과 죄수2 밖의사람의 모든 dist를 bfs로 구한다 이떄 문이 아닌 빈 공간을 지나가는 경..
백준 12851 / 숨바꼭질 2 다른 숨바꼭질 문제는 경로를 출력하는 문제였던 것 같다. 그떄 여러가지 답이 가능해서 '스페셜 저지'가 붙어있던거 같고. 이 문제는 최단경로를 출력함과 동시에 몇가지 경로가 가능한지에 대해 묻는 문제다. 최단경로를 출력하는 방법은 숨바꼭질4(https://naivep.tistory.com/22) 참고. 최단으로 갈 수 있는 경로가 몇개 있는지 알아내는 방법은 현재 인덱스까지 올 수 있는 방법이 몇개 있는지 담는 cnt[인덱스] 배열을 만들어 check가 true임에도 next의 위치에 가는 경로가 최단경로와 같다면 cnt를 늘려주는 방법이다. 그림으로 보면 5까지 가는 최단경로가 2, 9까지 가는 최단경로가 2라고 가정하자. 10은 아직 들린적 없다. 우선 5가 10에 접근한다. dist[10]은 3이된..
백준 1525 / 퍼즐 나올 수 있는 경우의 수가 총 9!. 그러나 현 퍼즐의 상태를 저장하기 위해선 (빈칸이 0이라 가정하고) 최대 876543210 짜리 배열이 필요하다. (약 4기가) 무조건 메모리초과가 난다. 이 문제를 해결하기 위해선 map이란 클래스가 필요하다. map은 쉽게 생각해서 map["string"]이나 map[92342384023] 같은 일반적인 배열이 할 수 없는 것들을 가능하게 하는 자료구조다. ( ) 문제에서 사용된 map의 기능은 count. map.count("바보")는 "바보"란 스트링이 한번이라도 들어갔으면 1, 들어간 적이 없으면 0을 출력하는 기능이다. (BFS 문제에 자주 사용되는 부울 배열의 기능과 같다.) 또한 코드는 string의 기능을 잘 이용해야 쉽게 풀 수 있다. string...
백준 1208 / 부분집합의 합 2 굉장히 어려운 문제. 부분집합의 합이라 나올 수 있는 경우의 수의 최대가 2^40. 시간초과가 난다. 그러하므로 n을 2로 나눈 후 두 경우로 나누어 해결해야한다. n을 2로 나눈 후 두 경우로 나누어 해결하는 알고리즘을 Meet in the middle, MITM이라 부른다고 한다. 1. n개의 수를 n/2짜리 배열과 n/2짜리 배열 두 개로 나누어 담는다. 2. 각각의 배열에 담긴 수의 부분집합의 합을 모두 구하여 새로운 배열 n1, n2에 담는다. 3. n1의 인덱스 하나 n2의 인덱스 하나를 합한 값을 정답 s와 비교하여 체크한다. (투 포인터스 알고리즘 이용) 여기서 가장 어려웠던 건 투 포인터스 알고리즘을 이용하는 법이다. 위의 배열이 n1, 밑의 배열이 n2라 가정하자. n1은 시작 인덱스부..
백준 1644 / 소수의 연속합 일단 n 이하의 소수를 모두 구해놓으면 투 포인터스 알고리즘을 통해 O(n)만에 답을 구할 수 있지만 n의 제한이 400만이기 때문에 400만 이하의 소수를 모두 구하는 것은 빠른 시간내에 불가능하다. 400만이하의 어떤수 i를 2부터 루트 i까지 나누어 본 다음, 나눠지지 않으면 소수로 판별하는 알고리즘이 있지만 이마저도 느리다. 해답은 에라토스테네스의 체 어떤 소수를 구하면 그 소수의 배수들을 모두 체크하는 방법이다. 에라토스테네스의 체를 사용하면 빠르게 해결가능하다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include#..

티스토리툴바