기로에 서다

문제 programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴� programmers.co.kr 문제 풀이 1. 균형잡힌 문자열인지는 s를 탐색하며 '(' , ')'의 개수를 비교하면된다. 2. 올바른 괄호 문자열인지는 해당 문자가 '('이면 스택에 넣고, ')'일 때 스택에서 pop한다고 할 때 스택이 비어있는데pop하는 경우를 확인하면 된다. 코드 #include #include using namespace std; string f(string w) { vect..

문제 programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자 programmers.co.kr 문제 풀이 1. 반복되는 문자열의 길이 l은 1

문제 www.acmicpc.net/problem/19576 19576번: 약수 가능 한 방법 중 하나로, a2를 12로, a3을 3으로 바꾸면 된다. www.acmicpc.net 문제 풀이 1. 약수관계를 생각해보면 1은 모든 수와 약수관계를 이루므로 와우매직을 사용하는 경우엔 1로 바꿔주면 된다. 2. 와우매직을 최소한으로 사용하기 위해선 기존의 수들이 최대한 많은 약수관계를 이뤄야하고, 이는 수들을 정렬했을 때 각 인덱스를 시작으로 해당 인덱스의 수와 다른 수들과의 약수관계를 이루는 길이를 구하고 그 중 최댓값을 n에서 빼주면 와우매직을 사용하는 최소횟수이다. 코드 #include using namespace std; int n, dp[5001]; vector a; int go(int cur) { i..

문제 www.acmicpc.net/problem/19588 b.first; } int main() { cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); cin >> n >> m; v.resize(n + 1), pxor.resize(n + 1), pxor2.resize(n + 1); for (int i = 1; i > x >> y; v[i] = { x, y }; } auto it = v.begin(); sort(it + 1, v.end(), cmp); for (int i = 1; i > q; while (q--) { cin >> a >> b; cout

문제 www.acmicpc.net/problem/19591 19591번: 독특한 계산기 숫자, '+', '*', '-', '/'로만 이루어진 길이가 106 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −263 이상 263 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다. www.acmicpc.net 문제 풀이 1. 파싱 : 문자열을 숫자와 연산자로 파싱하는 과정이 까다롭지만 연산자가 나왔을 때, 연산자는 연산자대로 저장하고 그동안의 숫자들을 하나의 숫자로 묶어서 저장하면 쉽게 파싱할 수 있습니다. (첫 수가 음수일때 예외처리) 2. 자료구조 : 연산할 때 맨 앞과 뒤에 접근하므로 덱을 사용하여 숫자, 문자들을 관리할 수 있습니다. 3. 주어진 조건대로 연산자의 우선순..

문제 www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 문제 풀이 괄호를 사용하는 전형적인 스택문제이므로 여는 괄호를 만났을 때, 그 앞의 숫자 K값을 담는 스택(벡터)를 하나 사용한다. 문자열을 처음부터 탐색할 때 (숫자,숫자), (숫자,여는괄호)와 같이 연속된 두 문자의 종류에 따라 길이에 더해지는 값이 달라지므로 편의상 문자를 두 개씩 보기로한다. 해당 문자가 숫자일때, 스택(벡터)이 비어있다면 $Q$꼴이고 스택(벡터)이 비어있지 않다면 $K(Q)$..

문제 https://www.acmicpc.net/problem/17080 17080번: 결함 게임 첫째 줄에 돌의 개수 N이 주어진다. (1 ≤ N ≤ 5,000,000) www.acmicpc.net 문제 풀이 각 플레이어는 턴마다, 만약 현재 보드 위에 있는 돌탑 중 어딘가에 올릴 수 있는 돌이 남아있다면, 반드시 그러한 돌들 중 하나를 골라 올릴 수 있는 돌탑 중 원하는 돌탑 위에 올린다. 만약 어떤 돌탑에도 돌을 올릴 수 없다면, 남아있는 돌 중 아무거나 하나를 골라 보드 위에 새로운 돌탑의 바닥을 만든다. 모든 돌이 소진된 뒤, 돌탑의 개수가 홀수이면 선공이 이기며, 짝수이면 후공이 이긴다. 위 조건들을 생각하며 돌의 개수를 한 개씩 늘려보면 아래의 규칙을 찾을 수 있습니다. 1. k개의 돌을 둬..

문제 https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 문제 풀이 1. 정확하게 순위를 매길 수 있다는건 이길 수 있는 선수의 수와 만나면 지는 선수의 수를 안다는 것이고, 이들을 합했을 때 자신을 제외한 N-1명이라는 것입니다. 2. 모든 선수간의 승,패 관계의 관계는 N v 이고 v > w 이면 u > w) 각 선수의 이길 수 있는 선수의 수와 만나면 지는 선수의 수를 하나씩 올려주면됩니다. 코드 #include #include using namespace std; int in[101],out[101]; // in..

문제 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제 풀이 단순하게 시간복잡도를 생각해본다면 $O(C*M*s)$ = $O(10^9)$로 TLE가 남 따라서 상어의 움직임을 줄여야 했고 아래의 관찰을 통해 해결함 (상어 H가 같은 위치로 돌아오는데 걸리는 시간) = (오른쪽으로 갔다가 돌아오는 시간) + (왼쪽으로 갔다가 돌아오는 시간) 이는 좌표를 우측 90도 방향으로 돌렸을때, (위,아래)로 움직이는 상어들도 동일하게..