목록Algorithms/SIMULATION (14)
혼종 꼬지마루
문제 이름 한번 잘 지었네..... f**k만 몇번을 외쳤던가.... A+등급을 딸 때 풀었던 문제라 쉽게생각하고 건드렸다가 문제 출력조건이 조금 달라서 맞왜틀 이러고 1시간을 날려먹은 문제 문제 조건도 애매모호한 부분이 있고, 출력 답의 예시라도 설명을 해줬으면 좋았을 문제.... 먼저 출력은 2가지만 생각하면 된다. 정상 종료, loop로 인해 정상종료가 불가능한 경우 정상 종료는 문제가 없는데 loop를 설정하는거에서 문제가 많다.... 일단 풀이를 차근히 해보도록 하겠다. 먼저, 이 문제의 핵심은 [, ]일때 점프하는 index를 어떻게 잘 정해주는가이다. 간단히 stack으로 해결할 수 있다. 일단 명령어를 입력받고, 순회하며 stack으로 쌍을 지어 점프 포인트를 만들어 주면 된다. 그 외에는..
삼성전자 19년 상반기 기출이라고 해서 예~~~~전부터 풀어보려고 했지만.....귀찮아서 미루고 미루다가 드디어 풀어보았다 ㅋㅋㅋ 어려워 보이고, vector를 쓰면 편할 것 처럼 보이지만 범위가 명확하고, 굳이 vector를 쓰지 않아도 될 것 같아서 그냥 풀었다 1. 입력되는 확인할 target 좌표와 3x3행렬을 입력받는다. 2. 함수는 총 5개를 만들었다. target좌표를 확인할 함수, 행렬을 한줄씩 계산하고 바꿔줄 함수, R, C에 들어갈 각각의 함수를 만들었다. 3. for문으로 dab을 count하게 만들었고, for문이 돌 때 가장 먼저 target좌표의 답을 확인 4. R, C의 길이를 확인하여 CalR, CalC함수를 호출 5. CalR기준으로, 행을 순회하며 열의 값을 tmp_arr..
망할 미세먼지 때문에 내 차가 세차를 해도 일주일을 못가는거 같다...ㅂㄷㅂㄷ일단 망할 미세먼지가 퍼지는건 구현하기 위해서도 구조체 배열로 저장하는게 좋기도 하고... 좀 비효율적인거 같기도 하고일단 이 문제는 공기청정기를 돌리는 과정에서 너무 구현하기 귀찮아서 한 10번은 코드짜다 지웠다 한거같다어떻게든 덜 귀찮게 짜려고...그래도 일단은 일전에 풀었던 블록게임에서 아이디어를 얻었다...DFS로 좌표 끝까지 가고 돌아오면서 갱신하는 방법을 사용 1. 먼저 먼지가 퍼질 수 있는 조건 map[i][j] / 5가 1이상인 지점을 구조체 배열을 만들어 좌표와 그 값을 저장 2. 미세먼지가 저장된 구조체 배열에서 하나씩 꺼내어 4방향 검사하는데, 이때 먼지가 못퍼지는 경우(공기청정기 or 배열 범위 초과)는 퍼..
얼마전 있었던 모 기업의 코딩테스트 기출이라길래 풀어보았는데....이 문제 말고 같은 시간대의 시험이 두 문제 모두 시뮬레이션이 나오는 건 처음봤다...두 문제 합쳐서 디버깅까지 내가 2시간이 걸렸다면.... 할만 했다고 생각...개인적으로 구현이 쬐끔 까다로울 뿐 그리 어려운 문제는 아니었다고 생각한다 1. 일단 물고기들의 좌표를 구조체 배열에 저장하며, map에는 그 물고기들의 index(입력 순서 i값)을 찍어준다 2. 물고기를 문제의 조건에 맞게 시간에 따라 x축을 하나씩 이동하며 y축을 검사하고, 물고기를 잡는다- 물고기를 잡았다면 그 해당하는 arr의 death를 1로 바꾸고, map에서 index를 제거- 잡은 물고기의 크기를 dab에 더한다 3. tmp배열을 지역으로 선언한 후, arr에 ..
와...벽에 튕기는 경우가 한방향으로만 한바퀴 돈다고 계속 생각해서 계속 틀렸다... 이래서 사람이 멍청하면 몸이 고생한다고 하나보다... 리뷰를 하면서도 얼탱이가 없넼ㅋㅋㅋㅋ 일단 이 문제는 좌표계가 문제 예시1번 처럼 생각하면 백타 틀린다 즉, 입력으로 주어지는 좌표계를 그대로 사용해야한다 그 이유는 K가 0.5의 배수이기 때문에 좌표계 자체를 2배 늘려준다고 생각하면 편하다 1. map을 그대로 입력받는다 2. 주어진 map에서 블록들을 각각 그룹으로 만들어 주기 위해 BFS를 사용하여 번호를 붙인다 3. 이렇게 만들어진 visit을 map으로 사용해야한다 시작위치를 y = 2*N, x = 2*K로 잡고 시작(나는 주로 N을 y로, M을 x로 두고 사용하기 때문에 입력을 거꾸로 받음) 4. 끝까지 ..
큐를 사용하지만 시뮬에 더 가깝다는 느낌이 들어서 simulation에 분류했다. 일단, 대기 순서를 기다린다는 것에서 유명한 문제인 은행업무 기다리기? 같은 문제처럼 이분 탐색을 하던지, 직관적으로 queue를 사용하여 시뮬레이션처럼 풀지 고민하다가 그냥 범위도 작길래 queue를 사용하였다. 1. 트럭을 다리위에 올리기 전에 트럭이 빠져 나올 수 있는지를 먼저 검사한다. - 트럭이 들어간 시간과 현재 지난 시간이 다리의 길이보다 클경우 pop한다 2. 1번의 검사를 마치면 큐에 문제의 조건에 만족할 수 있는 범위 내에서 큐에 넣어준다. 3. 1, 2번의 과정을 거치지 않는다면 시간을 늘려서 순차적으로 검사한다. 12345678910111213141516171819202122232425262728293..
DFS, BFS를 모두 사용하지만 결국엔 시뮬레이션이 더 중요한 문제였던듯 하다 1. 궁수의 위치를 DFS를 사용하여 정해준다. 2. 궁수의 위치가 정해졌다면, 기존 map을 tmp_map에 복사하여 시뮬레이션 용 map을 생성 3. 각각의 궁수 위치에서 BFS탐색으로 candi에 조건에 맞는 적의 위치를 저장 4. candi에 저장된 적의 위치를 dist가 가까운 순서, x가 작은 순서대로 정렬한다 5. 한번에 한명의 적을 공격할 수 있기 때문에 candi에 저장된 것이 있다면 맨 앞의 적의 위치면 candi2에 담아준다 6. 각각의 궁수에 대해서 이렇게 탐색을 끝냈다면, tmp_map에 제거할 적의 위치에 적이 있다면 tmp++하고 적을 tmp_map에서 제거 - 이때 중복되는 적을 공격할 수 있으니..
이 문제도 똑같이 구현을 잘 해줄 수 있느냐의 문제 입력받은 데이터는 이렇게 구성되어있다. N : 게임 스테이지의 갯수stages : 순서대로 각 유저가 몇번 스테이지에 있는지 입력받고 개인적으로 편하게 구현하기 위해 구조체 배열을 선언해서 만들었다 각 유저가 도달해 있는 stage 바로 앞까지는 해당 유저가 clear한 stage 이므로 check배열을 만들어서 그 스테이지를 끝낸 것으로 간주하고, 구조체 배열에는 그 스테이지에 머물러 있는 사람의 갯수를 넣어준다. 그리고 나서 단순히 for문을 돌면서 나눠주면 끝. 이 때 주의해야할 점이 모든 유저가 stage를 clear한 경우 그 실패한 유저가 0이므로 그대로 나눠주면 runtime error가 난다 이 문제는 단순히 if문 하나로 예외처리 해주면..
상당히 구현만을 위한 문제였다.... 이 문제랑 실패율 두 문제 밖에 못풀었는데 오픈 채팅방 문제는 stl을 안쓰고 풀다가 시간초과가 계속 떠서 오래걸림... stl 쓰자마자 바로 통과!! 그냥 문제의 조건에 맞게 구현만 잘해주면 된다. map과 vector, string 만 잘 다뤄주면 된다 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include #include #include using namespace std; vector solution(vector record) { vector answer; vector tmp; vec..
문제를 조금씩 잘못 이해해서 좀 오래걸렸던 문제... 우선순위 큐를 사용하라는 말이 많았는데 나는 굳이 그렇게 특별히 알고리즘을 사용하지는 않았다 1. 초기에 주어진 양분에서 입력된 나무의 위치를 넣는다. 2. 봄이 찾아온다. 여기서 2중 for문으로 순회하며 나무가 있는 곳은 sort하여 어린 나무 순서대로 양분을 먹인다. 양분을 먹이다 남은 양분보다 많은 나이가 나오면, 그순간부터 dead 구조체 배열에 순차적으로 담아주고, 나무의 갯수와 그 map에서 죽은 나무를 제거한다. 3. 여름이 찾아온다. dead 구조체 배열에 담긴 죽은 나무들을 하나씩 map에 나이의 절반을 더해준다. 4. 가을이 찾아온다. 다시 2중 for문을 순회하며 나이가 5이상인 나무 주변의 8개 방향에 나이 1인 나무를 뒤에다 ..