MZ 개발자

원재가 어떤 물건을 조건 하에 사재기를 하려고 하는데 조건은 다음과 같다. 1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다. 2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다. 3. 판매는 얼마든지 할 수 있다. 예를들어 5일동안 물건의 매매가를 6 9 1 1 3 으로 알고있을때 조건을 만족했을때 최대로 얻을 수 있는 이득은 6을 사고 9에 팔고 1을 사고3에 팔아서 총 7만큼 최대 이익을 챙길 수 있다. 처음 문제를 보았을때 최대 이익을 얻기 위해서 우선순위 큐를 생각하였다. 하지만 이를 이용하면 인덱스의 순서가 바뀌게 되어 우선순위 큐를 관리해주어야 한다. 우선순위 큐를 이용하여 구현한 방식이다. #include #include #include #inclu..

이 문제는 record가 주어지고 각각을 공백으로 구분했을때 첫번째는 타입, 두번째는 유저 아이디, 세번째는 닉네임이 주어진다. 각각의 타입에 맞게 결과를 기록 및 유저 아이디를 변경 해야한다. 구현을 하기 앞서 문제 분석을 먼저 하였다. (특히 프로그래머스 문제는 문제 길이가 길고 이해 하는데 어려움이 있다.) 아이디어 문제 구현에 필요한 변수부터 생각해보자. 1. record에 포함된 내용은 각각 "타입", "유저 아이디", "닉네임"이므로 이 3개를 저장할 변수가 필요하다. 2. 결과를 저장할 배열이 필요하다. => vector answer 3. 타입에 따라 특정 유저 아이디의 닉네임을 저장할 공간이 필요하다. => map m 상태를 그냥 배열에 pair 이렇게 저장할경우 Change 타입시 모든 ..

이 문제는 정점 쌍이 주어지면 트리의 부모가 누구인지 찾는 문제이다. 문제의 예제 입력이 너무 깔끔하게 되어있어서 쉽게 생각할 수 있지만 현재 노드에서 어떤 인접리스트를 탐색해야 할지 생각이 필요한것 같다. 처음 문제를 보았을때 인접리스트를 바로 떠올리지는 않았다. 유니온-파인드인가..?? 생각을 해봤는데 아닌것 같았고.... 뭔가 다음 노드로 이동할때 마다 이동한 노드의 부모 노드를 표시해줘야 할것 같은데 한참을 생각하다가 인접리스트를 이용한 완전 탐색을 떠올렸다. 문제의 예제를 인접리스트와 그래프로 표현하면 다음과 같다. 이제 그래프 완전 탐색을 하면서 현재의 노드의 부모가 어떤건지 표현해주면 된다. 여기서 주의할 점은 단순 dfs로 문제를 풀때 이미 탐색이 끝난 노드는 재방문 하지 않돌고 visit..

이 문제는 N개의 물건중 몇개를 골라서 그 고른 물건의 무게가 K보다 작거나 같게 하였을때 얻을수 있는 가치의 최댓값을 구하는 문제이다. 처음 문제를 보았을때 물건을 무게순으로 정렬하여 모든 케이스에 대해 전부 탐색을 할까 생각했다. 하지만 이렇게 풀었을때 O(n!)의 시간 복잡도가 나오게 된다. 예를 들어 n이 100이라고 하였을때 1개를 선택해서 그 가치가 최대가 될수 있지만 100개를 전부 선택을 해야 가치가 최대가 될수 도 있다. 따라서 각각의 경우에 최악의 경우 100,99,98...개를 선택해야하는 경우가 발생한다. 이 문제를 해결하기 위해 2차원 배열 dp[i][k]를 생성하고 i는 n개의 물건중 i번째 물건을 선택한경우, k는 무게 제한으로 1부터 k 까지 모든 경우에 dp를 채워나가면 된..

이 문제는 I,O로 구성된 문자열 중 IOI 가 몇개 포함되어 있는지 갯수를 구하는 문제이다. 처음 단순 부르트포스 방식으로 접근했다면 당연히 만점을 받지 못했을 것이다. 서브테스크 1의 경우 N> s; solution(); } 다음은 KMP 알고리즘을 활용한 풀이이다. 자세한 알고리즘 설명은 여기를 확인하면 된다. 알고리즘 - KMP 안녕하세요. 오랜만에 문어체로 시작하는데요, 학부동안 배운 알고리즘 또는 배우지 못한 다양한 알고리즘 및 자료구조 이론을 정리해보려고 합니다. 설명 과정에 틀린 부분이나 추가해야할 부 devconf.tistory.com #include #include #include using namespace std; int n, m; string s; vector getSkipTabl..

