전체 글 (52) 썸네일형 리스트형 스택/큐 - 프린터 https://www.welcomekakao.com/learn/courses/30/lessons/42587# 위 문제를 푸는 데 아래 로직을 구현하였다. 1. queue (13 line) 에 프린터 대기목록을 저장한다. 2. 우선순위 소팅이 적용되지 않은 queue 를 순회하며, 최대 우선순위를 가진 프린터를 찾고 정보를 저장한다. 3. 2번에서 찾은 정보를 기반으로 우선순위 정렬 (35~40 line)을 하는 데, 이 정보를 vector (20 line) 에 저장한다. 그리고 위 처럼 문제를 풀지 않고, maxHeap 을 사용해도 문제를 풀 수 있을 것 같다. 나중에 시간되면 해보기로.. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2.. 스택/큐 - 쇠막대기 https://www.welcomekakao.com/learn/courses/30/lessons/42585 위 문제를 푸는 로직은 다음과 같다. 1. 여는 괄호( '(' ) 는 레이저이든 막대이든 상관없이 스택에 넣는다. 2. 닫는 괄호( ')' )는 레이저이거나 막대기의 끝을 나타낸다. 그렇기 때문에 2가지로 로직으로 나뉠 수 있다. 2-1. 바로 이전 괄호가 닫는괄호일 경우, 막대기를 나타내는 데 이 경우엔 막대기의 끝점을 나타내기 때문에 마지막에 잘린 부분을 정답에 더해준다. (18 line) 2-2. 바로 이전 괄호가 닫는괄호가 아닌 경우 즉, 여는 괄호인 경우엔 레이저를 나타내므로 현재 스택에는 끝점을 만나지 않은 막대기들만 남아있으므로 스택의 크기만큼 정답에 더해준다. (19 line) 1 2.. 백준 11053번 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 101 2 3 4 1 2 3 4 5 6만약 위 예제입력 풀이1. d[i] = i번째에서 가질 수 있는 모든 부분수열의 최대 길이로 설정2. j = 0 ~ i 까지 수열을 순회3. i 번째 수 보다 j 번째 수가 더 작고, d[j] + 1 이 d[i] 보다 크다면 새로 값을 설정한다. 위 풀이를 차근 차근 따져보면 아래 그림과 같다.말로 설명하기보다 그림이 편할 것 같아서 노가다함 간단하게 말해서, 현재 i 번째 숫자까지 수열의 최대 길이를 계산하는 로직을[0 ~ 1], [0 ~ 2], ... [0 ~ N] 까지 반복하는 것이다. #include #define MAX 1000 using namespace std;int main(){ int.. 백준 1012번 유기농 배추 https://www.acmicpc.net/problem/1012 전형적인 dfs 혹은 bfs 로 풀수있는 문제이다.딱히 풀이방법을 적을 것도 없이 인접한 배추끼리는 에벌레 1마리로 벌레를 예방가능하므로인접한 배추들끼리 그룹을 지어 최소로 필요한 에벌레의 갯수를 구할 수 있다. #include #define MAX 50using namespace std;int m, n;int dx[4] = {0, -1, 0, 1};int dy[4] = {-1, 0, 1, 0};bool isInner(int x, int y) { return (x >= 0 && x = 0 && y 프로그래머스 124 나라의 숫자 https://programmers.co.kr/learn/courses/30/lessons/12899 #include #include #include using namespace std;string solution(int n) { string answer = ""; int q = 0, r = 0; char ch; do { q = n / 3; r = n % 3; n = (r == 0) ? q - 1 : q; ch = (r == 0) ? '4' : r + '0'; answer += ch; } while (q > 0); return answer;}int main() { cout 백준 9465번 스티커 https://www.acmicpc.net/problem/9465 이 문제를 풀기위해선 무작정 큰 스티커만을 찾아서 선택하는 로직을 사용해선 안된다. 100 99 99 1 만약 큰 스티커만 찾는다면 100을 찾을텐데, 이 문제의 답은 99 + 99 = 198 이기 때문이다. 풀이1. N번째 열에서 택할 수 있는 가짓수는 3가지 이다. 0 - 아무 스티커도 선택하지 않음( dp[N][0] ) 1 - 위에 스티커를 선택 ( dp[N][1] ) 2 - 아래 스티커를 선택 ( dp[N][2] ) 2. 그렇다면 N번째 열에서 최대 값은 N-1 번째 열에서 각 가짓수에 의해 결정된다. N번째 행에서 아무 스티커도 선택하지 않았을 땐 - N-1 번째 행에서 아무 스티커도 선택하지 않았을 때 - N-1 번째 행에서 위.. 백준 7562번 나이트의 이동 https://www.acmicpc.net/problem/7562 풀이1. BFS 문제2. 8방향으로 탐색하며, 이미 방문했던 노드는 다시 방문하지 않는다. bfs 알고리즘으로 탐색하기 때문에 첫 방문했을 때에 이미 가장 적은 횟수이기 때문이다. 주의사항처음에 dfs 로 풀었는 데, 개발 툴에서 답이 나오길래 제출했더니 시간초과가 떴었다.가만히 생각해보니 dfs 방식을 사용하면 (x, y) 노드에 첫 방문했을 때, 가장 적은 횟수로 방문한 것이 아니기 때문이다.그래서 내 알고리즘에도 재방문한 노드에 대해서 이동 횟수를 비교하고 작은 값을 덧씌우고 다시 dfs 탐색을 시작하기 때문이다. DFS 소스#include #include #define MAX 300using namespace std;int from.. 백준 2644번 촌수 https://www.acmicpc.net/problem/2644 풀이 입력으로 전달받은 x, y 의 촌수를 구하는 것은 바꾸어말하면 x, y 사이의 간선의 갯수를 구하면 된다.이를 depth 라고 표현하였으며 풀이 방법은 아래와 같다. 1. 입력으로 전달받은 각 부모, 자식들을 인접리스트로 구성한다. 2. 방문을 시작하기 전에 x를 queue 에 삽입한 뒤, bfs 로 각 node 를 방문한다. 3. 현재 방문한 사람(cur)의 인접한 사람(node)들의 depth 를 저장한다. 현재 방문한 사람의 depth + 1 이 인접한 사람의 depth 가 된다. 4. 마지막으로 y 의 값을 출력한다. #include #include #include #include #define MAX 100using name.. 이전 1 2 3 4 5 ··· 7 다음
