본문 바로가기

알고리즘 풀이

 (50)
백준 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..
백준 14501번 퇴사 https://www.acmicpc.net/problem/14501 이 문제는 혼자 힘으로 하려다가.. 결국 다른사람의 코드를 보고 이해하였다. 아래가 참조한 블로그이다.http://jongnan.tistory.com/9 풀이1. N번째 날에 가질 수 있는 최대 금액 d[N] 을 구해야 한다. 2. N번째 날에 선택할 수 있는 경우는 2가지이다. - N번째날 상담을 한다 -> N번째 날 금액(P)을 받고, T일이 지난 후에 다시 상담여부 결정 ( find(day + T[day]) + P[day] ) - N번째날 상담을 하지 않는다. -> 다음 날부터 다시 상담여부를 결정 ( find(day + 1) ) 3. 딱 N번째 날에 끝난다면 - 0을 반환 ( day == N + 1 ) N번째 날을 초과한다면 - ..
백준 15686번 치킨배달 https://www.acmicpc.net/problem/15686 위 문제는 모든 경우의 수를 다 탐색해야하는 문제이며 백트래킹 알고리즘을 적용해야 한다.예를들어 5개의 치킨집이 있고, 그 중 2개를 방문해야 한다면 1. 1 1 0 0 02. 1 0 1 0 03. 1 0 0 1 0 ... ... 0 0 0 1 1 까지 모든 경우의 수를 탐색해야 한다. 최대 M 개의 치킨집을 찾았다면 해당 case 에서 최소 거리가 되는 치킨거리를 구한다.이후 위에서 설명한 모든 경우의 수에서 최소 거리가 되는 치킨거리를 구하면 된다. #include #include #include using namespace std;vector clients;vector stores;bool visit[13] = {false, };i..

티스토리툴바