프로그래밍 공방

문제 programmers.co.kr/learn/courses/30/lessons/17681 코딩테스트 연습 - [1차] 비밀지도 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다 programmers.co.kr 문제해결방법 이 문제는 단순하게 각 지도의 정수 배열을 비교해가며 전체 지도를 만들어주었다. 코드 12345678910111213141516171819202122232425262728293031package Programmers; public class Solution_보물지도 { public static String makeMap(int n, int a, int..

문제 programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 문제해결방법 이 문제를 풀기 위해 시작 인덱스와 끝 인덱스 두 개의 포인터를 사용하였다. 1. gems를 돌면서 Map에 존재하면 pass, 존재하지 않으면 해당 보석 이름을 Key로, Value를 0으로 해서 맵에 넣어준다 -> 맵에 넣어줄때마다 카운트해서 보석의 종류의 개수를 알 수 있다. 2. 끝 인덱스를 배열의 0에서부터 증가시켜가며 보석의 종류별로 나온 횟수를 센다. (0에서 1이 되는 경우 카운트 하여 보석 ..

문제 www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net 문제해결방법 이 문제를 해결하기 위해, 0인 곳을 1로 만들어서 상, 하, 좌, 우에 있는 모양들이 연결되도록 하고, 그 결과로 만들어지는 가장 큰 모양을 찾아야 겠다고 생각했다. 1. 처음에 배열을 돌면서 BFS를 통해 연결 요소들을 찾아 각 연결 요소에 번호를 붙이고 Map에 그 번호를 Key로 사이즈를 Value로 해서 저장해줬다. 2. 다시 한 번 배열을 돌면서 0인 곳마다 상, 하, 좌..

문제 www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 문제해결방법 수영장의 넓이를 구하기 위해 물의 높이와 땅의 높이의 차를 계산한 배열을 따로 계산해두었다. 높이의 차가 양수인 영역들 중에 배열의 가장자리와 닿지 않는 영역들을 모두 더하면 수영장의 넓이가 된다. 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515..

문제 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제해결방법 BFS를 돌면서 인구 이동이 발생하는지 확인하고, 만약 발생한다면 인구 이동을 시켜준다. 위 과정을 더 이상 인구 이동이 발생하지 않을 때까지 반복해준다. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566..

문제 www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 문제해결방법 이 문제는 사람을 정점으로 두고 간선의 길이를 1로 가정하고 풀었다. 한 사람에서 다른 사람들까지의 거리를 모두 구해서 2이하인 사람들의 수를 구하는 문제였다. 모든 정점에서 다른 모든 정점까지를 구해야 하기 때문에 플로이스 와샬 알고리즘을 사용해서 풀었다. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142..

문제 www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 문제해결방법 이 문제는 집, 편의점, 펜타포트 락 페스티벌 좌표를 그래프의 정점으로 가정하고 풀었다. 각 좌표에서 다른 좌표까지의 거리가 1000이하라면 두 정점을 간선으로 연결해준다. 집 정점을 시작으로 BFS를 돌면서 락 페스티벌 정점까지 도착할 수 있다면 happy, 없으면 sad를 출력했다. 코드 123456789101112131415161718192021222324252627282930313..

세그먼트 트리는 특정 구간에 대해 주어지는 쿼리에 효율적으로 응답하기 위해 만들어진 자료구조이다. (구간의 합, 특정 구간에서 가장 큰 수 / 작은 수 등) 입력 배열을 리프 노드로 하고 내부 노드는 리프 노드를 병합해서 나타낸다. 주어지는 쿼리에 대해서 병합 방식은 다를 수 있다. 세그먼트 트리를 구현하는 방법은 여러 가지가 있지만 이 글에서는 구간 합에 대해서 재귀로 구현하는 방법에 대해서 정리했다. 세그먼트 트리의 구현은 크게 3가지로 나눌 수 있다. 1. 트리 생성 2. 노드 업데이트 3. 쿼리 처리 트리 생성 세그먼트 트리의 크기(배열의 길이)는 입력 배열의 크기 n에 대해서 (int) (Math.ceil(Math.log(n) / Math.log(2))) 이다. (아래 코드의 arr는 입력 배열..

문제 www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제해결방법 이 문제는 세그먼트 트리를 사용해서 풀었다. 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859package baekjoon; import java.io.BufferedReader;imp..

문제 programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제해결방법 이 문제는 N을 사용한 횟수를 기준으로 잡고 DP로 풀었다 DP[N] = (DP[N-1], DP[1]) (DP[N-2], DP[2]) .... (괄호 안에 있는 DP의 원소끼리 사칙연산을 해준다) 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556package Programmers; import java.util.HashSet;import java.util.Set; public class Soluti..