본문 바로가기

자료구조

 (13)
[백준 / BOJ] 22866 탑 보기 문제 출처 : https://www.acmicpc.net/problem/22866 22866번: 탑 보기 3번째 건물에서 볼 수 있는 건물은 2, 4, 8번째 건물로 총 3개를 볼 수 있다. 그 중 3번째 건물과 가장 가까운 건물은 2, 4번째 있는 건물로 이 중 번호가 작은 번호인 2가 답이 된다. www.acmicpc.net 일직선으로 다양한 높이의 건물이 존재한다. 한 건물 i의 옥상에서 다른 건물들을 볼때 높이가 건물 i보다 큰 건물만 볼 수 있으며, 높이가 L인 건물 뒤에 L이하인 건물은 볼 수 없다고 할때, 각 건물에서 볼 수 있는 건물의 최대 수와 가장 가까운 건물의 idx를 구하는 문제다. 풀이 N이 최대 100,000으로 완전탐색으로 구현할 경우 O(N*N)번 반복해서 TLE를 맞게된다...
[백준 / BOJ] 2533 사회망 서비스(SNS) 문제 출처 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net N명의 친구들이 서로 트리 형태로 연결되어있다. 친구들은 자신의 친구들이 모두 얼리어답터 일때, 자신도 얼리어답터가 된다. 이때, 모든 친구를 얼리어답터를 만들기위해 필요한 초기 얼리어답터 수를 구하는 문제다. 풀이 다이나믹 프로그래밍으로 푼 문제다. 트리에서의 DP의 전형적인? 유형으로 DP로 풀리는것을 떠올리는것이 문제였다. 아이디어 트리의 현재 노드에 할수있는 연산은 두 ..
[백준 / BOJ] 13335 트럭 (Java) 문제 출처 : https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net n개의 트럭이 길이 w인 다리를 지나야한다. 다리가 견딜수있는 최대 무게가 L이라할때, n개의 트럭이 모두 지나기 위해서 걸리는 시간을 구하는 문제다. 풀이 구현 문제였다. 로직은 아래와 같다. 1. 다리의 현재 상태를 저장하는 큐를 하나 만든다. 이 큐에는 트럭이 다리에 진입한 시간, 무게가 저장될것이다. 2. 다리가 새로운 트럭을 ..
[백준 / BOJ] 17298 오큰수 (Java) 문제 출처 : https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net N개의 수로 이루어진 수열이 있다. 이 수열의 i번째 원소를 Ni라 할때, Ni보다 오른쪽에 있으면서 Ni보다 큰 수를 찾아서 구하는 프로그램을 만드는 문제다. 풀이 스택으로 푸는 문제다. 수열에서 Ni보다 오른쪽에 있는 수중 더 큰수를 찾아야한다. 즉, 입력받는 Ni을 스택에 계속 집어넣으면서, Stack의 가장 위에있는 원소가 입력받은 Ni보다 더 큰 경우 스택의 가장 위에있는 원소가 Ni..
[백준 / BOJ] 2493 탑 (Java) 문제 출처 : https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 서로 다른 높이를 갖고있는 N개의 탑이 있다. 이 탑을 일렬로 세우고 탑의 꼭대기에서 왼쪽으로 레이저를 발사한다. 이때, 레이저는 처음 만나는 탑만 수신할수있다. 각 탑에서 레이저를 발사할때, 각 탑별로 레이저를 수신하는 타워를 출력하는 문제다. 풀이 스택으로 푼 문제다. N이 500,000이므로, 완탐으로 풀경우 시간초과가 발생한다. 문제의 조건중 "레이저는 처음 만나는 탑만 수..
[백준 / BOJ] 3015 오아시스 재결합 문제 출처 : https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net N명의 사람이 한 줄로 기다리고있다. i번째 사람과 i+a번째 사람이 서로 보기위해선, i ~ i+a사이에 i와 i+a보다 큰 사람이 없어야한다. 이때, 서로 볼수있는 사람의 쌍을 구하는 문제다. 풀이 푸는데 시간이 좀 많이 걸린문제다. 처음엔, 세그먼트 트리로 생각했으나, N*N/2 시간이 걸릴것이라 생각하여 포기했다.(문제 질문을 보니 세그먼트로도 풀리는듯..
[백준 / BOJ] 1039 교환 문제 출처 : https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 0으로 시작하지않는 정수 N이 주어진다. 정수 N의 자릿수 M에 대해 다음과 같은 연산을 K번 수행했을때, 나올수있는 최댓값을 계산하는 프로그램이다. 1 13 -> 31 과 같은 루트로 이동해 최댓값을 찾을수도 있기때문이다. 따라서, 체크배열을 map check; 와 같이 선언한다. (cnt번 이동해서 vector 형태가 되었을때, 이동횟수) 위 정보들을 갖고 구현하면된다. -1 출력은 1. N이 한자릿수 인경우 2. N이 두자릿수면서 일의자리가 0인경..
[백준 / BOJ] 1275 커피숍2 문제 출처 : https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 커피숍 마담 동호는 손님들과 게임을한다. 게임 방식은 다음과 같다. N개의 수가 있으면 동호는 손님에게 3~7번째 수를 묻는다. 이때, 손님이 답은 000 입니다 라고 대답을한다. 그후, 8번째 수를 2로 고친다. 풀이 기본적인 세그먼트 트리로 풀리는 문제였다. 구현은 다음과 같다. 1. 입력받은 정수N개를 세그먼트 트리구조로 저장해놓는다. 2. 쿼리를..

티스토리툴바