Coding Test

1. 문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 백준 플래티넘 찍고, 아무튼 취업 준비 해야 하니 요새 코테 트렌드에 맞는 프로그래머스 줄창 풀고 있었는데 이 문제는 너무 얼탱이 없어서 정리해둔다. 15분 컷내고 다른 문제 풀려고 넘어가는데 내 발목을 1시간이나 붙잡았다. ㅡㅡ 23년 이후로 테스트 케이스가 추가된 것 같다. 다른 사람들은 어떻게 풀었는지 궁금해서 뒤져봤는데, 지금 돌려보면 전부 틀린 풀이라고 나온다. 2. 아이디어 애초에 문제 카테고리가 이분 탐색이었으니, 사용할 알고리즘을 알면 문제 해결을 위한 구현은 쉬웠다. left ..

1. 문제 설명 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 2. 아이디어 💡 사이클을 이루지 않는 최소 비용의 간선 찾기 => MST 보자마자 최소 신장 트리를 만들어야 겠다는 건 떠올리지 못 했고, 한참을 문제를 째려보다가 탐욕법으로 접근하면 되겠다 싶긴 했는데 구현이 막혔다. (각 노드가 선택할 수 있는 경로 중에 가장 비용이 작은 간선을 선택하면 되므로 탐욕법 접근이 가능하다 판단했다.) 구현이 막혔던 이유는 처음에 모든 정점의 좌표를 이용해서 간선에 대한 비용을 계산해두..

1. 문제 설명 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 푸는데 시간을 많이 소모하긴 했지만, 재밌는 문제라서 오히려 좋은 시간이었다. 2. 아이디어 보자마자 Union-find 문제라고 생각해서 15분 만에 기계적으로 코드 작성해서 제출했다. 하면서 '나...좀 천재?'이러고 있었는데, 지금 생각해보면 왜 틀린 것도 아니고, 런타임 에러가 났는지가 의문이다. 여튼 50%까진 성공했으니, 배열 크기를 잘못 잡았나 싶어서 어떤 케이스에서 오작동이 되나 살펴보던 중 그냥 아이디어 자체가 틀렸음을 알..

1. 문제 설명 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 조건 하나 잘못 읽었다가 시간 왕창 빼앗김.. 난이도 자체는 어렵지 않다. 2. 아이디어 bfs 돌리면 되겠다 싶은 건 보자마자 알 수 있을 거고 문제는 움직일 target이 여러 개가 존재할 수 있기 때문에, 그 중 최적값만 찾아야 한다. 흐름은 다음과 같이 진행될 것이다. 현재 위치에서 bfs로 다음 먹이의 위치와 위치까지 이동 거리를 계산한다. 만약, 이동하지 않았다면 반복문을 멈춘다. 아기 상어를 다음 먹이의 위치로 이동시킨다...