취업 준비 및 일상

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/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번의 다익스트라, 음수 간선은 벨만 포드를 돌려 각자 따로 처리한 후 반복문으로 음수 사이클이 있나 확인해보려고 했..

https://www.acmicpc.net/problem/17367 17367번: 공교육 도박 공교육의 수호자 수찬이는 공교육의 정수라고 할 수 있는 한국정보올림피아드의 문제를 가지고 게임을 하려고 한다. 수찬이는 2010년도 한국정보올림피아드 시·도 지역본선 중등부 1번 문제를 www.acmicpc.net 풀이 dp[i][j][k][n]을 '처음 주사위를 3번 던져 나온 눈이 i, j, k이고, 던질 수 있는 기회가 n번 남았을 때의 기댓값'이라고 정의합니다. 그러면 dp[i][j][k][n] = max((주사위를 한 번 더 던지고, 기회가 n-1번 남았을 때의 기댓값), (i, j, k일 때의 점수))가 됩니다. 자세한 풀이는 에디토리얼를 참고하세요 코드 1 2 3 4 5 6 7 8 9 10 11 1..

https://www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net 그 유명한 '습격자 초라기' 문제입니다. DP 문제라는건 예전에 들어서 알았는데도 풀이 접근조차 못하겠더라고요. 그래서 casterian님의 풀이를 봤습니다. 이 분 글 퀄리티가 좋습니다. cf) 안 되는 풀이 처음에 풀이 아이디어를 대충 본 후, '1~N열에서 최솟값, 2~N열 + 1열에서 최솟값을 구하여 두 값의 최솟값이 정답이 되지 않나?' 라고 ..