Realuda의 블로그

코딩테스트 연습 - 표현 가능한 이진트리 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr처음에 이진트리를 보고 쫄았는데 별로 상관없는 문제였다. 우선은 제시된 숫자를 이진수 문자열로 변환한다.문자열이 이진트리로 표현된다면 가져야할 길이로 늘려준다.늘려준 문자열이 조건을 만족하는지 재귀적으로 확인한다. 재귀는 이렇게 진행했다.1. 문자열을 세 부분으로 나눈다.left, mid, rightmid는 문자열의 중간에 있는 문자다. 이진트리의 루트 역할을 한다.left와 right는 루트 노드를 제외한 왼쪽 부분트리와 오른쪽 부분트리다. 2. left와 right에 대해서 재귀함수를 수행한다.이 함수..

코딩테스트 연습 - 연속 펄스 부분 수열의 합 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 쉬운 문제인데 함정이 있었다. 연속 펄스 함수는 크게 의미 없다. 결국 sequence에 연속펄스 함수를 적용한 다음, 0번부터 n번까지의 부분수열의 합을 dp로 처리해 계산하면 되는 문제였다. 1. sequence에 연속펄스 함수를 적용한다.2. dp에 부분 수열의 합을 기록한다.예제로 있는 sequence 수열 [2, 3, -6, 1, 3, -1, 2, 4]로 살펴보자. sequence에 연속펄스 함수를 적용한다. 1로 시작하는 펄스인지, -1로 시적하는 펄스인지는 상관없다.그럼 sequence..

코딩테스트 연습 - 보석 쇼핑 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 우선 보석의 종류를 알아야한다. 전체 배열을 한번 순회하면서 보석의 종류를 객체에 기록했다. 그리고 그 다음은 [head, tail] 구간을 설정했다. head와 tail은 초기값 0으로 설정한다. tail을 증가시키면서 [head, tail] 구간에 모든 보석이 포함되는지 확인한다. 모든 보석이 포함된다면 반대로 head를 증가시키면서 확인한다. 더이상 모든 보석이 포함되지 않을때까지 반복한 뒤 구간의 크기를 기록한다. head를 강제로 +1 하고 위 작업을 반복해서 다음 구간을 찾는다. 이 방식으로 정답은..

코딩테스트 연습 - 도둑질 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr dp를 이용한 문제dp[n]에 0번 집부터 n번 집까지 도둑질을 할 때 얻을 수 있는 최대값을 저장해서 풀었다. 단, 한가지 문제가 있었는데, 집이 원형 리스트라는 것이다.첫 집을 털었다면 마지막 집을 털 수 없다는 제한이 있기 때문에 이 부분을 해결해야 했다. dp를 두번 돌리는 것으로 해결했다.dp1은 첫 집을 털었을 경우, dp2는 첫 집을 털지 않았을 경우로 초기화 한 뒤 두 dp를 동시에 진행한다.마지막에 두 dp의 최대값을 비교해서 더 큰 값을 반환하면 된다. dp1은 마지막 집을 털지 못하므로 정답을 비교..

코딩테스트 연습 - N으로 표현 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 딱 보자마자 풀이가 떠오르지는 않는 문제였다. 오히려 감조차 잡을수 없었다. 혼자 고민 해서는 풀지 못할듯 하여 검색해보았다. 핵심 아이디어는 동적 프로그래밍을 사용하는데, dp[i]에는 N을 i번 사용해서 만들 수 있는 숫자들을 기록하는 것이었다. 지금까지의 동적 프로그래밍에서는 dp[i]에 하나의 값만 기록했었는데, 이렇게 데이터셋을 기록하는 방식이 새로웠다. dp에 들어갈 자료구조는 HashSet을 사용했다. HashSet은 javascript의 Set와 같은 자료구조로, 중복값을 허용하지 않는다. Ha..

코딩테스트 연습 - 베스트앨범 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr뭐 특별한 알고리즘이나 자료구조를 사용할 것도 없이 요구사항만 구현하면 된다. 입력받은 두 배열로 Dictionary를 만든다.Dictionary는 장르와 해당 장르의 총합, 제일 많이 플레이된 노래, 두번째로 많이 플레이된 노래를 가진다.다음은 장르들을 총합으로 정렬하고 순서대로 answer에 추가해준다. answer는 배열 형태인데, 배열의 크기를 미리 정할 수 없어서 List 형태로 먼저 만들고 array로 변환했다.using System;using System.Collections.Generic;using S..

코딩테스트 연습 - 지형 이동 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 지형을 사다리 없이 이동할 수 있는 구역으로 나누고, 각 구역들에서 최소신장트리를 찾는다 BFS를 통해 사다리 없이 이동할 수 있는 구역들로 나눈다. BFS는 많이 써봤으니까 그냥 하면 된다. visited[,] 라는 이름으로 2차원 배열을 만들어서 구역들을 표시했다. 다음은 각 구역들에서 다른 구역으로 가는 간선을 만든다. 예시의 그림에서라면 노란색 구역의 5에서 파란색 구역의 10으로 가는 사다리를 4개 놓을 수 있고, 파란색 구역에서 빨간색 구역으로 가는 사다리를 2개 놓을 수 있다. 각 사다리에 대해서 ..

코딩테스트 연습 - 섬 연결하기 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 모든 정점을 포함하는 최단 경로를 구하는 문제 -> 크루스칼 알고리즘을 적용하기로 했다사실 처음에는 이전에 다른 문제를 풀 때 사용했던 플루이드-워셜 알고리즘을 적용하려고 했는데, 잘 안됐다 크루스칼 알고리즘은 최소신장트리를 구하는 알고리즘이다최소신장트리는 모든 정점을 포함하고 순환 구조가 없는 트리들 중에 가중치 합이 최소인 트리를 말한다 아무튼 크루스칼 알고리즘을 적용하면 모든 섬을 연결하는 경로 중 최단 경로를 구할 수 있다 1. 간선들의 가중치를 오름차순으로 정렬한다2. 가장 가중치가 작은 간선을 연결한다..

코딩테스트 연습 - 쿠키 구입 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 보기에 굉장히 단순한 문제우선 완전탐색으로 풀어보기로 했다. 가능한 모든 부분순열 s를 첫째 아들에게 줄 [l, m] 쿠키라고 하고, s[l, m] = s[m+1, r]를 만족하는 r을 찾는다. [l, m] 구간을 만드는 방법은 1부터 n까지의 정수 중에서 두개를 뽑는 것이므로 O(n^2) s[l, m] = s[m+1, r]을 만족하는 r을 찾는 것은 O(n^2) (r을 m+1부터 마지막 요소까지 순회하면서 요소들의 합을 구해야한다) 최종 시간복잡도는 O(n^4)이 된다 O(n^4)는 시간복잡도가 너무 크기때문..

코딩테스트 연습 - 숫자 게임 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr그냥 단순하게 풀었다.A와 B를 내림차순으로 정렬해놓고, A와 B의 요소를 하나씩 비교한다.B가 이길 수 있다면 그대로 이기면 된다.B가 이길 수 없다면 B에서 제일 약한 사람을 보낸다. 코드using System;public class Solution { public int solution(int[] A, int[] B) { int answer = 0; Array.Sort(A, (a, b) => { return b - a; }); Array.Sort(B, (a, b)..