본문 바로가기
반응형

알고리즘

15663번 15663번 - N과M (9) N과 M 시리즈는 같은 문제인 듯 달라서 헷갈린다. N과 M (10)을 풀고 (9)를 풀었다. 처음에는 (9) 번에서 막혔었다.. 아이디어는 같은 depth 에서 같은 숫자를 사용하면 안된다는 것! 그래서 check 배열을 만들어서 1~10000까지 숫자를 사용했는지를 체크. 그리고 used 배열을 통해서 특정 인덱스를 사용했는지 안했는지를 체크했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include#include using namespace std;int num[8];int used[8];int op[8];int n, k;void go(int depth,int befor.. 더보기
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일때는 재귀.. 더보기
5644. 무선충전 5644. 무선충전 시뮬레이션 문제. 조금 문제를 충실히 생각해봐야 했던 문제였다. 일단 내가 생각하던 x, y 좌표가 아니어서 내 방식으로 바꿔주는 부분에서도 헷갈렸다. 문제의 그림만 처음 봤을때는 BFS를 생각했지만, 문제 상에서 그냥 거리 D를 이용하면 따로 BFS를 사용하지 않아서 간단해졌다. p[i][j] 를 통해서 i 시간에 좌표들의 위치를 저장하였다, 즉 j=0 일때는 0번 사람, j=1 일때는 1번 사람의 위치가 된다. 전체적인 흐름으로는 주어진 시간을 0초부터 끝까지 돌면서 각 점에서 닿을 수 있는 BC중 가장 Power 가 쌘놈을 찾는다. 단 이 과정에서 닿 을 수 있는 BC가 여러개인 놈을 체크하기 위해, cnt 라는 갯수를 세는 변수를 추가했다. 가장 쌘놈이 교집합일 때는 케이스를 .. 더보기
15684번 15684번 -사다리 조작 이번 상반기에 대기업 알고리즘 문제로 나왔던 문제. 막상 가서 실전에서 문제를 풀 때에는 배열을 더 크게 잡아서 약간 미로탐색처럼 문제를 풀었었다. 하지만 지금 다시 보면서 생각해보니, 각 점들을 노드라고 생각하여 방향 그래프를 완성하면 문제가 쉬워진다. 근데 이 문제에서 계속 헷갈렸던게 입력값이었다.. N,M,H 가 주어지는데 나는 평상시에 N을 세로, M을 가로로 놓고 문제를 많이 풀다보니 헷 갈려서 그냥 변수를 바꿔버렸다. X축은 X로 Y축은 Y로 바꿔서 문제를 풀었다. 그리고 좌표값들을 노드 번호로 바꿔서 문제를 풀었다. 즉 세로가 3, 가로가 4인 사다리로 보았을 때, (1,1)은 1번 노드로, (1,2)는 2번 노드로, (1,3)은 3번 노드로 이런식으로 좌표를 노드.. 더보기
1247.최적경로 1247. 최적경로문제에서 나와있듯이 그냥 모든 경로를 탐색하면서 최소값을 찾아주어도 시간제한이나 메모리제한에 걸리지 않는다. 그래서 그냥 부르트포 스를 이용해서 문제를 해결했다. 한 집의 위치정보와 그 집을 방문했는지 여부를 구조체를 이용해서 만들어주었다. house 변수의 0번째를 출발하는 집으로, 1번째를 도착하는 집으로 설정하였고, 재귀함수를 이용해서 모든 경우를 탐색하였다. 재귀함수의 매개변수로 이전의 값들을 저장하면서 거리를 구하면서 재귀함수를 실행시켰다. 그리고 마지막으로 도착점과 그 이전 점과의 거리를 더해주고 정답과 비교하면서 최소값을 찾아냈다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444.. 더보기
반응형

티스토리툴바