SY DevLog

백준 2841번 : 외계인의 기타 연주 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net 각 줄마다 P개의 프렛이 있다. 줄이 총 6개 이므로 각 줄별로 스택을 만들기 위해 스택 배열을 생성하고 크기를 6개로 하였다. 만약에 특정 줄(n)의 스택(stack[n])에 대해서 - 스택의 top에 있는 프렛이 현재 프렛보다 크다면, top의 프렛이 현재 프렛보다 작을 때까지 pop한다. 현재 프렛의 음을 내기 위해서는 그보다 큰 프렛에서 누르고 있는 손을 모두 떼야하기 때문이다..

백준 1935번 : 후위 표기식2 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 해시맵을 사용하여서 각 피연산자 알파벳을 key, 그 알파벳에 해당하는 정수를 value로 넣어주었다. 후위표기식으로 주어진 문자열의 문자를 차례대로 확인한다. 문자가 피연산자이면 해시맵에서 해당하는 정수값을 찾아서 스택에 넣고, 문자가 연산자이면 스택에서 연산할 값 2개를 pop한 후, 연산 결과를 다시 스택에 push 한다. 연산이 다 끝나고 마지막에 스택에 남아있는 값이 최종 연산 결과가 된다. 연산 결과가 실수..

백준 17298번 : 오큰수 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net res 배열에는 각 원소의 오큰수가 무엇인지를 넣어준다. 스택을 하나 만들고, 이 스택에는 수열 A의 원소의 인덱스(idx)가 들어간다. - A[idx] 가 아직 오큰수를 만나지 못했다면, idx는 스택에 계속 남아있게 된다. - A[idx] 가 오큰수를 만나면, 스택에서 idx가 pop되고, res[idx] 에는 A[idx]의 오큰수가 들어간다. 백준 문제의 첫번째 예제를 보면, 수열 A는 3 5 2 7 이다. 우선 res의 모든 값을 -1로 초기..

백준 1406번 : 에디터 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 스택을 이용하여 문제를 풀었다. [1차 시도] 처음에는 stack을 하나 만들어서 문자열의 문자들을 스택에 넣고, cursor 변수를 만들어서 명령어에 따라 커서의 위치를 갱신시켰다. 명령어 B(커서 전 문자 삭제)가 나오면, 현재 스택에 들어있는 문자의 개수 - cursor 만큼 스택에서 문자들을 pop을 한 다음에(그러면 스택의 맨 위에는 현재 커서 위치 바로 직전의 문자가 남아있게 된다.) 이 문자들을 임시 스택 tmp에 넣고, 제..

백준 18352번 : 특정 거리의 도시 찾기 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 다익스트라 알고리즘을 알면 쉽게 풀 수 있는 문제! 별로 어렵지 않게 쉽게 풀 수 있었다. 다익스트라 알고리즘 다익스트라(Dijkstra) 한 정점에서 다른 정점까지의 최단거리를 구하는 알고리즘 주로 간선에 가중치가 주어질 때 사용한다. 단, 다익스트라 알고리즘은 가중치가 음수인 경우에는 적합하지 않다. (이유는 나중에 설 lotuslee.tist..

백준 2143번 : 두 배열의 합 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 먼저 배열 A의 부분합들을 리스트에 저장한다. 배열 B도 마찬가지로 부분합을 구해서 리스트에 저장한다. 그리고 두 개의 리스트를 가지고 투 포인터 알고리즘을 이용하여 문제를 풀었다. 투 포인터 알고리즘 - 다른 방향으로 해결하기 투 포인터 알고리즘 - 2. 다른 방향(배열 2개) 투 포인터 알고리즘 - 다른 방향 배열에서 두 원소의 합이 어떠한 값 X와..

백준 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+..

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