알고리즘/SW EXPERT 썸네일형 리스트형 3184번 3184번 - 양 해당 영역마다 BFS를 이용해서 문제를 풀 수 있었다. 처음에 탈출하는 영역 예외 처리를 해줘야 한다고 생각했는데, 문제를 읽어보니 양과 늑 대는 모두 영역 안에 존재한다는 조건때문에 그냥 각 영역에서 BFS를 실행하면 되는 문제였다. 각 영역에서 BFS를 실행하여, 해당 영역의 양의 수와 늑대의 수를 구하고, 늑대가 많거나 같으면 늑대를 최종 늑대 개수에 더해준다. 그 반대 의 경우에는 양의 수를 최종 양의 개수에 더해준다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include#i.. 더보기 4534. 트리 흑백 색칠 4534. 트리 흑백 색칠 모든 경우를 탐색하는 것은 시간이 너무 오래 걸린다, 하지만 생각해보면 트리 순회처럼 재귀적으로 문제를 해결 할 수 있어 보였다. 그리고 최적 부분 구조라는 판단이 섰기 때문에, DP를 이용하여 문제를 풀어나갔다. 점화식은 'D[node][color] 로 node 에서 color 를 가질 때, 가질 수 있는 최대의 색칠 방법의 수' 라고 정의하였다. 이러한 점화식에 입각해서 생각해본다면, D[node][흰색] = D[next][검은색] + D[next][흰색] D[node][검은색]=D[next][흰색] 이 된다. ###문제를 겪으면서 빠졌던 문제점### 처음에 계속 문제에서 빠뜨렸던 부분은, 한 노드에서 자식 노드가 2개 이상일 때에는, 자식 노드들의 최대 색칠 방법의 수를 .. 더보기 4583. 세븐 카드 섞기 게임 4583. 세븐 카드 섞기 게임 문제 자체가 쉬워보였지만, K값이 10^12 이기 때문에 시간을 단축하는게 아주 중요한 문제라고 생각했다. 그래서 어떤 규칙이 있을까 생각해보다가, 단순하게 따로 수학적인 규칙이나 증명이 있을 수 없을 것 같다고 생각을 했다. 그렇다면 문제의 조건에서 풀기 위해서는 반드시 맨 처음의 값이 카드를 섞으면서 다시 중복해서 나와야한다고 생각했다. 그래야지 그때를 기준으로 K값을 나머지 연산으로 줄여 풀 수 있기 때문이었다. 그래서 while 문을 통해서 맨 첫번째 0123456 이 아닌, 그 다음 0123456 이 존재하는지 여부를 확인하고 그 때의 값을 m2에 저장하였다. 그리고 while 문을 빠져나오면 K를 m2 로 나눈 나머지 값으로 변경시켜준다. 그리고 위의 while.. 더보기 5432. 쇠막대기 자르기 5432. 쇠막대기 자르기 이 문제는 스택을 이용하여 문제를 풀 수 있었다. 주어진 문자를 하나씩 순서대로 스택에 담아가면서, ) 이게 나오면 스택에서 팝을 시켜준다. 이때 스택에 남아있는 원소들의 갯수가 잘려진 쇠 막대기들의 갯수가 된다. 하지만 고려해야할 예외사항이 있다. ( ) 나왔을 경우와 ) ) 나왔을 경우는 다른 케이스이기 때문이다. ( ) 나온 경우에는 위의 방식대로 지금까지 모든 막대가 레이저에 의해서 잘리는 경우이므로 스택의 사이즈만큼 정답에 더해준다. ) ) 나온 경우에는 레이저에 의해 잘리는게 아닌, 막대기의 길이가 끝나서 생기는 것이므로 길이가 끝나는 막대 1개를 정답에 더해준다. 123456789101112131415161718192021222324252627282930313233.. 더보기 5648. 원자 소멸 시뮬레이션 5648. 원자 소멸 시뮬레이션 최악의 경우를 떠올려봐도...시간통과될 것 같은데 왜 안되는것인지 모르겠다...ㅠㅠ SW EXPERT 에 질문을 올렸더니, 한분께서 STL QUEUE 가 속도가 느린것 같다고, 배열로 만들어서 해보면 통과라고 했는데 정말 됐다. 어떠한 이유인지 정확히 모르겠으나, STL 의 QUEUE가 삽입,삭제 연산이나 이런부분에서 속도가 좀 저하되는 것 같다. 이 문제는 푸는 과정에서 시간초과가 정말 많이 났다. 맨 처음에는 생각했던 방식은 1. 모든 점들을 이동 → 2. 겹쳐지는 점들을 다시 탐색 → 3. 겹친점들 제거 → 4. 맵 초기화 방식 으로 순서적으로 진행하였다. 하지만 시간초과 해결을 못해서 이리저리 낑낑대고 인터넷으로 다른 분들 보면서 최적의 정답 코드로 수정했다. 그러.. 더보기 5653. 줄기세포배양 5653. 줄기세포배양 아이디어를 캐치하지 못해서 굉장히 헤멘 문제.. 일단 처음에 맵의 사이즈를 어느정도로 잡을지도 고민해야했던 문제. 맵의 사이즈는 최대 50x50 이 되고, 그 테두리가 1로 둘러싸여 있을때 (1일 경우 가장 빨리 먼곳으로 번지므로), 2시간당 1칸씩 늘어나게 되고, 시간은 최대 300이므로, 최대 150까지 사이즈가 늘어난다. 따라서 가 장 많이 줄기세포가 번져도 200x200 안에 들어가게 되므로 그것보다 크게 해주면 된다. 내가 캐치 못한 간단한 '하나의 셀을 두개의 세포가 번식하려고 할때 생명력이 큰 놈이 셀을 차지한다.' 는 부분이었다. 이 부분을 다른 분의 아이디어를 보고 풀게되었다. 큐를 10개를 사용해서, 가장 큰 생명력을 가진 줄기세포를 먼저 옮기다는 점. 처음에 큐.. 더보기 5658. 보물상자 비밀번호 5658. 보물상자 비밀번호 단순한 시뮬레이션 문제였다. 이전 문제들보다 정답률이 낮은데, 개인적으로는 훨씬 간단한 문제인 것 같다. 기본적으로 N의 최대값이 28이기 때문에 , int 형 변수로도 충분히 통과할 수 있기 때문에 따로 long long 은 쓰지 않았다. 그냥 주어진 문자를 10진수로 변환시키고, 변환한 값들 중에서 10번째 값을 찾으면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include#include#include#in.. 더보기 5656. 벽돌깨기 5656.벽돌깨기 이게 맞나 싶을 정도로 지저분하게 푼 것 같다... 일단 기본적으로 완전탐색 + 시뮬레이션 문제 같은데.. 시뮬레이션을 엄청 지저분하게 푼 것 같다.. 기본적인 흐름은, 구슬을 최대 4번까지 할 수 있으므로 가로축에서 모두 굴려보는 방식의 완전탐색을 이용했다. 나한테 까다로운 부분을 시뮬레이션 부분이었는데.. 이 부분은 분할정복과 흡사하게 재귀를 이용하였다.. 혹시 스택오버플로우가 나지 않을까 했는데 역시나 스택오버플로우가 발생하였다. makeMap() 이라는 함수 부분에서 분할정복 재귀를 이용하였는데, 구슬이 오는 시작점을 기준으로 상,하,좌,우 를 모두 하나씩 이동하면서 그 그 이동하는 지점에서 다시 재귀함수를 실행하도록 구현하였다. 스택오버플로우는 범위값 지정해주고, 0일때는 재귀.. 더보기 이전 1 2 3 4 5 다음