취업 준비 및 일상

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

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 딱 보고 '이분 매칭'아니야? 라고 생각을 해서 알고리즘 태그를 까서 봤습니다. 스포당해서 제대로 푼 느낌이 아니네요. 스케줄링 유형의 문제에 약합니다. 풀이 도착한 사람이 현재 갈 수 있는 게이트 중 가장 큰 숫자로 배치시켜야 합니다. 그러려면, 현재 나온 숫자에서 거슬러 올라가면서 아직 사용하지 않은 게이트 중 가장 큰 숫자를 찾으면 됩니다. 가장 먼저 생각나..

코테 수준에서 이거? 알 필요 없습니다. 근데 백준 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로 될 겁니다. 그러면, 상태 공간을 저장할 배열을 만들어야 할 겁니다. 가..

https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 풀이 '뭔 LCA여' 할 수 있겠지만, 질문 게시판의 글에서 알 수 있듯이 naive한 구현으로도 풀릴 수 있도록 설계한 문제입니다. M번의 쿼리마다 최소 공통 조상을 찾는데 순회해야하는 횟수는 최대 O(N)이므로, O(MN)으로 가능합니다. 다만 저는 각 정점 별 parent만 기록한 후, 처음 정점에서 위로 쭉 올라가면서 방문한 정점을 Set에 넣어주고, 두 번째 정점에서 올라가다 Set..

https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 나의 접근 방법 숫자도 작고, 케이스도 얼마 안 많을 거 같아서 경우 나눠주면 될 거라고 생각했습니다. 그런데 경우 나누는게 꽤 빡세더라고요. 못 하겠어서 알고리즘 분류를 보고 풀었습니다. 풀이 A, B, C A ret[2][0] = Math.min(a+b, A); ret[2][1] = Math.max(b-(A-a), 0); ret[2][2] = c; // B -> C ret[..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 나의 접근 방법 N = 10000, M = 100000이므로 O(N^2)보다 작은 시간복잡도를 갖는 풀이가 있을 거라 생각했습니다. 시작점을 기준으로 특정 점까지 가는 거리를 구하는 문제이기에, 다익스트라에서 로직을 살짝 바꿔주면 될 거라고 생각했습니다. 한 번 틀렸는데, min을 써야할 곳에 max를 쓰는 실수를 고치니 정답을 얻었습니다..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 나의 (실패한) 접근 방법 1. 플로이드는 O(N^3)이라 일단 제외했습니다. 다만, 풀고 다른 사람의 코드를 보니 플로이드도 아슬아슬하게 제한 시간 내에 도는 거 같습니다. 2. 이후 '음수 사이클이 존재하나 확인하면 된다'는 생각에(아이디어는 맞았죠.), 양수간선은 N번의 다익스트라, 음수 간선은 벨만 포드를 돌려 각자 따로 처리한 후 반복문으로 음수 사이클이 있나 확인해보려고 했..