취업 준비 및 일상

왜 잘 봄?

4시간 좀 넘어서 6문제 풀었습니다. 7번은 대충 어떤 식으로 쌓이는 지는 알겠는데, 처리를 어떻게 할지 생각이 잘 안 나더라고요. P1 알고리즘: 구현 난이도: 실버 하위? P2 알고리즘: 그리디 난이도: 골드 하위? 백준에서 비슷한 문제를 본 기억이 있습니다(링크). P3 알고리즘: 브루트포스, 구현 난이도: 실버 상위? P4 알고리즘: 트리, 애드혹 난이도: 골드 하위? P5 알고리즘: 빡구현, 유니온 파인드 난이도: 골드 중상위? P6 알고리즘: 그리디 난이도: 골드 중간? P7 모름! 시험 끝나고 치킨 먹으면서 생각해보니 될 거 같기도 한데, 당시에 5번 문제를 대략 10번 가량 꼴아박으며 AC를 받느라 육체적, 정신적 여력을 다 써서 그냥 바로 행복버튼(=테스트 종료) 눌렀습니다. 2문제가 그..

https://youtu.be/PE4vLbyOgw0 흥미롭네요

https://softeer.ai/challenge/certification/detail.do?idx=1974 Softeer 제1조 (목적) 이 약관은 현대엔지비㈜ (이하 ‘회사’)가 제공하는 Softeer 사이트의 테스트 참여에 관한 사항을 규정함을 목적으로 합니다. 제2조 (테스트 응시자의 의무) 1. 아이디와 비밀번호에 softeer.ai 지인한테 추천받은 사이트인데, 해당 사이트에서 정기 역량 진단이 있다고 해서 한번 봤습니다. 모든 문제를 푼 사람에게 Lv.3 등급 인증 자격 부여하며, 해당 등급 인증을 획득하면 현대자동차 등의 현대 계열사의 SW 분야 지원시 코딩테스트 면제라 합니다. 시험 전 공고가 뜨면 신청합니다. 선착순이라고 했는데, 이번 시험 기준으로 453명이 지원했으니 경쟁이 치열하..

를 적으면 됩니다.

바킹독님이 트라이 강의를 올려서 다시 공부했습니다. 트라이 문제를 좀 풀어본 적이 있어서 복습일 줄 알았는데, 트라이 구현 방식이 달라서 좀 새로웠네요. 이 방법을 알았다면 현대모비스 알고리즘 경진대회에 나온 트라이 쓰는 2문제에서 더 높은 점수를 받을 수 있지 않았을까? 싶기도 합니다. 기존에 트라이를 블로그를 통해 공부했을 때, 다들 구현 방법으로 Trie class를 만들어 사용하는 방법을 제시하더라고요. 그리고 Trie내의 자식 노드를 구현을 1) Map으로 하는 방법, 2) 적당한 크기의 Trie배열을 선언하는 방법으로 나눌 수 있었습니다. 위 강의에서는 처음부터 2차원 배열을 크게 선언한 다음 사용하라고 했는데, 처음 보니까 조금 생소하기도 하고 비효율적이다는 느낌(되게 안쓰는 칸이 많아요)을..

https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 딱 보고 '이분 매칭'아니야? 라고 생각을 해서 알고리즘 태그를 까서 봤습니다. 스포당해서 제대로 푼 느낌이 아니네요. 스케줄링 유형의 문제에 약합니다. 풀이 도착한 사람이 현재 갈 수 있는 게이트 중 가장 큰 숫자로 배치시켜야 합니다. 그러려면, 현재 나온 숫자에서 거슬러 올라가면서 아직 사용하지 않은 게이트 중 가장 큰 숫자를 찾으면 됩니다. 가장 먼저 생각나..

https://www.acmicpc.net/contest/view/849 2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회 (SUAPC 2022 Summer) Open Contest www.acmicpc.net 6문제 풀었습니다. 생각보다 잘한 듯? 수학적인 사고력을 요하는 문제가 많네요. A 세 정수 $x$, $y$, $k$에 대해 정답을 구하는 기댓값은 세 정수 $0$, $y-x$, $k-x$에 대해 정답을 구하는 기댓값과 동일합니다. double 이차원 배열 dp를 다음과 같이 정의합시다: $dp[l][k]$ = (최솟값이 $0$, 최댓값이 $l$인 구간에서 $k$를 찾는 기댓값) 경우의 수를 적당히 잘 나누어주어 기댓값을 저장합니다. 시간 복잡도는 O($2400^2$ + $N$)입니..

코테 수준에서 이거? 알 필요 없습니다. 근데 백준 11437번: LCA를 멍청한 구현으로 풀고 나니 살짝 허무해서, 개념을 공부하고 문제를 좀 풀어봤습니다. 개념 한 마디로 'Sparse Table'이라는 자료 구조에 각 노드의 (2의 제곱번째) 조상'들'을 저장하여 (처리 과정 O(NlogN)), 이후 LCA를 O(logN)에 구할 수 있도록 하는 방법입니다. Q번의 LCA를 찾는 과정을 naive한 풀이는 O(NQ)의 시간 복잡도 내에 수행하나, sparse table을 이용하면 O((N+Q)logN) 시간 복잡도 내에 수행할 수 있습니다. parent[cur][i] = parent[parent[cur][i-1]][i-1]의 의미를 잘 알아두면 나중 구현할 때 기억하기 좋을 듯합니다. 자세한 설명은..

https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 풀이 처음 보면 꽤 막막합니다. 케이스를 잘 나누어 각 경우마다 최적의 움직임을 수행하면 될까? 일단 케이스를 분류하는거조차 모르겠고, 각 상황별 최적의 움직임이 뭔지도 모르겠네요. 이 방법은 아닌 듯 합니다. 한 단계의 움직임을 분석해보니까, 0을 (가능한 방향의) 사방의 숫자랑 바꾸는 것이고, 이는 사방 탐색으로 구현할 수 있어 보입니다. 거기에다가 특정 상태에 가장 먼저 도착...? => BFS로 될 겁니다. 그러면, 상태 공간을 저장할 배열을 만들어야 할 겁니다. 가..