알고리즘/문제풀이 (50) 썸네일형 리스트형 [백준] Q22866 탑 보기JAVA https://www.acmicpc.net/problem/22866 22866번: 탑 보기 3번째 건물에서 볼 수 있는 건물은 2, 4, 8번째 건물로 총 3개를 볼 수 있다. 그 중 3번째 건물과 가장 가까운 건물은 2, 4번째 있는 건물로 이 중 번호가 작은 번호인 2가 답이 된다. www.acmicpc.net 1. 문제의 유형 및 이해 스택 일직선으로 다양한 높이의 건물 총 N개에 대해 양 옆에 존재하는 건물의 옆을 몇개 볼 수 있는지 궁금하다. 현재 건물 높이가 L이라고 할 때, 높이가 L보다 큰 건물만 볼 수 있고, 바라보는 방향에 높이가 L인 건물 뒤에 L이하의 건물이 있다면 가려져서 보이지 않는다. 각 건물에서 볼 수 있는 건물들의 개수와, 가장 가까운 건물 위치를 출력하라. 어떤 기준 건물.. [백준] Q11085 군사 이동 JAVA https://www.acmicpc.net/problem/11085 11085번: 군사 이동 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 www.acmicpc.net 1. 문제의 유형 및 이해 그래프 탐색, 분리집합 문제를 단순히 하면 다음과 같습니다. 노드 P개와 W개의 edge가 주어진다. 이 때 두 노드 C와 V가 주어지는데, C에서 V까지 가는 여러 경로가 있다. 이 때 각 경로에 포함된 간선 중 가장 작은 값을 가장 크게하는 경로를 찾아보자. 처음에 푼 풀이방법과 이후에 알게된 풀이에 대해 정리해봅시.. [백준] Q17610 양팔저울 JAVA https://www.acmicpc.net/problem/17610 17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net 1. 문제의 유형 및 이해 완전탐색 서로다른 K개의 추를 양팔저울을 한번만 비교하여 원하는 무게를 그릇에 담고자 한다. {1,2,6}의 추가 주어질 때 , 만들 수 있는 모든 경우의 수는 다음과 같다. (ㅁ : 그릇) 그릇에 4만큼의 무게를 담고자 할때는 가지고 있는 추 2, 6을 이용하여 (ㅁ + 2) = 6 을 통해 ㅁ = 4 를 만들어 낼 수 있다. 모든 추의 합이 S라고 할 때 1~ S .. [백준] Q9079 동전게임 JAVA https://www.acmicpc.net/problem/9079 9079번: 동전 게임 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 세 줄로 이루어지며, 한 줄에 세 개의 동전모양이 주어지는데, 각각의 동전 표시 사이에는 하나의 공백이 www.acmicpc.net 1. 문제의 유형 및 이해 완전탐색, bit연산 동전을 3행 3열로 놓을 때 앞면을 H 뒷면을 T라고 하자. 게임의 목적은 모든 동전을 같은 면으로 보이도록 하게하는 것이다. 한 번에 3개의 동전을 뒤집는 행위를 '한번의 연산'으로 셀 때 최소 횟수로 실행하고 싶다. 가로, 세로, 대각선 (항상 3개씩 뒤집어야함) 연산의 개수는 총 가로 3줄, 세로 3줄 대각선 2줄로 한번의 상태에서 총 8.. [백준] Q2204 도비의 난독증 테스트 JAVA https://www.acmicpc.net/problem/2204 2204번: 도비의 난독증 테스트 꿍은 도비에게 영어단어들을 제시한 후 어떤 단어가 대소문자를 구분하지 않고 사전순으로 가장 앞서는지 맞추면 양말을 주어 자유를 얻게해준다고 하였다. 하지만 인성이 좋지 않은 꿍은 사실 www.acmicpc.net 1. 문제의 유형 및 이해 구현, 정렬 대소문자를 구분하지 않고 사전순으로 가장 앞서는 단어를 정답으로 한다. apPle Bat AnT가 주어질 때 Ant apPle Bat 순으로 정렬이 된다. 각 테스트 케이스마다 주어지는 단어 개수 N 는 1000이하이다. 각 단어는 길이가 최대 20인 단어가 주어지고, 대소문자 구분을 없앴을 때 같은 단어는 주어지지 않는다. 2. 문제 접근 방법 문제에서 주.. [백준] Q16566 카드게임 JAVA https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 1. 문제의 유형 및 이해 이분탐색, 분리 집합(Disjoint set) 문제 내용이 길어서 핵심만 간추리면 다음과 같다. 상대와 카드를 비교하여 내 카드를 어떻게 낼지 정하는 문제이다. 1~N까지 번호가 쓰인 N개의 카드 중 내가 가진 M개의 카드가 주어진다. 총 K번 비교를 하는데 상대가 낼 카드의 번호가 주어진다. 비교한 카드는 없어진다... [백준] Q2568 전깃줄 -2 JAVA https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 1. 문제의 유형 및 이해 LIS, 이분탐색 다음과 같이 전깃줄이 연결되어 있을 때 서로 교차하지 않도록 최소한의 개수로 전깃줄을 없애려고 한다. 이 때 없애야하는 전깃줄의 최소 개수와 번호를 오름차순으로 나열하기. 한쪽을 기준으로 보았을 때 '교차하지 않는다'라는 말은 기준의 방향성과 동일하게 나열되어 있다 라고 이해할 수 있습니다. 그렇지 않다면 역으로 가서 교차하게 되기 때문입니다. a를.. 이전 1 2 3 4 ··· 8 다음
