Eastplanet

문제 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 풀이 방법 https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 치즈 문제와 유사해서 똑같은 풀이 방법으로 접근할 ..

문제 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 풀이 방법 문제 유형 : 그리디 & 유니온 파인드 그리디 접근 각각 gi에 따라 도킹할 수 있는 게이트는 다음과 같다. 1번 게이트는 1,2,3,4인 비행기가 도킹할 수 있고, 2번 게이트는 2,3,4인 비행기가 도킹할 수 있고, ..., 4번 게이트는 4인 비행기만 도킹할 수 있다. -> 4인 비행기가 자기만 사용할 수 있는 게이트를 사용하는 게 가장 좋지..

1. Union Find 자료구조 ( 서로소 집합 자료 구조) Union find 자료 구조는 서로소 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이고, find와 union 연산을 제공한다. find 연산 해당 원소가 속한 집합의 대표를 반환한다. 위와 같은 서로소 집합이 주어졌을 때, 대표는 1번과 2번이고 find 연산의 결과는 아래와 같다. find(1) = 1 find(3) = 1 find(4) = 1 find(5) = 1 find(2) = 2 find(6) = 2 union 연산 두 개의 집합을 하나의 집합으로 합친다. 초기 상태 union (1, 2) union (3, 4) union (1, 5) union (1, 3) 이후 상태 2. 구현 방법 자신의 부모를 지시하는 배열..

문제 풀이 1. N명의 성적을 받아서 각 점수를 받은 사람이 몇명인지 카운팅 한다. 2. 각 점수의 누적합을 구한다. 3. 누적합을 통해 해당 점수가 몇등인지 계산한다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int N = I..

문제 https://softeer.ai/practice/6252 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 제약 조건 시간: 5초 메모리: 1024MB 입력으로 들어오는 수의 범위가 매우 커서 완전 탐색이 어렵기 때문에 이분 탐색으로 문제를 접근함. start = 1 (모든 컴퓨터의 성능이 1 이상) end = 2 * 10^9를 넣어 이분탐색을 진행한다. (모든 컴퓨터의 성능이 2*10^9 이상) 2 * 10^9인 이유 1대의 컴퓨터의 성능이 10^9이고, 예산이 10^18이 들어오면 성능을 10^9만큼 올릴 수 있다. 기존의 성능 10^9 + 올린 성능 10^9 = 2 * 10 ^ 9 canUpgrade(mid)를 통해 현재 예산으로 모든 컴퓨터의 성능이 mid 이상이 될 수..

문제 https://www.acmicpc.net/problem/22944 22944번: 죽음의 비 가로, 세로 길이가 $N$인 정사각형 격자가 있다. 해당 격자에는 두 곳을 제외한 모든 곳에 체력을 1씩 감소시키는 죽음의 비가 내리고 있다. 죽음의 비가 안내리는 곳은 현재 있는 위치와 안전지 www.acmicpc.net 풀이 방법 풀이 문제에서 사람은 항상 목적지 아니면 우산이 존재하는 곳을 향해야만 최적의 이동을 할 수 있다. 따라서 시작위치, 우산위치, 목적지를 정점으로 재구성한 뒤 BFS를 수행한다. 설명 1. 안전 지대로 바로 가는 것이 가능 하다면 이 경우가 최소 이동 횟수이다. 2. 안전 지대로 바로 가지 못한다면 안가본 우산위치 중 하나의 위치로 가야한다. 최소 이동 거리라는 조건을 만족하기..

문제    풀이 방법1. 필요 시 마다 검색S, E가 주어진 후 S부터 E까지 팰린드롬인지 검사하는 방법의 경우S = 1, E = N으로 주어지고 M = 100만인 경우, 2000*100만 = 연산 횟수가 20억이 된다.1번 방법의 경우 이미 검색했던 정보를 저장하지 않아서 다시 검색하는 문제가 존재한다. 2. 가능한 모든 경우를 미리 검색해서 저장미리 모든 경우에 대해 팰린드롬인지 검사를 해서 저장 해놓은 배열 ans[][]를 통해,검색이 필요한 경우 ans[S][E]를 참조해 결과를 리턴하는 방식S와 E를 위한 2중 for문과 S, E가 정해진 상황에서 팰린드롬인지 검사하기 위한 for문 총 3중 for문이 필요하고연산 횟수는 2000*2000*2000 = 80억 이 된다. 3. 필요 시 마다 검색 ..

문제 풀이 방법 예제 케이스와 같이 7 3 6 2 4를 재배치 하면 2 3 4 6 7로 나타낼 수 있다. 한 번의 Defile을 통해 모든 국회위원을 없애기 위해서는 1 2 3 4 5와 같이 1부터 시작해서 각 옆의 수들은 차이가 1 이내여야 한다. 2 3 4 6 7 을 1 2 3 4 5 6 으로 바꾸기 위해서는 7을 1로 만들고(해커 6명 고용) 6을 5로 만들어서(해커 1명 고용) 총 7명의 해커를 통해 1 2 3 4 5 6 을 만들 수 있다. 그러나 가장 뒤의 숫자를 가장 앞의 빈 숫자(1)로 옮기는 과정은 해커를 최소한만 사용하지는 않는다. 1 3 3 5 의 경우 가장 뒤의 숫자를 2로 바꾸면 총 3명의 해커로 1 2 3 3 을 만들 수 있지만 1 3 3 5 에서 3을 2로 바꾸고 5를 4로 바꾸..