키자드에 등록된 총 336개의 포스트를 확인하실 수 있습니다.
1시간 18분 컷. 이전에 짰던 소스가 어렴풋이 기억나서 비슷하게 짯으나이전 소스를 더욱 잘 만듦.numbering을 통해 index에 접근하고, 큰 index와 작은 index에 동시에 이어지면 작은 index에 큰 index 데이터를 넣고, 그 인덱스는 제거하지않고 형태만 놔둔다면,vector 인덱스가 흐트러지지 않음.이건 지금 소스 코드.
51분 컷.이전에 풀이한 알고리즘으로 풀었음.상어의 시작 나이나, map이 0인 곳은 물고기 리스트로 넣지 않는 점 등 다양한 값에서 실수하지 말기.디버깅 머리로 해보기!!
29분 컷.전에 왜 2시간이나 걸린 문제인지 모르겠다.아마도 최대 M개를 무조건 골라야 한다는 점에서 몰라서 그랬을 것이다.
50분 컷.1. dfs에 mi ni넣기!! m_idx나 n_idx 넣지마!!!!!!!!2. 이차원 배열을 dfs돌릴 때는 [][] 두번째 인덱스를 넘겨줄 때 한바퀴 돌면 0으로 돌려놔야 [][0]부터 돈다!!!!!!!!!
1시간 43분 컷.이전에 1시간만에 풀었는데 오히려 늦게 풀었다.정신이 안말짱할 때 풀어서 그런거같다.(자기전 ! ㅜㅜ) - -> 다른 사람 조언을 보았다. 역시 알고리즘 문제.4 4 8 8을 합칠 때 한 번 시행 후 8 8 8 이 되어야 하는데 벡터를 그냥 쓰다보니 16 8이 되더라..이점 유의해서 line vector를 pair로 만들어서 합쳐 만들어진 것은 표시를 해주었다..
48분 컷.다 풀고 나서 46개에서 실패하길래 차근차근 다시 살펴보니,처음 시작 부근을 visit 안했었음.
다음과 같은 경우 2번째 처럼 나와야 하나,0인 경우 처음에는 break 해줘서 올바른 답이 나오지 않았음. continue 해주면 됨.약 52분 컷,, ㅜㅜ
1시간 17분 컷.이전에 함수를 분리하지 않아서 정말 오랫동안 푼 기억이 있는데,한번에 검사한다는 생각이 아니라, 높이가 달라지면 한번 더 방문해서 검사하도록 해서소스를 내 스스로 더 알아보기 싶게 짤 수 있었다.도움이 되었다.
1시간 29분 컷. 이전보다 1시간 빠르게 풀었다.dfs + 시뮬레이션 문제.다시 푸니까.시간이 -1씩 단축되어서 나온다.마지막에 +1을 해줘서 출력했지만, 왜 -1단축되었는지 고민해봤지만 잘모르겠다.더 고민해보자초기화 해주는 것 조심! 이것 때문에 정답이 모두 0이나오는 무시무시한 실수
50분 컷.이전 보다 수행시간은 늘었지만, 알고리즘적으로 더 완벽한 코드.1.활성 바이러스 선택하는 dfs2.simulation-마지막에 바이러스가 남는경우-queue를 통해, 이미 퍼진 곳은 검사 x, 빈칸의 개수를 카운트해서 이미 찼으면 return time
1시간 13분 컷.이전보다 300ms나 단축시켰다!역시 복잡할 때는 함수로 분리하는 습관이 중요하구나.계산해보니 complexity가 5^12개나 나와서 걱정했는데, 예외처리를 잘 해주어서 시간 단축에 많이 도움된 것 같다.-이제까지 연결한 core수 + 앞으로 할 core수 < 최대 core수다음의 두가지를 작성하지 않아서 시간이 걸렸다.1. wire를 visit해준 후에 dfs 돌고나서 빠져나올 때 원래대로 돌려놓아야 한다.2. max_core 갱신해주기!
2시간 17분 컷.전형적인 시뮬레이션 문제로 어떻게 진행할지는 정확하게 정리 후 소스짜기!간단하게 소스를 짯지만,정해진 벡터 크기를 돌면서 erase할 경우 에러가 날 수 있다!정해진 벡터크기를 다돌고 erase를 따로 돌자.이전에서 1/4.5 정도의 실행시간으로 줄였다.
어제 풀다가 "와.. 내가 이제까지 뭘 공부한거지?" 생각이 든 문제.그렇게 복잡한 BFS, DFS 문제를 많이 풀어놓고 이렇게 간단한 DP 문제도 제대로 못풀다니.DP와 DFS로 같이 짜보았다.emplace == insert.(emplace가 속도가 조금 느린 대신 안전한 방법이라고 알고있음.)
1시간 33분 컷.미생물이 3개 이상 합쳐질 때 어떻게 할지 생각나지 않아 멘붕. 돌면서 가장 큰 인덱스를 map에 저장하고 나머지는 live= false 해주는 것이 아이디어.
53분 컷,그런데 이전에 푼게 시간이 더 적어서 한번 확인해보기.-> c 스타일로 풀면 그렇게 됨.
1시간 만에 풀었는데, dfs 내부에서 다시 dfs를 넘겨줄때 index를 제대로 넘겨주지 않아서 4시간 동안 풀이함..ㅠㅠ1시간 만에 작성한 풀이900ms아래는 4시간동안 변화한 풀이600ms
1. 깃허브에 올릴 폴더나 파일을 한 폴더에 넣어서 내 로컬저장소(git사용하던 장소)에 새로 만들어줌2. cmd 창을 키고 저번에 했던 것 이어서 작업 - add이렇게 add 해줌.3. commit달아주고 싶은 말과 함께 commit4. git status로 확인!5. 저장소 연결 후 올리기!6. 올라간 것 확인
습관적으로 물고기의 vector를 만들고, 나이가 작은 순서대로 나열한 후또다시 vector를 만들어 거리가 가장 작은 것 순서대로 나열한 후, bfs를 할 생각이었다.이렇게 풀다보니, 어떻게 최소거리인 물고기한테 갈 수있지? 최소거리로 못가고 돌아가서 거리가 더 멀어지면 어쩌지?하는 생각에 풀 수 없었다.다른 사람의 아이디어를 보고 1시간만에 풀수있었다.만약 자신이 쓰려는 알고리즘이 너무 복잡하고 어떻게 풀어야 할지 모르겠다면. 알고리즘을 다시 생각해보고, 더 간단하게 생각해야한다.아이디어는.상어를 기준으로 큐에 넣고 돌면서 갈수 있는 곳을 찾고, 먹을 수 있는 물고기를 찾으면 된다.큐에 넣는 것이 중요한데, 이를 이.......
이전에 카카오 시험때 core dumped 가 걸린 문제인데,lock을 기준으로 0인덱스 - m+1부터 n까지 돌려야 key배열이 lock의 첫번째부터 끝까지 순차적으로 잘 돈다.돌지 않은 곳은 visit으로 체크하지 않은 곳이므로 다시 돌려 lock의 나머지 부분도 확인해줘야한다.확인할때 cpy_key로 확인하는 것도 잊지 않는다.
1시간 30분 풀이복잡도:{입력: n*msearch_map: 4*2*5*n*mmirroring: n*m + n*mrotation: n*m + n*m}search_map: 4*(2+n*m)*(5+n*m)*(n*m) = n^3*m^3500^3 ^2땡!!!!!!!!!!!!!!!!!!!!!!! 틀림 정답은search_map:4*rotation() + 4*2*mirroring() + 4*2*5*n*m
이 문제, 상반기때 인턴 지원하여 시험치러 갔을 때의 첫번째 문제와 같다.인턴이라 동일 문제를 낸 것인지, 원래 삼성이 냈던 것을 또 내는 것인지 모르겠다.푸는 데는 3시간이 걸리지 않은 것 같다.숫자를 기록할 number와, 숫자의 등장 횟수인 cnt를 기록할벡터 num_sort를 이용하여등장횟수가 오름차순이 되도록, 등장횟수가 같으면 숫자가 오름차순이 되도록 sort 해주었다.다음의 점을 주의해서 작성해야한다.소스 코드의 전체적인 구성은소스 코드는
푸는 데 이틀 정도가 걸린 것같고,알고리즘에 대한 고민을 많이 했다.다음의 문제 때문에 알고리즘의 시간 복잡도를 줄이는 데 애를 먹었다.1. 상어가 서로 먹힐 때 벡터 연산을 하면 2중 for문으로 하게된다. 만약 상어가 10000마리 이면, 10000*10000*(전체 사람이 땅을 지나가는 시간: 최대100) = 100억 = 100초가 걸린다. 이의 복잡도를 줄이기 위해 - 정렬을 하는 방법을 생각했으나, 정확한 답이 나오지 않았고, 결국 시간 초과가 났다. 즉 10000마리의 일부를 없애는 것만으로 시간 복잡도를 줄이는 데 실패했다. -> 원자소멸 시뮬레이션에서 했던 것처럼 map을 이용한다!!2번을 응용하여, 낚시왕에서는1. 상어가 움직.......
이전에 풀다가 다음의 2가지가 제대로 되지 않아 멘붕이 왔었던 문제이다.다시 풀는데는 3시간 정도 걸렸지만,처음에 실패했기에 일주일 정도 걸린 문제이다.1. 배열을 돌면서 ni==0인 곳은 가장 첫줄이라, 왼쪽만 검사하면 되고 nj ==0인 곳은 가장 왼쪽줄이라, 위쪽만 검사하면 된다. ni==0, nj==0인 곳은 가장 첫줄이며 가장 왼쪽 줄 즉 index [0][0] 이라 그저 next_ = 1을 대입한다. 검사를 하면서 위쪽과 왼쪽을 둘다 검사하는 경우에는 다음의 세가지로 나누어지는데 -왼쪽만 만족 -위쪽만 만족 -왼쪽 , 위쪽 둘다 만족 왼쪽, 위쪽만 만족할 경우에는 그저 그 visit 값만 저장하면 되지만.......
약 1시간동안 풀이한 문제.쉬웠음.디버깅하면서 틀린 점을 소스 코드에 주석처리로 해놓음대부분 &&나 || 연산자의 문제였음!!! 그리고 배열에 인덱스를 논리적으로 제대로 못넣어서 생긴 문제였음!!
원래 푸는데 1시간 30분 정도 걸렸지만,무슨일인지 틀렸다고 해서 sum을 long long으로 바꿔보고, 배열도 long long, check 함수도 long long으로 바꿔서 고민해보다 30분이나 더 걸렸다.원래대로 int로 하니까 잘된다....뭐가 문제인거지..찾아보니 배열을 51로 수정한거 밖에 없다. 이게 왜 틀린건지 이해가 되지 않는다.
푸는데 정답이 제대로 나오지 않아 오래걸렸던 문제이다.bfs 와 dfs에 익숙하면 함수는 금방 작성할 수 있고, 시뮬레이션의 정확한 시간을 도출하는데 어려움을 겪었다.1. 마지막에 바이러스가 남았을 때는 굳이 시간을 ++해줄 필요가 없다. 빈칸이 아니기 때문. 이것을 위해 빈칸만 개수를 계산하는 cnt와비교할 최종 개수 check_cnt를 두었다.바이러스가 퍼지는 시간을 제대로 기록하지 못해 정확한 답을 도출하지 못했고,2. 결국 예제 1의 설명의 토대로 작성하여 통과할 수 있었다.//미리 cnt++이나 visit을 해주지 않고 실제 방문하여 주변에 bfs하는 것을 하기 전 방문체크!와 cnt++!3. 그리고 아래는, 순서대로 1위치와 2위치를 돌때, 2.......
이번에도 푸는 데 오래 걸렸다.시간 초과되는 문제 때문이다. 다음의 두개를 처리를 해주니 352msec로 통과하였다.1. h_idx와 n_idx로 시작점 설정해주기.사다리를 놓는 조합이기 때문에 1,3을 시행후 3,1을 시행하면 중복이기 때문에 다음과 같이 해준다.주의할점은 ni에 관한 for문을 돌고 hi 갱신후 다시 ni가 0부터 돌지 않기 때문에, 다 돌고 나서 n_idx를 0으로 갱신해준다.2. 사다리 놓은 개수 1, 2, 3을 정하고 make_line(dfs)를 도는데, 각 단계를 순서대로 시행하다가, 어느 순간 통과해서 result가 갱신되면 더 이상 진행하지 않고 전체 프로그램의 정답을 내어도 좋다.생각보다 이부분에서 시간을 더 많이 소비한다.전체 소스.......
푸는 데 3~4시간 정도 걸린듯. 띄엄띄엄 풀었고 시간 측정을 안해서 잘 모르겠음.첫 번째 생각T struct 내부 나무를 리스트로 짜버리면, 할 때마다 sort를 해야한다.sort를 할시에 complexity 소모,새로 태어나는 나무는 무조건 나이가 1인점과, 이전에 심어져있는 나무는 계속 나이가 증가하므로,queue를 이용하여 짜면 쉽다. 중간에 원소를 꺼낼 필요가 없다면 queue를 가장 먼저 생각해보자.!두 번째 생각queue로 했을 때 왜 안되서 deque으로 바꿨는지 기억이 안난다. 어째든 제약사항이 있었고,deque으로 하기로 하고 소스를 다시 짯다.덱에서 이터레이터가 안되는 줄알고 양분 섭취하여 나이+1해줄 때도 push, pop했었는데,알고 보니 1. .......
연구소3을 풀어봤다면 엄청 금방 풀 수 있는 문제!1시간 30분 컷..ㅠ주의할 점: dfs 돌릴 때, m_idx를 인덱스로 전달하고한바퀴돌면 m_idx = 0 해줘야 다시 0부터 돈다는 점!