알고리즘/연습문제

[네트워크 연결] 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을 반환한다 문제 접근 어떤 경로로 이동 하는지에 따라 최소 값이 달라질 수 있다 아래 사진처..

문제 정보는 아래 링크를 확인해주세요! [9576 - 책 나눠주기] 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 �� www.acmicpc.net 문제 접근 방법 a와 b를 입력 받는 동시에 리스트에 b를 기준으로 오름차순 정렬을 해준다. 나눠준 책을 확인하기위한 배열 생성 정렬된 책 정보를 통해 a~b까지 분기문을 돌면서 등록되지 않은 책을 등록하고 최대 수량 증가 위 과정을 테스트 케이스만큼 반복한다. [소스 코드] package algorithm.grid; import java.util.*; /* * 백준 9576 * 책 나눠주기 ..

문제 정보는 아래 링크를 확인해주세요! [3109 빵집] 3109번: 빵집 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴� www.acmicpc.net 문제 접근 방법 (0,0) 부터 오른쪽 대각선 위, 옆, 대각선 아래를 검사해주면서 지나갈 수 있는 곳을 방문 표시해주고, 오른쪽 라인으로 (0,C)까지 이동하면서 검사를 반복한다. 검사를 마치고 (0,C)까지 이동할 수 있다면 종료 (R,0)까지 위 세가지 과정을 반복한다. 유의해야할점은 해당 파이프라인으로부터의 가지치기를 방지하기위해 재귀함수를 리턴한다. 자세한 설명은 아래 그림 참조 [소스 코드] package ..

문제 정보는 아래 링크를 확인해주세요! [백준 - 1202 보석도둑] 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 � www.acmicpc.net 문제 접근 방법 가방과 보석점을 오름차순으로 정렬한다. 우선순위 큐를 하나 만든다. 가방에 대한 분기문을 진행하면서 현재 가방의 무게보다 작은 보석점의 가격을 우선순위 큐에 담는다. 우선순위 큐에서 가격이 가장 높은 것을 꺼낸다. 결과값에 더해준다. [소스 코드] package algorithm; import java.util.*; public class Algorithm { //보석점..

문제 정보는 아래 링크를 확인해주세요! [암호코드] 2011번: 암호코드 문제 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이� www.acmicpc.net 문제 접근 방법 암호코드의 첫째 자리부터 마지막 자리수까지 만들 수 있는 가지수를 구해나가는 DP 방식 만들 수 있는 문자의 번호는 1 ~ 26 이므로 현재값으로 1~9 사이의 문자를 만들 수 있는지 확인하고 현재값과 이전값으로 10 ~ 26 사이의 문자를 만들 수 있는지 확인한다. 유의해야할 부분은 각 DP 요소마다 범위를 넘어설 수 있으므로 1000000으로 나눠주고 암호코드의 첫 번째 요소가 '0'이면 문자..