알고리즘
-
[백준] 10163 : 색종이 - 자바(JAVA)알고리즘/백준 2022. 3. 16. 00:01
https://www.acmicpc.net/problem/10163 10163번: 색종이 평면에 색깔이 서로 다른 직사각형 모양의 색종이 N장이 하나씩 차례로 놓여진다. 이때 색종이가 비스듬하게 놓이는 경우는 없다. 즉, 모든 색종이의 변은 서로 평행하거나, 서로 수직이거나 둘 www.acmicpc.net 문제 해석 평면에 색깔이 서로 다른 직사각형 모양의 색종이 N장이 하나씩 차례로 놓인다. 색종이는 비스듬하게 놓이는 경우는 없습니다. 위의 그림에서 4번 색종이를 하나 더 놓았을 때 3번 색종이는 완전히 가려서 보이지 않게 됩니다. 다음과 같이 N장의 색종이가 주어진 위치에 차례로 놓일 경우, 각 색종이가 보이는 부분 면적을 구하는 프로그램을 작성하세요. 문제 풀이 전 설계 https://junuuu...
-
[백준] 2563 : 색종이 - 자바(JAVA)알고리즘/백준 2022. 3. 15. 00:01
https://www.acmicpc.net/problem/2563 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 문제 해석 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 변과 도화지의 변이 평행하도록 붙입니다. 여러 장의 색종이를 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.(종이가 겹치게 붙을 수 있습니다.) 입력 첫째 줄에 색종이의 수가 주어집니다. 이어 둘째 줄부터 한 줄..
-
[백준] 1158번 : 요세푸스 문제 - 자바(JAVA)알고리즘/백준 2022. 3. 14. 00:01
https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 해석 문제는 사람의 수 N과 제거할 순번인 K를 입력받습니다. 초기 시작 자료구조는 다음과 같습니다 1, 2, 3, 4, ......, N 여기서부터 순서대로 K번째를 제거합니다. N=5라 가정하여 초기 시작 자료구조는 1, 2, 3, 4, 5 이며 K=2라고 가정해보겠습니다. 초기 시작 1, 2, 3, 4, 5 2번째수인 2제거 step 1 : 1, 3, 4, 5 굵은글씨 3부터 2번째수인 4제거 step 2 : 1,3,5 굵은글씨 5부터 2번째수인 1제거 step 3 : 3,4 ..
-
[백준] 1275번 : 커피숍2 - 자바(JAVA)알고리즘/백준 2022. 3. 13. 16:41
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개의 정수를 가지고 게임을 한다. 우리는 심판 역을 맡았기 때문에 질문에 대한 답들을 미리 알아야 한다. 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다. 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어집니다. 셋째 줄부터 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합을 구하라, a번째 수를 b로 바꾸어라 라는 뜻의 데이터가 주어..
-
세그먼트 트리란?알고리즘/알고리즘 2022. 3. 13. 15:39
세그먼트 트리란? 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하기 위한 자료구조입니다. 배열에서 특정 구간의 합을 가장 빠르게 구하기 위한 방법은 무엇일까요? 예시 데이터 : 5 8 7 3 2 5 1 8 9 8 7 3 여기에서 인덱스 1부터 10까지 데이터의 합을 구하려면 어떻게 할 수 있을까요? 간단하게 인덱스 1부터 10까지 데이터를 다 더해준다면 데이터의 개수에 의존하여 O(N)의 시간 복잡도가 나옵니다. 이것을 트리 구조를 이용해서 구한다면 O(logN)의 시간복잡도로 부분합을 구할 수 있습니다. 다음 그림을 보면 조금 더 이해하기 쉽습니다. 이처럼 더한값을 다시 재사용하면서 최종적으로 0~14의 연산 결과를 얻기 때문에 O(logN) 시간을 보장합니다. Segment..
-
1210. [S/W 문제해결 기본] 2일차 - Ladder1 - 자바(JAVA)알고리즘/SW Expert Academy 2022. 3. 12. 00:01
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 0과 1로 이루어진 보드가 존재합니다. 0은 이동할 수 없으며 1은 이동할 수 있습니다. 실제 사다리 게임을 하는 것처럼 아래로 내려가다가 왼쪽 또는 오른쪽으로 이동할 수 있다면 이동합니다. 목적지에 도달하게 된다면 시작점을 출력하는 문제입니다. 평소에 사용하던 좌표계인 data[세로][가로] 와는 다르게 data [가로][세로]의 형식을 띄고 있습니다. 또한 왼쪽 또는 한쪽 방향으로만..
-
1861. 정사각형 방 - 자바(JAVA)알고리즘/SW Expert Academy 2022. 3. 11. 00:01
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 N^2의 방이 NxN형태로 존재합니다. 위에서 i번째 줄의 왼쪽에서 j번째 방에는 1 이상 N^2 이하의 수 A(i, j)가 적혀 있습니다. 어떤 방에 있을때, 상하좌우에 있는 다른 방으로 이동할 수 있습니다. 이동하려는 방이 존재해야 하며, 이동하려는 방에 적힌 숫자가 현재 방에 적힌 숫자보다 정확히 1 더 커야 합니다. 처음 어떤 수가 적힌 방에서 있어야 가장 많은 개수의 방을 이동할..
-
Upper_bound와 Lower_bound란?알고리즘/알고리즘 2022. 3. 10. 09:26
어떤 리스트에서 이분 탐색을 이용하여 특정 값을 찾을 때, 리스트가 중복된 값을 포함하고 있을 때 중복 값들을 전부 찾거나 또한 그 중복값들을 활용해서 문제를 해결하기 위해서 lower_bound, upper_bound를 사용하면 특정 target number 보다 크거나 같은 첫 번째 원소 인덱스, target number보다 큰 첫번째 원소의 인덱스를 찾을 수 있습니다. 이진 탐색을 이용하기 때문에 리스트는 항상 정렬되어 있어야 합니다. hashFunction을 이용하여 중복된 값들의 개수를 탐색하면 O(1)이라 훨씬 더 빠르게 탐색할 수 있을 것 같은데..?라는 생각이 들긴 합니다. 하지만 특정 구간의 범위를 지정하기 위해서는 유용하게 사용할 수 있을 것 같습니다. upper_bound 범위 [be..