SY DevLog

백준 17281번 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 문제 자체는 어렵지 않으나, 평소 스포츠 룰을 잘 몰라서 문제를 이해하는데 시간이 좀 걸렸다. 핵심은 아홉번의 차례 동안, 1번 타자는 4번째로 고정되고 나머지 타자들은 순서를 정해줘야 한다. 이 부분은 순열에 해당하므로 재귀를 이용하여 브루트포스로 모든 케이스를 구하였다. 9번째까지 모든 순서를 정하고 나면 solve() 메서드를 호출해서 N번의 이닝이 모두 끝날 때까지 score를 갱신시켜준다. 매번 타자가 공을 던진 후, 갱신된 score을 ma..

백준 17779번 : 게리맨더링 2 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 배열을 돌면서 매 위치마다 가능한 모든 d1과 d2 에 대하여, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이를 구한다. 배열의 마지막까지 다 완료한 후 min 변수에 있는 값이 최소값이 된다. 소스코드 :

백준 16697번 : 괄호 추가하기 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 브루스포스로 쉽게 해결할 수 있는 문제였다. 괄호 안에는 하나의 연산자만 들어가야 한다. 하나의 연산자만 들어가므로 괄호 안에 정수는 두 개만 들어갈 수 있다. 수식 안에 정수가 n개 있을 때, 수식에 넣을 수 있는 괄호의 수는 0개 부터 (n/2)개까지 넣을 수 있다. ex) 수식이 1+2+3+4+5 일 때, 최대로 괄호를 넣으면 1+(2+3)+(4+5) 로 두 개까지 넣을 수 있다. * 이 때, (1+2)+(3+..

한 정점에서 다른 정점까지의 최단거리를 구하는 알고리즘 주로 간선에 가중치가 주어질 때 사용한다. 단, 다익스트라 알고리즘은 가중치가 음수인 경우에는 적합하지 않다. (이유는 나중에 설명) 우선순위 큐를 이용하지 않고 구현하는 방법과 우선순위 큐를 이용하여 구현하는 방법이 있다. 우선순위 큐를 이용할 때 시간복잡도는 더 줄어든다. 시간 복잡도 : O(N²) 다익스트라 알고리즘을 구현할 때 필요한 몇 가지가 있다. - 시작점과 각 정점들간의 최단거리를 저장하는 이차원 배열 dist[start][end] : start 정점부터 end 정점까지의 최단거리 과정을 진행하면서 계속해서 최단거리를 업데이트하기 때문에 처음에 dist 배열의 모든 요소를 Integer.MAX_VALUE 값으로 초기화해준다. 그리고 새..

백준 14697번 : 방 배정하기 14697번: 방 배정하기 정보 초등학교 6학년 여학생들은 단체로 2박 3일 수학여행을 가기로 했다. 학생들이 묵을 숙소에는 방의 정원(방 안에 있는 침대 수)을 기준으로 세 종류의 방이 있으며, 같은 종류의 방들이 여러 www.acmicpc.net 브루스포스 알고리즘이며, 나는 재귀를 이용하여 문제를 풀었다. 재귀의 base case를 방 배정을 성공(true)하느냐, 실패(false)하느냐로 나눴는데, 꼭 모든 방에 학생을 배분할 필요가 없으므로, 아직 모든 방에 배정하기 전인데 남은 학생 수가 0이 되어도 탈출 조건이 될 수 있다. - 모든 방에 배정 여부와 관계없이 남은 학생이 0명이면, true를 반환 - 마지막 방까지 배정했을 때, 남은 학생이 존재하면 fal..

백준 17136번 : 색종이 붙이기(삼성 SW 역량 테스트) 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 그리디 + 백트래킹으로 해결할 수 있는 문제 나는 재귀를 이용하여 문제를 풀었다. 배열을 돌면서 큰 색종이부터 붙일 수 있는지 확인한다.(그리드 방식) 현재 위치에서 5x5 크기의 색종이를 붙일 수 있으면 붙인다. 다음 위치로 이동해서, 5x5 크기의 색종이를 붙일 수 있으면 붙인다. ... 배열의 마지막 위치로 이동해서 5x5 크기의 색종이를 붙일 수 있으면 붙인다. 마지막 위치에서 색종이 크..

LIS(Lowest Increasing Subsequence) : 최장 증가 수열 : 어떤 수열이 주어졌을 때, 그 수열에서 가장 긴 증가하는 부분 수열을 구하는 알고리즘 (최장 증가 수열의 요소가 꼭 연속하지 않아도 됨) 1. 최장 증가 수열을 나열하는 문제 2. 최장 증가 수열의 길이를 구하라는 문제 보통 이 두가지 문제가 기본적이다. 여기서는 최장 증가 수열의 길이를 구하는 알고리즘을 볼 것이다. 1번 케이스의 경우, 수열 자체를 구하는 것이기 때문에 수열 요소의 추적이 별도로 필요하다. 시간 복잡도 : O(NlogN) 대략적인 알고리즘은 아래와 같다. 증가하는 수열을 저장하는 리스트가 필요하다. 리스트는 증가하는 수열을 저장하고 있기 때문에 계속 오름차순 상태를 유지하면서 갱신된다. 수열의 요소를..

백준 15904번 : UCPC는 무엇의 약자일까? 15904번: UCPC는 무엇의 약자일까? 첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열의 맨 앞과 맨 끝에 공백이 있는 경우는 없고, 공백이 연속해서 2번 이상 주어지는 www.acmicpc.net 알고리즘 : 그리드 알고리즘, 문자열 어렵지 않은 문제 String 메서드만 적절히 사용하면 쉽게 풀 수 있는 문제다. 입력 받은 문자열의 첫번째 위치부터 시작하여 차레대로 indexOf(찾으려는 문자, 시작 인덱스) 메서드를 이용한다. 'U', 'C', 'P', 'C' 문자가 존재하는지 하나씩 검사한다. 'U' 문자를 찾으면 'U'의 위치 인덱스 +1 부터 'C' 문자가 있는지 확인한다. ..

백준 15903번 : 카드 합체 놀이 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 크게 어렵지 않은 문제. 문제를 보자마자 우선순위 큐를 사용해야겠다는 생각이 들었다. 카드 중에서 제일 작은 수 두 개를 뽑아서 합을 구하는 과정을 반복하면 되기 때문이다. 우선순위 큐는 매번 제일 작은 값을 찾을 때 유용하게 쓰일 수 있다. 알고리즘 : 1. 우선순위 큐에 카드를 모두 넣는다. 2. 카드 중에서 제일 작은 두 수를 뽑은 뒤, 그 합을 구한 다음, 다시 우선순위 큐에 합을 ..

소수찾기 알고리즘 2부터 시작해서 배수가 되는 수를 지워나가면 다 지우고 최종적으로 남은 수들이 소수가 된다. 소수가 아닌 수를 걸러내는 것이 체로 걸러내는 모양과 비슷해서 '에라토스테네스의 체' 라고 부름 시간 복잡도 : O(N*log(logN)) 알고리즘 : 1. 2부터 N까지 소수를 구하고자 하는 범위의 모든 수를 나열 2. 2를 제외한 2의 배수를 모두 지움 3. 3을 제외한 3의 배수를 모두 지움 4. 5를 제외한 5의 배수를 모두 지움 ... ?. n을 제외한 n의 배수를 모두 지움 (여기서 n은 n*n