dev-hunmin

programmers.co.kr/learn/courses/30/lessons/42890 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr - 접근법 후보키의 성질은 다음과 같다. 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다. 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이..

www.acmicpc.net/problem/1298 1298번: 노트북의 주인을 찾아서 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 www.acmicpc.net - 접근법 각 노드들이 선호하는 방번호가 있고 최대한 많은 노드들을 각기 다른 방에 1개씩 넣는 법을 묻는 문제이다. 즉, 단순한 이분매칭으로 해결할 수 있다. 문제에서 주어진 노드들의 개수(N)도 100으로 여유있고 간선들의 개수(5000)도 여유있으므로 단순하고 빠른 DFS로 해결할 수 있다. 로직은 간단히 말하면, 탐색하는 노드가 선호하는 방 번호에 '비어'있다면 바로 매칭시켜주고 누가 점거하고 있다면..

www.acmicpc.net/problem/2376 2376번: 단말 정점들의 거리 첫째 줄에 단말 정점의 개수 n(2≤n≤1,000)이 주어진다. 다음 n-1개의 줄에는 차례로 1, 2번 단말 정점 사이의 거리, 2, 3번 단말 정점 사이의 거리, …, n-1, n번 단말 정점 사이의 거리가 주어진다. 다 www.acmicpc.net - 접근법 이진 트리에서 각 단말 정점들의 거리를 가지고 트리 전체를 복원하는 문제이다. 이진 트리는 부모가 자식을 항상 2개씩(왼쪽노드,오른쪽노드)를 가지기 때문에, 단말 정점들의 거리에서 거리가 2인 경우가 항상 존재한다. 단말 정점의 거리가 2라는 것은 같은 부모(조상)을 가지고 있다는 얘기이므로, 이 두 단말 노드들을 공통된 부모(조상)으로 묶어주고 그 노드를 다시..

programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 programmers.co.kr - 접근법 취약 지점의 개수가 최대 15개까지 주어지고, 투입할 수 있는 친구의 수는 최대 8명까지 주어진다. n은 200까지 주어지지만, 문제를 잘 읽고 생각해보면 결국 고려해야할 부분은 취약 지점들 사이의 간격들이기 때문에 n은 간격 계산에만 한번 사용되지 알고리즘 선택에는 영향을 끼치지않는다. 그러므로 우리에게 영향을 주는 2개의 변수의 최대크기를 보아하니, 완전탐색으로 ..

programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr - 접근법 사람 한명이 지날 때 마다 배열의 각 요소가 1씩 감소된다. 그렇게 여러명이 지나가게 되면 결국 언젠가 그 요소는 0이 되고 그 돌을 무시하고 지나갈 수 있는 최대 거리는 k로 주어진다. 즉 사람이 지나갈 때 마다 배열의 각 요소가 1씩 감소되고 결국 0이 되어버린 돌들을 다음 사람이 0이 된 돌들을 최대 k개 만큼 무시하고 지나갈 수 있는 최대 사람 수를 구하는 것이다. 가장 쉽게 생각할 수 있는 방법은 사람1명부터 +1하면서 못지나갈때까지 탐색하는 것인데 각 배열의 원소값이 ..

programmers.co.kr/learn/courses/30/lessons/68937 코딩테스트 연습 - 트리 트리오 중간값 5 [[1,5],[2,5],[3,5],[4,5]] 2 programmers.co.kr - 접근법 이 문제에서 가장 중요한 것은 중간값의 의미를 평균값으로 오해한다면 자칫 문제가 더 어려워진다.. 문제의 예시에서 나오는 세 값중의 중간값, 즉 정렬된 값 A,B,C가 있다면 중간값은 B이다. 따라서 각 A,B,C의 값은 정점(A,B,C)가 있다면 (A-B거리, A-C거리, C-B거리) 이다. 또 여기서 주어지는 값은 트리를 형성한다. (사이클이 없다, 간선의 수는 정점의 수-1) 그렇기 때문에 각 정점 사이의 경로는 '유일' 하다. 위 조건들을 가지고 다시 문제를 보면, 결국 답을 ..

programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr - 접근법 N(맵의 크기)이 25이므로 처음에 생각나는 풀이는 완전탐색 DFS 이다. 하지만 최단거리..

programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr - 접근법 문제와 주어진TC를 통한 예시를 보면, 각 배열에 담긴 값(높이)이 동,서,남,북 인접한 배열에 담긴 값과의 차이가 주어진 height 이하이면 cost없이 통할 수 있다. 그러나 height 보다 큰 인접한 곳은 '사다리'를 설치해야만 지나갈 수 있다. 결국 cost가 소모되는 것은 사다리를 ..