혼종 꼬지마루

왜 됬지?라는 생각과 함께 풀었다......죽자고 예외잡고....hard coding하기 싫어서 이것저것 했는데 자꾸 안되니까 짜증나서 혹시나 하고 제대로 되는거도 hard coding으로 바꿔서 코드가 뭔가 길어졌지만....결론은 되는걸 올림....ㅂㄷㅂㄷ안되길래 에이씨.....하고 roll back시켰더니 통과된 희한한 문제였다 1. 간편하게 만들기 위해 1~9까지 적힌 map을 생성 2. L의 크기에 따라 pattern 순서를 입력 받으면서, 중복된 숫자가 있으면 바로 NO를 출력하고 종료 3. arr[0]의 좌표를 시작으로 dfs 탐색을 시작한다 4. 탐색 중, map[y][x]가 순서에 맞지는 않지만, 방문 했던 점이라면 그 진행방향으로 한번 더 이동시키고 dfs를 다시 던져준다. 방문하지 않았..

알고리즘 단톡방에 어떤분의 요청으로 stl map이나 hash를 사용하지 않고 푼 코드가 있냐고 물어보길래 trie를 사용해서 풀어보았다 1. N개의 문자열이 들어오는 순서대로 TRIE안에 넣어준다. - 이때 마지막 문자열의 길이가 끝날 때는 NODE의 end를 true로 바꾸어 노드가 끝났음(문자열의 마지막)을 표시한다. 2. 이 후 M개의 문자열이 들어오는 순서대로 N개의 문자열이 들어 있는 TRIE에 넣어 비교한다. 3. 문자열이 탐색하다가 next 문자가 NULL포인터를 가지거나, 문자열이 끝났음에도 end가 false인 경우는 그냥 리턴 4. 찾을 경우에는 dab_cnt를 하나 늘려서 리턴한다 5. check함수를 모두 빠져 나왔을 때 답을 찾은 것인지 체크하기 위한 check_num과 비교하여..

말 그대로 최대 정사각형의 크기를 구하는 문제 주어진 map에서 최대로 정사각형이 되는 크기의 너비나 높이를 구하면 됨 1. map을 순회하면서 dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]의 최소 값을 구한다 - 이유는 저 3개의 포인트는 각각 정사각형의 크기를 가진 값을 저장하기 때문 - 하나라도 작으면 작은 사이즈의 정사각형을 넣어 주어야 하기 때문이다.ex) 0 1 1 0 0 0 1 1 0 0 0 1 1 1 0 ----->>>>> 0 1 4 1 0 0 1 1 1 0 0 1 4 4 0 0 1 1 1 0 0 1 4 9 0 2. 최소값의 너비나 높이를 구하기 위해 sqrt해주고, +1해 준 뒤 다시 제곱하여 dp[i][j]에 넣어준다. 3. 시간 복잡도는 O(N^2)이..

망할 미세먼지 때문에 내 차가 세차를 해도 일주일을 못가는거 같다...ㅂㄷㅂㄷ일단 망할 미세먼지가 퍼지는건 구현하기 위해서도 구조체 배열로 저장하는게 좋기도 하고... 좀 비효율적인거 같기도 하고일단 이 문제는 공기청정기를 돌리는 과정에서 너무 구현하기 귀찮아서 한 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. 끝까지 ..

기존 값을 저장하고, 그걸 불러와야 답을 구할 수 있다... 그래서 메모이제이션이 중요하기 때문에 DP라고 생각함 1. 순차적으로 map을 검사하면서 방문하지 않은 지점이라면 DFS로 탐색 2. 방문한 지점이라면 그 방문한 지점의 값을 반환 3. 이렇게 끝까지 같다가 돌아오면 리턴된 값과 답을 비교하여 답을 찾아준다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #define MAXSIZE 1002using namespace std; char map[MAXSIZE][MAXSIZE];int visit[MAXSIZE][MAXSIZE];int dx[] = { 0, 0, -1, 1 };int ..

큐를 사용하지만 시뮬에 더 가깝다는 느낌이 들어서 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에서 제거 - 이때 중복되는 적을 공격할 수 있으니..

전형적인 Brute Force 문제이다. 색종이를 큰사이즈부터 가능한 위치에 붙여넣고, 모두 붙였다면 최소값을 찾는 문제 원래 나는 stl을 안쓰고 문제를 푸는것을 선호하지만, 이 문제는 안쓰고는 시간초과가 날 것 같아서 vector를 사용했다 1. map을 순회하며 색종이를 붙일 수 있는 위치를 찾는다. 2. 큰사이즈(5x5) 부터 작은 사이즈(1x1)를 차례대로 붙이면서 다음으로 넘어간다. 3. 만약 더이상 붙일 자리가 없다면 최소값을 갱신 4. 붙이는 갯수가 답보다 커진다면 return 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include ..