분류 전체보기 (124) 썸네일형 리스트형 PS 일기 4월 5주차 중간고사 시험과목이 하나, 코딩테스트도 하나, 주말에 수업도 하나 + 발표 준비까지 낀 주차라 상당히 정신없는 5주차 PS 일기입니다. 1289 트리의 가중치 정확한 풀이에 대해 설명을 들었고, 예시 출력까지 잘 되었지만 WA를 받았습니다. 이는 입력을 받을 때 임의로 간선의 방향을 정해서 받았는데 일단 이 점이 문제라고 힌트를 받았습니다. 따라서 간선 입력을 양방향으로 받고 1번 정점을 시작으로 dfs를 돌려 각 정점의 자식 정점들을 모두 찾아주었습니다. D(u) : 정점 u를 루트로 하는 서브트리에서 u를 끝으로 하는 경로의 가중치 위와 같이 dp 배열을 정의하고 아래와 같은 점화식을 세웠습니다. $D(u) = \sum\limits_{1\leq i\leq k} (D(v_{i} * W_{u,v_{i}}.. PS 일기 시작 지금까지는 문제 풀이에 대해서만 간략하게 블로그에 올렸지만, 앞으로는 주차마다 PS 일기를 따로 적어보려 합니다. 매번 문제를 다 해결하는 것도 아니며, 예제 출력에서조차 막히는 상황이 있는데 이런 경우에는 아무런 기록조차 남기지 못한다는 점이 너무 아쉬워 문제 접근 방법과 어디서 막혔는지에 대해서도 "일기"처럼 기록하려 합니다. 따라서 이 PS 일기는 독자에 따라 전혀 알맹이 없는 내용으로 느껴질 수 있으니 이 점 양해부탁 드리겠습니다. *여전히 "주차별 문제풀이"는 따로 올릴 예정입니다. 긴 글 읽어주셔서 감사합니다.🙇🏻♂️ 네이버 1차 코테 후기 시험은 토요일에 있었지만 사정이 있어 이제야 후기를 올립니다. 결론부터 말하면 이번엔 망했습니다ㅠㅠ 총 4문제 2시간 시험으로 1번 구현, 2번 문자열 구현, 3번 정렬후 투포인터, 4번 bfs 등으로 풀이고 예상됩니다. 저는 4문제중 1솔을 했고 2,3번에서 이미 막혀 4번까지는 가지도 못했습니다. 규정상 자세한 내용을 담을 순 없지만, 간략하게나마 느낀점을 남겨 보자면.... 더이상 모르는 알고리즘에서 문제가 출제되는 일은 없지만, 이미 아는 내용을 가지고 익숙하게 문제를 해결하는 능력이 많이 부족하다 느낀 시험이었습니다. 물론 모든 문제를 다 풀어 볼 수는 없겠지만, 문제에서 요구하는 알고리즘을 구현하는데에 있어서는 많은 연습이 필요하다고 느꼈습니다. BOJ 문제풀이 (W27) 무려 2주만의 PS입니다!! 그간 코딩테스트와 중간고사가 겹쳐서 못하고 있었는데 시간 비면 짬짬이 해야겠습니다. 4학년 올라오니까 거의 매주 시험입니다 😭😭😭 16325 king's color 트리 dp 문제입니다. 간선이 주어지는데 문제 풀이와는 전혀 관계없습니다. 어떤 정점이든간에 2가지 경우만 생각해주면 됩니다. 어떤 정점 u를 색칠했을때, 그 색이 다른 정점을 칠할때도 사용되는 경우와 그렇지 않은 경우가 있습니다. 이때 F(i, j) 를 i개의 정점을 j개 이하의 색으로 칠하는 경우의 수라고 정의하면 후자의 경우 $K*F(N-1, K-1)$ 입니다. 정점 u를 칠하는 경우 k개, 나머지 정점들을 k-1개의 색으로 칠해주는 경우 전자의 경우 $(K-1)*F(N-1, K)$입니다. 정점 u를 부모와 .. CF 717 D2 후기 너무 졸려서 1솔하고 자러갔습니다.... 1035인데도 11시 넘어가니까 눈이 감기네요ㅎㅎ A. Tit for Tat 제일 앞에 있는 원소를 감소시키고 맨 뒤에있는 원소는 증가시키면 자연스럽게 사전 역순으로 정렬을 할 수 있다는 관찰로 풀었습니다. int idx = 0; for (int i = 0; i n-1) break; if (arr[idx] > 0) { arr[idx]--; arr[n-1]++; } else { idx++; i--; } } 이런식으로 인덱스를 하나씩 전진시키면서 문제를 해결했습니다. B. AGAGA XOOORRR 대회중에 풀지 못하고 끝나고 나서 해설보면서 업솔한 문제입니다. 풀이를 보고 푼 문제라 풀이의 정당성에 대해서는 의문이 있지만, 풀이를 .. 카카오 커머스 2차 후기 완전 망했습니다.... 문제는 예상 범위 안에서 난이도만 조금 높은 수준으로 출제되어 나름 히트였는데 구현에서 완전 망했습니다. 특히 원인을 알 수 없는 Import 에러를 시험이 끝날 때 까지 잡을 수 없었습니다. 분명 올바르게 경로를 적고 import했는데, default로 주어진 java 파일 이외에 임의로 만든 java 파일은 import시 모두 symbol을 찾을 수 없다는 에러가 나왔습니다. 나름 출제 의도를 정확하게 파악하고 시험에 들어간건데 환경 설정 관련한 문제로 망해서 망연자실입니다. 아무튼 2차 시험 주제는 시스템 디자인이었습니다. 너무 아쉽습니다.... 카카오 커머스 1차 합격 사실 올솔이라고는 했지만, 코딩테스트의 성격상 실제 결과를 알려주지는 않았기 때문에 걱정이 되었는데 합격을 통지받았습니다. 특히 2번 문제에 제출한 솔루션의 시간복잡도와 3번 문제의 풀이가 정해와 다를것 같아 고민이었는데 다행입니다. 2차는 4/10 토요일에 4시간동안 진행됩니다. 언어 제한에 대한 안내는 없지만 특이하게 프로그래머스에서 VScode 환경을 제공해주는데 이를 이용하여 제출을 해야하며, 외부 IDE 사용 가능하다고 합니다. *자바로 진행되고, 스프링부트+JPA를 사용한다고 합니다.(IDE는 VScode) 합격 통지가 시험 4일전에 와서 시간이 많이 촉박하네요. 소중한 기회인 만큼 잘 해보겠습니다. BOJ 문제풀이(W26) 15565 귀여운 라이온 인형의 갯수를 누적합으로 구해주고, 투포인터를 이용하여 인형이 K개 이상인 가장 짧은 구간을 찾아주면 됩니다. 이때 투포인터는 end를 하나씩 늘려 가면서 각각의 end를 끝으로 하는 인형이 K개 이상인 가장 짧은 구간을 찾을 수 있습니다. for (int e = 1; e =k) s++; else break; } if (sum[e] - sum[s-1]>=k) len = min(len, e-s+1); } 찾아준 구간이 정말 K개 이상인 구간인지 보장못함으로 마지막에 값을 갱신할때는 이를 체크해주어야 합니다. 다른 풀이로는 구간의 인덱스를 활용하는 풀이가 있습니다.(선생님이 알려주신 풀이입니다) 예전에 풀었던 17844 복붙하기 문제에서 비슷하게 사용했던 테크닉같은데 구현이 아주 짧.. 카카오 커머스, 데브 매칭 후기 1시간 텀을 두고 같은 날 코테가 있었습니다. 결과부터 말하면 카카오 올솔, 데브매칭은 2솔입니다.(4문제중 2솔) 특이 사항으로는 두번의 코테 모두에서 cpp 사용이 제한되었습니다. 카카오는 자바, 데브 매칭은 파이썬을 사용했습니다.(카카오는 자바만 가능했습니다) 카카오 커머스(3문제) 2시간 시험이었고 40분 남기고 올솔했습니다. 1번 그냥 구현문제였고 N이 10만이었는데 $O(N)$안에 해결 할 수 있었습니다. 길이 N짜리 chck 배열을 만들어서 갯수를 카운팅했습니다. 2번 비트마스킹에 완탐을 이용해서 풀었습니다. $O(2^{15}N)$정도로 구현했는데, 구현 미스로 뒤에 상수가 하나 더 들어가서 시간안에 돌아갈지는 모르겠습니다. 3번 다익스트라에 경로추적을 이용하여 문제를 해결했습니다. 이 문제.. 명제 논리 진리표 p q p ∧ q p ∨ q p → q p ↔ q T T T T T T T F F T F F F T F T T F F F F F T T p이면 q이다(implies, if p then q) 오직 p인 경우에만 q이다(p if and only if q) 위 2가지를 제외하고는 진리값이 직관적입니다. p이면 q이다의 경우 ~(p ∧ ~q)입니다. p ↔ q의 경우 ~(p ∧ ~q) ∧ ~(q ∧ ~p)입니다. 나중에 2-sat 구현할때 필요한 내용인데, 저는 이를 모르고 구현하여 애먹었습니다. 이전 1 ··· 5 6 7 8 9 10 11 ··· 13 다음
