코딩공작소

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 www.acmicpc.net 너무 억울하다 .... 하루종일 이문제에 매달렸는데 로직자체에는 문제가 없었는데 그냥 answer를 너무 작은값으로 해줘서 오류가 ..

오류가 났던 이유는 처음 상어의 위치를 그대로 9로 박아줘서 돌아가는 길이 생겼던것이다. 그리고 한 단계에서의 모든 먹이를 찾고나서 정렬을 하는 과정에서의 코딩에 문제가 있었다. BFS를 선택한 이유가 최소거리 때문이었다. 최소거리라는 말은 각 stage가 얼만큼 진행되었는지를 알려주는 것이기도 하기 때문에, 위와 같은 문제의 경우 pop되어 나오는 값이 +1이 된 시점부터 다음 stage라고 생각하면 된다. 기본적으로, 우선순위를 두고 먹이를 먹는것이므로 벡터에 저장해서 정렬을 해주었다. 이 과정에서 핵심은 먹이를 찾자마자 먹는것이 아니라 우선순위대로 먹기 때문에, 해당 stage에서의 먹이를 모두 찾은 다음 먹는것이다. 그 과정에서 stage가 필요했다. 문제 N×N 크기의 공간에 물고기 M마리와 아..

일단 문제 자체는 매우 쉬운 문제였다. 그냥 bfs를 해주는 문제였고, 조건 하나가 더 달려있는 문제였다. 그리고 갱신을 위해 그냥 각각의 위치마다의 좌표를 자료형에 보관해서 나중에 탐색 후, 업데이트 해주면 되는 문제였는데, 시간초과 발생했고 이유를 도저히 모르겠어서 넘어갔었다. 하지만 이유를 찾아버렸다. 그 이유는 다음과 같다. if문 안에 바로 조건을 넣지 않고 bool형 함수로 따로 구현했는데 그것만으로도 시간 초과가 발생했다..... (이에 대해서는 스택을 참조하고 리턴주소반환하는것등의 시간이 걸린다고 한다.....) 그리고 자료형을 생성 소멸할때 시간이 걸리므로 글로벌로 한번 선언해주고 초기화하면서 사용해주니까 속도가 400ms --> 100ms로 4배나 줄었다. 첫번째 코드가 시간초과가 났던..

일단 상반기 시험에도 멘붕이 왔었던 문제다 .. 그때의 문제는 일단 상하좌우 인접한 것만 보고 bfs에 꽂혀서 바로 bfs를 구현해버렸다. 그리고 나서 돌렸더니만 문제점이 초 단위로 탐색을 진행하는거여서 bfs는 인접하면 쭈루룩 진행되서 초단위로 실행시킬수가 없었다. 지금 생각해보니 백준 빙산 문제도 년단위로 진행되는 문제였었는데 좀 비슷한거같다... 오히려 빙산보다 쉬웠는데 빙신같이 못풀었다. ㅠㅠ. 그래서 bfs에서 조건으로 해결하려고 조건만 1시간동안 수정했었는 듯...2번문제는 생각보다 쉬웠는데 1번에서 멘붕와서 시간 다날려서 망했었다.... 그리고 문제를 자세히 읽어보면, 넓이탐색을 하는것도 아니다.. 그냥 단순히 상하좌우만 탐색할 뿐... queue조차 필요없다 그리고 멘붕왔던 것은 전부다 동..

문제를 읽자마자 BFS로 최소거리를 구해서 더해야겠다는 생각을 했다. 최소를 구해야되기때문에 BFS를 선택했다. 문제 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까? 천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사..

많이 접해본 유형이었다. 무리의 수를 세는 유형이었고, vector와 pair를 사용해보았다. bfs탐색을 하는 문제였지만, 탐색 시 높이라는 조건이 있었다. 조건에 맞는 곳만 탐색하는 유형. 간단한 특이점은 모든 높이들을 고려해서 최대값을 찾는 것이었고, 최소높이부터 최대높이까지 전부 찾아서 최대값을 구해주었다. 문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역..

