동적프로그래밍 문제이다 .... ! https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제풀이 문제 자체는 굉장히 심플하다. 연속되는 수를 선택해서 구할 수 있는 합 중에 가장 큰 합을 구하는 문제이다. 예제입력 2를 보게 되면 3 4 -4 6 5 가 선택되어 출력이 14가 나왔다. 즉, 음수, 양수를 신경쓰지 않고 선택하는 것이다. 점화식도 간단하게 구할 수 있다. 이전까지 탐색했던 값과 현재 위치의 값을 비교하여 더 큰 값을 저장하면된다. memo[0]..
문제해결프로그래밍 수업에서 동적프로그래밍을 하고 있던 차라 정리하면서 간단한 문제를 하나 풀어보았다. https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 들어가기 앞서 동적프로그래밍(Dynamic Programming)이란 얼핏보면 어려워보이지만 사실 동적계획법에서 동적이란 "기억"을 의미한다. 메모이제이션을 이용하여 이미 계산된 결과를 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 하는 방식이다. 정말 말그대로 기억을 해두는 것이다. DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식) 두가지 방식으로 구성된다. 하향식은 재귀..
알고리즘 분류는 구현, 자료구조, 큐이다. 문제 1부터 N까지의 카드에 대해서 한장은 버리고, 그 다음장은 맨 아래로 옮기는 것이 카드가 1장이 남을때까지 반복 된다. 1부터 4까지 있을 때 1 2 3 4 -> 1은 버리고 2는 아래로 옮기면서 3 4 2 -> 3은 버리고 4는 아래로 옮기면서 2 4 -> 2를 버리면 카드가 4 한장이 남기 때문에 버린 순서대로 -> 1 3 2 4 가 정답이 되게 된다. 버린 카드: 1 3 2 마지막 카드: 4 풀이 큐를 이용하여 간단하게 문제를 풀어보았다. 1~N까지의 수를 큐에 넣고, 큐에 첫장은 빼서 바로 출력하고, 그 다음장은 빼자마자 큐에 다시 넣는 작업을 큐의 사이즈가 1보다 클때까지만 while문을 이용하여 반복하였다. 그 후엔 마지막 장을 출력해주면 된다...
전공공부에 매진하다보니 백준을 푼지 오래된 것 같아서 차근차근 다시 풀어보려고 한다. https://www.acmicpc.net/problem/6550 6550번: 부분 문자열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문자열 s 와 t가 빈칸을 사이에 두고 들어온다. s와 t의 길이는 10만을 넘지 않는다. www.acmicpc.net 위 문제는 입력이 없을 때 까지 반복처리를 해야하기 때문에 while문을 이용하여 eof 처리를 진행하였다. 백준의 경우에는 입력 자체가 파일로 처리되기 때문에 아래 코드로 정상처리가 되지만 Intellij는 IDE에서의 입력이기 때문에 끝을 찾지 못해서 따로 control+D 를 이용한 종료를 해야한다. while..
백준 7578번 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 백준 7569번 토마토 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net ..
백준 10026번 적록색약 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 알고리즘분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 2차원 배열 델타 사용 2차원 배열을 델타를 이용하여 풀었다. 한 지점을 8방향으로 탐색할 때 좌표값의 계산은 위 사진과 같다. y값이 증가할 수록 아래로 이동한다. 적록색약 문제는 4방향 탐색이기 때문에 x, y = {-1, 0}, {1, 0}, {0, -1}, {0, 1} 상하좌우 좌표값만을..
백준 1260번 DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS(깊이 우선 탐색)란? DFS(깊이 우선 탐색, Depth-First Search)란 그래프의 가장 깊은 곳부터 탐색하는 것으로 자기 자신을 호출하는 순환 알고리즘에 형태를 가지고 있다. 주로 스택(Stack)으로 구현되며, 아래코드도 스택을 이용하여 구현되었다. BFS(너비 우선 탐색)란? BFS(너비우선 탐색, Brea..
그리디 알고리즘이란? greedy: 1. 탐욕스러운 2. 욕심많은 사전 상의 의미와 같이 탐욕 알고리즘이라고도 부른다. 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고완된 알고리즘으로, 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법임 동적 프로그래밍을 대체하는 것이 아닌, 같이 쓰이며 서로 보안하는 개념으로, 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘 창의력(문제를 풀기 위한 최소한의 아이디어)를 요구하는 문제 유형 그리디 알고리즘을 사용하여 프림 알고리즘과 다익스트라 알고리즘 구현가능 다익스트라 알고리즘의 경우 그리디 알고리즘이지만 암기가 필요한 유형문제 출제 유형의 폭이 넓기 때문에 특이 케이스를 제외하고는 단수 암기를 통해 모든..
