막내의 막무가내 프로그래밍 & 일상

www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 모 코테에서 나온 문제와 똑같다. 시간을 좀 잡아먹었던 문제입니다. ㅂㄷ 풀이는 다음과 같습니다. [Java] import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; class Main { public static void main(String[] args) { Scanner sc = new Scann..

www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 해시맵을 사용하면 간단하게 풀리는 문제입니다. 단 다음 공식을 알아야합니다. 옷 종류별로 (옷 개수+1) * (옷 개수 + 1 ) * ... * (옷 개수 + 1 ) -1 이 총 알몸이 아닌 상태로 의상을 입을 수 있는 경우의 수 입니다. 풀이는 다음과 같습니다. [Java] import java.util.HashMap..

www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 처음 완전탐색으로 접근했다가 삽질만 했습니다. 제출 시 60초가 걸리는 테스트케이스와 100,000개의 n 때문에 완전탐색으로 푼다고 해도 시간초과가 날 것 같당.. 이후 서칭 후 DP 문제인 것을 알고 dp로 풀었습니다. 다음 그림으로 점화식을 세우면 됩니다. [Java] import java.util.Scanner; class Main { public static void main(String[]..

www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 백준 최단경로 단계별풀기 두 번째 문제를 풀어봤습니다. 시작점에서 도착점까지의 최단 경로를 구해야하는데 반드시 거쳐야 할 정점 두 개를 조건으로 추가되었습니다. 반드시 지나야하는 정점이 v1, v2 인데 start -> v1 -> v2 -> end start -> v2 -> v1 -> end 두 가지 로직이 가능합니다. 이를 적용한 풀이입니다. [Java] impor..

www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 백준 최단경로 단계별풀기의 첫번째 문제입니다. 최단경로의 가장 베이스적인 문제입니다. 풀이는 주석에 적어놓았습니다. 또 설명은 다음 블로그에서 그림과 함께 잘 해놓으셨습니다. ㅎㅎ dragon-h.tistory.com/20 [백준 1753 : JAVA] 최단경로 / 다익스트라 개요 이 문제는 가중치가 1이 아니고 음의 가중치도 아니기 때문에 다익스트라를 이용하여 풀이할 수 있다. 다익..

www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 하루에 시간이 없어도 한문제씩은 풀려고 했는데 요즘 못풀고 있습니다. 감이라도 안잃게 그리디 문제 골라서 풀어봤습니다. 주석으로 설명되는 간단한 문제였습니다. [Java] import java.util.Scanner; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextIn..

www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 백준 3248 양 문제입니다. 저번에 풀고서 분명 맞았는데 계속 틀리게 나와서 이상하다 싶어 버린 문젠데 재채점 되서 맞았다고 알림이 왔습니다. 이거랑 거의 똑같은 문제는 다음과 같습니다. youngest-programming.tistory.com/424 [알고리즘] 백준 3187 양치기 꿍 -bfs- 자바 www.acmicpc.net/problem/3187 3187번: 양치기 꿍 입력의 첫 번째 ..

www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 백준 그리디 유형의 문제입니다. 키가 1인 사람부터 N인 사람까지 차례대로 입력을 받으며 해당 키 사람의 왼쪽에 입력 만큼의 키큰 사람이 왼쪽에 있어야합니다. 다음 블로그에서 설명을 잘해놓았습니다. lipcoder.tistory.com/entry/%ED%95%9C-%EC%A4%84%EB%A1%9C-%EC%84%9C%EA%B8%B0-%EB%B0%B1%EC%A4%80-1138%EB%B2%88 한 줄로 서기 ..

www.acmicpc.net/problem/1074 1074번: Z 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 www.acmicpc.net solved.ac 에서 레벨에 맞는 문제를 골라서 가끔 풀고있습니다. 그 중 한 문제입니다. 풀고서 다른 분들의 풀이를 봤는데 다양하게 푸는 것 같고 효율성 관련하여 에러가 난다는 말씀이 많았습니다. 문제를 제출하고 45초 동안이나 테스트케이스를 돌리는걸 보니 효율성이 중요한 듯 합니다. 저는 분할정복을 사용하여 문제를 해결했습니다. 4분의 1조각 씩 쪼개면서 2x2(num이 2일때) Z모양으로 탐색을..

www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 백준 우선순위큐 단계별 풀기의 마지막 단계의 문제를 풀었습니다. 풀다가 도저히 안풀려서 가장 깔끔하게 푸신 분의 코드를 보고 이해했습니다. 설명도 잘해놓으셨습니다. dragon-h.tistory.com/6 [백준 1655 : JAVA] 가운데를 말해요 / PriorityQueue 개요 PriorityQueue를 이용하여 풀 수 있는 문제이다. 해당 자료구조에 대한 이해도가 없는 사람들은 기초 문..

www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이 www.acmicpc.net 백준 우선순위큐 단계별풀기의 첫번째 문제입니다. 스캐너로 풀면 시간초과납니다. ㅠ 풀이는 다음과 같습니다 [Java] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; class Main { public static voi..

www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 백준 유니온파인드 단계별 풀기의 두번째 문제입니다. youngest-programming.tistory.com/427 [알고리즘] 백준 1717 집합의 표현 -유니온파인트(Union-find)- 자바 www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 ..

www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 www.acmicpc.net 백준 유니온파인드 단계별풀기의 문제입니다. 처음 푸는 유형이라 밑을 참고해서 공부 후 풀었습니다. brenden.tistory.com/34 [백준 1717] 집합의 표현 글에 개요 백준 알고리즘 1717번 "집합의 표현" 문제입니다. 앞서 다루었던, 아래 참고할 글 1번에 정리한 내용을 보시면 쉽게 푸실 수 있는 문제입니다. 유니온 파인드 (Union-Find)를 정리한 글 내용..

www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 백준 이분탐색 단계별 풀기에 있는 공유기 설치 문제를 풀어봤습니다. 처음에 문제가 이해가 잘 안갔는데 저랑 같은 생각을 한 분의 블로그를 통해 이해할 수 있었습니다. 감사합니다. dundung.tistory.com/54 백준 2110 공유기 설치 Java 이분탐색 문제인 공유기 설치 문제이다. 난 문제를 이해하는 것도 헷갈렸다.. 요즘 문제 이해하기가 넘 힘들..

www.acmicpc.net/problem/3187 3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net 기본적인 BFS를 살짝 응용한 문제입니다. BFS를 돌며 한 영역에서 양과 늑대의 수를 비교해주고 결과를 도출해주면 됩니다. 풀이는 다음과 같습니다. [Java] import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Main { private static boolean[][] isVisited; pri..