알고리즘
-
[프로그래머스][카카오][자바] 양궁대회
🔗 링크 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr 🔒 문제 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원회는 한 선수의 연속 우승보다는 다양한 선수들이 양궁대회에서 우승하기를 원합니다. 따라서, 양궁대회 운영위원회는 결승전 규칙을 전 대회 우승자인 라이언에게 불리하게 다음과 같이 정했습니다. 어피치가 화살 n발을 다 쏜 후에 라이언이 화살 n발을 쏩니다. 점수를 계산합니다. 과녁판은 아..
2022.02.11
-
[파이썬][백준] 다각형의 면적
🔗 링크 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 🔒 문제 🔎 문제풀이 다각형 넓이 구하기 다각형의 넓이를 계산하는 일은 정삼각형 넓이를 구하는 것처럼 간단하기도 하지만 각 변의 길이가 다른 11각형의 넓이를 구하는 것처럼 복잡하기도 합니다. 다양한 다각형의 넓이를 구하는 방 ko.wikihow.com 문제 접근을 어떻게 해야 할지 감이 안 잡혀서 다각형 면적을 구하는 공식이 있는지 찾아서 풀 수 있었다. 공식대로 코딩을 하니 문제가 쉽게 풀려 당황했다. 주의 할 점은 음수로 정답이 음수로 나올 수 있어 마지막에 처리해주었다. ..
2022.01.25
-
[알고리즘][자바]서로소 집합, Union Find
서로소 집합(Disjoint Sets)이란? 서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미 합니다. ex) {1,2}와 {3,4}는 서로소 관계이다 {1,2}와 {2,3}은 서로소 관계가 아니다. 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조입니다. 서로소 집합 자료구조는 두 종류의 연산을 지원합니다. 합집합(Union): 두개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산입니다. 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산입니다. 서로소 집합 자료구조는 합치기 찾기(Union Find)자료구조라고 불리기도 합니다 여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정은 다음과 같..
2022.01.21
-
[파이썬][프로그래머스] 파괴되지 않은 건물
🔗 링크 코딩테스트 연습 - 파괴되지 않은 건물 [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 10 [[1,2,3],[4,5,6],[7,8,9]] [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 6 programmers.co.kr 🔒 문제 🔎 문제풀이 처음에는 skill에 있는 좌표 모든 곳을 type에 맞게 계산을 해서 풀었었다. 당연히 효율성에서 시간 초과가 났었다. 좌표를 기억 표시해두고 한 번에 모든 걸 계산할 수 있는 방법을 찾아야 했었다. 누적합을 사용하여 풀어보았다. 첫 번째로 적이 맵의 (0,0)부터 (3,4)까..
2022.01.20
-
[파이썬][백준21318] 피아노 체조
문제링크 21318번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 문제 문제풀이 x, y의 구간에서 주어진 난이도(arr) arr[i] > arr[i+1] 개수를 찾는 문제. 모든 주어진 질문을 완전 탐색으로 하면 시간초과가 났습니다. 구간을 검색해봤던 곳을 또 검색하는 경우가 있을 거라고 생각해서 누적합을 이용하면 된다고 생각했다. 난이도 배열을 한번 돌면서 전 난이도랑 비교하고 누적합을 더해주었다 따라서, dp[y] - dp[x]가 정답이 된다. 파이썬 코드 import sys """ 피아노 체조 https://..
2022.01.13