C++언어도 연습해보기루 했다. C++에서는 이차배열을 동적할당으로 받아주기가 까다로워서 그냥 최대값 N을 미리 주고 선언을해서 for문을 통해 조절해서 실행해준다. 그리고 지역변수로는 할당해줄수 있는 사이즈가 좀 제한적이다. (이건 에디터설정이라고 함.) 그래서 전역변수로 설정해주면 스택오버플로우가 발생하지 않았다. 전반적으로 자바와 똑같았고, 다른 점은 pop()함수가 void형이라는것과 top()으로 그 기능을 구현해준다는 것. 빼고는 다 똑같았다. ㅋ.ㅋ 그리고 dfs구현 할때 간과하기 쉬운것 2가지를 발견했다. 1.for문을 반대로 돌아야 원하는 결과를 얻을 수 있다(오름차순으로 구할 수 있다는 말) 2.while문을 돌때 이미 방문한 점에 대해서는 넘겨주어야 한다. 다른 그래프에서 그 그래프와..

먼저, 대각선으로 이동하는 참신한 문제였다. 사실 대각선으로 이동하는 거 자체는 어렵지 않았다. 예외처리랑 여러가지 상황이 생각보다 까다로웠다. 처음에는 BFS로 생각하고 코딩을 하였는데 결과를 보니까 동시에 인접한 곳을 탐색하기 때문에 처음위치로 돌아올 수 없었다. --> 미리 map을 구현해서 결과를 생각해보자.... 그래서 DFS(깊이탐색)으로 해야겠다고 생각을 했고 구현하기가 쉽지 않았다(stack,재귀) 재귀로 구현(++,--과정 중요!!)을 하여야 겠다고 생각했고, 처음위치도 알고있어야하고, 먹은 디저트 이미 지나온 길을 모두 표시하여야 하고 시간초과 오류와 여러가지 예외상황이 있었다. 시작점으로 돌아오는 과정중에 사각형이 아니어도 돌아올 수 있는 case를 발견하였고, 사각형이 되기위해서는 ..

무엇가는 완탐으로 선택해주어야 할때는 0,1 방법을 쓴다.. ex) 벽세우기, 팀원고르기,사칙연산 등등 모든경우를 다 따져서 선택하는 경우!! 이 문제의 경우에는 처음부터 완탐이라고 생각해주고 dfs로 접근해주었다. 하지만 모든방향을 접근하지 못하고 한번만 실행되게 되는 경우를 만들고 나머지 팀에대한 함수도 세워서 꽤나 생각을 어렵게 했던 것 같다. 하지만 한 팀을 구하면 나머지 팀원들은 자동을 구해지는 것이기 때문에 한팀을 구하는 것이 중요하다고 생각했다. 한 팀을 구할 때, 처음에는 탐색을 해주면서 능력치 까지 더해 주었기 때문에 i,j를 모두 알아야하는것이 어려웠다. 배열에 팀을 구별해줄수 있게만 팀을 선택해주면 된다고 생각했고 벽세우기와 같은 format으로 해주면 되겠다고 생각했다. **무작정 ..

간단해 보이지만 나에게는 어려웠다... 일단 읽자마자 완탐을 해야겠다는 생각은 했다. 처음에는 for문으로 돌려야겠다는 생각을 했다. 연산자를 순열로 배열시킨다음 하나하나 for문으로 계산해주어야겠다고 생각했지만 순열로 나타내는게 쉽지 않았다. 완탐생각을 하면 제일 먼저 재귀함수를 생각해보는것이 좋은것 같다. *재귀함수를 사용할때 보통 파라미터로 계산할 결과를 넣어주는데 흔히 내가 했던 착각은 이미 파라미터를 넣어줄 때 계산이 되서 다음 재귀로 들어가서 return과정을 만나는데 (한단계전에서 연산이 이루어짐) 이 부분을 착각해서 함수가 돌아가는 구조자체가 헷갈렸다. 그리고 재귀를 해줄때 완전탐색을 하기위해서는 ++ , -- 과정이 필요하다. 다른 재귀에서 원상태로 복구를 해줘야 하기때문!!. 문제 N개..