프로그래밍 공방

문제 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..

문제 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..

문제 www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 문제해결방법 이 문제는 최소 공통 조상(LCA)를 찾아서 푸는 문제였다. 2^i 번째 조상을 저장하는 배열로 만들면서 동일한 방법으로 2^i 까지의 경로에 있는 도로의 길이의 최대, 최소값을 저장하는 배열을 만든다. 두 도시가 주어지면 LCA를 찾으러 올라가면서 도로의 길이의 최대, 최소값을 찾으면서 올라간다. 코드 12345678910111213141516171..

문제 www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제해결방법 이 문제는 DP 문제로 점화식을 세워서 푸는 문제였다. 좌측 상단부터 우측 하단까지 배열을 탐색하며 해당 칸을 우측 하단으로 하는 가장 큰 정사각형의 크기를 기록한다. 예를 들어 위 그림은 배열의 값이 1인 (i, j) 칸을 탐색하는 중 (i-1, j) 칸에 5, (i-1, j-1) 칸에 6, (i, j-1) 칸에 3이 저장되어 있는 상태이다. 이때 셋 중에 가장 작은 값인 3을 선택해야 길이가 4인 가장 큰 정사각형을 만들 수 있다. (회색 점선) 위 내용을 점..

문제 www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제해결방법 이 문제는 다익스트라 알고리즘을 이용해서 풀었다. 1번 정점에서 N번 정점으로 가는 최단 거리를 D(1~N)로 표현한다면, A를 반드시 거쳐서 가는 최단 거리는 다음과 같이 표시할 수 있다. => D(1~A) + D(A~N) 이와 같이, A와 B를 반드시 거쳐서 가는 최단 거리는 아래와 같다. Min(D(1~A)+D(A~B)+D(B~N), D(1~B..

문제 programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 문제해결방법 1. 최대 2명이 탈 수 있기 때문에 가장 무거운 사람과 남은 무게에 맞춰 탈 수 있는 사람 중에 가장 무거운 사람을 태운다. 2. 남은 사람들로 위 과정을 반복하며 구명보트의 수를 세준다. 코드 12345678910111213141516171819202122232425262728293031package Programmers; pu..