코딩테스트

[네트워크 연결] 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 접근 방법 Union - Find 접근 두 노드 A와 B가 같은 부모 노드를 가지는지 검사(Find)하고 서로 다른 부모를 가질 경우, 두 노드를 합치고 부모 노드를 통일해준다(Union) 문제 접근 전체 간선을 담을 리스트 형식의 자료구조를 준비한다. 배열을 간선이 작은 순서대로 정렬한다 이유는 A와 B를 연결하는 여러 간선 중에 가장 작은 간선이 먼저 배치되어야하기 때문이다 간선 리스트 자료구조에 대해 분기문을 돌면서 간선의 두 컴퓨터 A와 B의 네트워크가 같은지 검사한다 (Find) 두 노드의 컴퓨터의 네트워크가 다르면, 네트..

[순위] 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 플로이드 워샬 알고리즘 A와 B, B와 C의 관계를 알고, A와 C의 관계를 알고 싶을 때 사용 승리 결과와 패배 결과를 리스트로 보관한다. 결과를 알 수 있는 두 선수(A, B)와 결과를 알고 싶은 두 선수(A, C)를 비교하여 A와 C의 결과를 도출한다 A > B // B > C일 때 ⇒ A > C가 된다. 만약, A > B, B > C, C > A인 경우가 있다면?? 해당 의문에 대해서는 문제 제한사항에 경기 결과에 모순이 없다는 것을 확인 순위 판단 선수 목록을 순회 하면서 A가 B..

[RGB 거리] 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 접근 두 가지 경우의 수 확인 첫 번째, 두 번째, 세 번째 집의 색이 전부 다를 경우 => O O O 두 번째 집만 다를 경우 => O O O 위 두 경우의 수를 구하기 위한 점화식 구하기 N번 째 선택한 색깔이 빨강일 경우 N-1번 째 선택한 색깔이 초록일 경우와 파랑일 경우 중에 더 작은 값을 빨강의 값과 더해준다 위 두 과정을 반복하는 점화식을 세우면 RED[N] = min(GREEN[N-1], BLUE[N-1..

[게임 맵 최단 거리] 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 n x m 크기의 맵에서 맵의 끝에 빨리 도착하는 방법 찾기 (1,1) 에서 시작하며, 1회 이동에 한 칸씩 동, 서, 남, 북 네 방향으로 이동 가능 맵은 0과 1로 구성되어 있고, 0은 벽, 1은 이동할 수 있는 곳을 의미한다 n과 m은 다를 수가 있고, n과 m이 모두 1인 경우는 존재하지 않는다 반환 값은 이동할 수 있는 최솟값을 반환하며, 맵의 끝에 도착하지 못 할 경우 -1을 반환한다 문제 접근 어떤 경로로 이동 하는지에 따라 최소 값이 달라질 수 있다 아래 사진처..

문제 정보는 아래 링크를 확인해주세요! [조이스틱] 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 문제 접근 방법 name의 길이만큼 'A'로 구성된 문자열을 만듭니다. name의 문자열의 요소가 'A'가 아닌 곳을 찾고 해당 요소를 위,아래로 움직인 횟수중 더 작은 값을 결과값에 추가해줍니다. 해당 요소에서 왼쪽과 오른쪽을 탐색해주면서 더 적은 이동으로 'A'가 아닌 곳을 찾는 방향을 선택합니다. 이 때, 유의해야할 점은 왼쪽과 오른쪽 검사에서 오른쪽 검사를 먼저해줍니다. 그 이유는 왼..

문제 정보는 아래 링크를 확인해주세요! [카카오프렌즈 컬러링북] 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 문제 접근 방법 기본적인 BFS 탐색 문제입니다. 그림판을 탐색하면서 0이 아니고 방문하지 않은 곳을 발견하면 영역을 하나 증가 시켜주고 현재 방문한 곳부터 상,하,좌,우를 탐색하며 같은 영역을 찾습니다. 해당 영역에 대한 탐색이 끝나면 그 영역의 갯수와 최댓값을 비교해줍니다. 다음 영역을 구하기위해 그림판을 재탐색합니다. [소스 코드] package algorithm.programmersLevel2..

문제 정보는 아래 링크를 확인해주세요! [다리를 지나는 트럭] 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이�� programmers.co.kr 문제 접근 방법 다리를 지나고 있는 트럭에 대한 정보와 대기하고 있는 트럭의 정보를 만들어주고 현재 다리의 가능 무게보다 대기중인 트럭의 무게가 작거나 같으면 그 트럭을 다리를 지나는 트럭 정보에 추가해주고, 현재 가능 무게를 트럭의 무게만큼 감소시킨다. 다리를 지나는 트럭 정보에서 트럭이 다리를 건넜으면 그 트럭을 제거해주고, 트럭의 무게만큼 가능 무게를 증가한다. 다리를 지나는..

문제 정보는 아래 링크를 확인해주세요! [주식가격] 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 문제 접근 방법 주식가격이 담긴 배열을 자신의 인덱스보다 높은 값들과 비교하면서 자신의 값보다 작은 값이 나오면 종료하고 해당 값까지의 시간을 결과 배열에 추가 [소스 코드] package algorithm.programmersLevel2; /* * 프로그래머스 * 주식가격 * */ public class Pro42584 { public int[] solution(int..