이 문제를 읽어보면 배열을 뒤집고 삭제하는 작업이 여러번 반복되는 문제임을 알수 있다. 일반 백터를 활용하여 풀기를 시도한다면 원소의 제일 첫번째를 삭제하는것 뿐만아니라 값을 뒤집는것 또한 귀찮은 일이다. 이때 이를 손쉽게 할수 있는 덱(dequeue)을 사용하면 간단히 해결 가능하다. 입력 문자열을 파싱하여 R일경우 뒤집힘을 알수 있다. 여기서 덱의 특징을 이용한 간단한 트릭을 사용한다면 다음과 같이 생각해볼 수 있다. 1. R이 나오지 않은 상태에서 D를 만난다면 덱의 front에서 pop을 해준다. 2. R이 나올때마다 pop의 위치를 바꿔준다. 위의 방법을 반복하여 수행한 후 마지막 출력시 현재 상태가 front인지 back 인지 확인 후 알맞게 출력해 주면된다. #include #include ..

이 문제는 기본적인 DFS를 활용한 땅 갯수 구하기와 비슷한 문제이다. 문제에서 정상인이 보이는 색과 적록색약이 보이는 색이 다르다. 따라서 각각 정상인 경우와 적록색약인 경우로 나누어 각각 DFS를 돌리면 된다. #include #include #include #include using namespace std; char rgb[102][102]; char rb[102][102]; bool visited[102][102]; int dx[4] = { 0,1,0,-1 }; int dy[4] = { 1,0,-1,0 }; int n; int rgbCnt = 0, rbCnt = 0; void dfs(int x, int y, char arr[][102],char c) { if(visited[x][y]) { ret..

이 문제는 A라는 수를 DSLR 규칙을 이용하여 B로 바꾸는데 필요한 최소한의 명령어를 나열하여 출력하는 문제이다. 처음 문제를 보았을때 숫자를 자릿수로 쪼개서 deque으로 저장할까 라는 생각을 하였다. 이 방법을 이용하면 L,R은 쉽게 풀수 있지만 D,S는 자릿수를 다시 계산해야 하는 번거로움이 생긴다. 그냥 숫자로 접근해보자!! DSLR을 숫자로 접근해보면 다음과 같은 식으로 표현할 수 있다. D: (n * 2) % 10000 S: (n - 1) < 0?9999:n - 1 L: (n % 1000) * 10 + (n / 1000) R: (n % 10) * 1000 + (n / 10) 이제 A숫자에서 B로 만들기 위해 우리는 DSLR을 반복해서 수행해야 한다. 처음에는 시뮬레이션 문제인가 헷갈렸다. 알..

안녕하세요. 오랜만에 문어체로 시작하는데요, 학부동안 배운 알고리즘 또는 배우지 못한 다양한 알고리즘 및 자료구조 이론을 정리해보려고 합니다. 설명 과정에 틀린 부분이나 추가해야할 부분이 있으면 언제든지 답글 달아주시면 감사하겠습니다. 오늘 배워볼 알고리즘은 KMP 알고리즘입니다. 문자 검색을 하는 가장 기본적인 방법은 부르트포스 방법으로 순차적으로 패턴을 비교하는 방법이지만 이 방법으로하면 패턴(M)이 길어지거나 문자(N)가 길어진다면 O(NM)의 시간복잡도를 가지게 됩니다. (여기서는 부르트포스 방법은 설명하지 않겠습니다.) KMP (Knuth Morris Partt Algorithm) 앞서 언급했듯이 부르트포스 방법으로 구현한다면 시간 복잡도는 O(NM)입니다. KMP 알고리즘은 부르트포스 알고리즘..

이 문제는 전형적인 분할 정복과 재귀를 사용하여 풀이하는 문제이다. 분할 할때 '('를 출력하고 정복시 ')'를 출력해주면 된다. 이와 비슷한 문제로 백준 2630 색종이 만들기가 있다. 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 위의 색종이 만들기 문제의 풀이는 여기를 참고하면 된다. 다음은 이 문제 풀이이다. #include #include #include using namespace std; char map[64][64]; string result = ""; void so..