꼼개의 개발자취

문제 : https://www.acmicpc.net/problem/5557 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제설명 탐색문제일까 싶었지만 N이 100이면 최악의 경우가 2의 99승까지 가기 때문에 무조건 DP로 풀어야 한다고 생각했다. 근데 DP의 가장 큰 문제는 점화식을 찾기 어렵다는 것이다. 30분 정도 고민해 봤지만 역시 생각해내기 어려워 다른 사람 풀이를 참고하였다. 알고리즘 핵심 변수는 dp[N][21] 인데 'N번 째 일 때 값이 0이상 20이하 이다.'를 나타낸 것이다. 이해하기가 쉽지 않은데 이 그림을 보면 이해하기 쉬울 것이다. 아래와 같은 예제가 주어졌을 때 5 9 3 3 3 ..

문제 : https://www.acmicpc.net/problem/2493 [ 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net ](https://www.acmicpc.net/problem/2493) 문제설명 단순 반복문을 사용한 구현문제로는 제약조건 때문에 시간초과가 날 수 있다. 1개의 for문을 사용하되 문제를 풀 수 있는 방법 하면 stack이 생각나야한다. 알고리즘 1. for문을 이용하여 앞에서 부터 스캔하며 stack에 값을 push한다. 2. 조건문안에 stack이 비었으면 자신보다 큰 탑이 없..

구현코드 문제 : https://www.acmicpc.net/problem/1966 [ 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net ](https://www.acmicpc.net/problem/1966) 문제설명 1. 제목 그대로 큐를 사용하면 된다. 자료구조을 이용하는 문제임을 쉽게 알 수 있다. 알고리즘 1. queue 와 중요도가 높은 문서를 알 수 있는 어떠한 가이드가 필요하다. 2. 가이드를 vector를 이용했다. vector를 정렬하여 높은 숫자가 빠지면 vector의 index도 증가하도록 하였..

문제 : https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 문제설명 1. 푸는 방법이 굉장히 많다. 어떤 방법으로 푸느냐에 따라 난이도가 달라지는 것 같다. 알고리즘 1. 먼저 가장 높은 위치를 구한 뒤 왼쪽과 오른쪽으로 나눠 생각한다. 2. 왼쪽부터 가장 높은 위치 인덱스 까지 반복문을 진행한다. 조건은 최대값인 tempValue 보다 현재위치의 높이가 크거나 같을 때 최대인덱스인 tempIdx부터 현재 위치까지 반복문을 진행..

문제 : SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제설명 1. 조합문제이다. 21개의 조합 중(anta tica 제외) 제한시간이 1초는 중복제거를 한다면 충분히 가능한 시간이다. 알고리즘 1. 남극언어의 특징인 접두사와 접미사는 무조건 읽어야만한다.(anta tica) 2. 21개의 알파벳과 K - 5 만큼 조합한다. 3. 조합된 원소를 이용해 읽을 수 있는 단어를 체크한다. 주의사항 1. 남극언어 필수 알파벳 5개보다 가르칠 수 있는 개수가 적으면 읽을 수 있는 단어는 0이다. 2. DFS 함수 구현 시 idx 변수를 통해 했던 조합은 중복 제거를 해야한다. 안그러면 시간초과 발생 구현 bool a..

문제 : https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 문제설명 괄호가 나오는 문제이다. 괄호가 나오는 문제는 왠만하면 스택을 사용하고, 여기서는 temp 변수가 핵심이다. 알고리즘 1. 열린 괄호가 나오면 stack에 push하고 괄호 모양에 따라 temp에 특정 값을 곱해준다. 분배 법칙이라 생각하면 이해하기 쉽다. 2. 닫힌 괄호가 나오면 바로전에 닫힌 괄호에 맞는 열린괄호가 있으면 result에 값을 더해주고 조건이 틀리면 break..

문제 : www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 문제설명 단순 구현 시뮬레이션 문제이다. 배열 회전하는 방법과 BFS를 사용하면 쉽게 풀 수 있다. 알고리즘 1. 배열을 스캔하며 나눠진 구역마다 회전해준다. 회전 방법은 코드에 주석처리 해놨다. 2. 회전 후 인접한 4방향을 탐색하고 조건을 실행한다. 3. 모든 명령을 마친 후 BFS을 통해 가장 큰 덩어리의 개수를 구한다. 주의사항 1. 구역을 나누고 회전하는 부분이 까다로웠는데..

문제 : www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 문제설명 단순 구현 시뮬레이션 문제이다. 알고리즘 1. 문제 설명에 나와있는 5x5의 흩날리는 비율을 각 토네이도 방향마다 적용시켜준다. 2. 4방향 모두 만들어준다. 3. 토네이도를 이동하며 방향에 맞는 배열을 적용시켜 계산한다. 주의사항 1. 구현 문제는 조건을 주의해야한다. 조건을 미리 종이나 메모장에 적어논 다음 코딩하는 것이 실수를 줄이는 방법같다. 2. 4방향..

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제설명 다양한 푸는 방법이 존재한다. 조합을 이용하여 풀면 쉽게 풀 수 있다. 알고리즘 1. DFS를 이용하는데 종료조건은 투약횟수보다 cnt가 커지거나 세로길이를 넘어갈 때 이다. 2. 조건을 만족하면 최솟값을 구하고 return 한다. 3. 투여했을 때 안했을 때를 나눠서 조합으로 탐색한다. 구현 static int D; //두께 static int W; //가로크기 static in..

문제 : https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작�� www.acmicpc.net 문제설명 문제를 처음 보면 단순한 DFS/BFS 문제로 느껴진다. 그러나 단순 탐색으로 찾는다면 많은 반례들이 있다. 예를 들어 십자가 모양으로 있는 TK를 통과하진 못한다. 사실 5x5 배열에 제한시간이 2초라는 것은 단순 탐색으로는 풀 수 없다는 걸 뜻한다. 그러므로 5x5 = 25개의 학생중에 7명을 뽑는다고 생각해야한다. 알고리즘 1. 25명의 학생중 7명을 뽑는다. 2. 뽑은 학..