Algorithm (PS)

유형 : 구현 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 이 문제에서 어렵다고 느껴졌던 점은 바라보는 '방향'도 고려해서 새로운 좌표로 이동시키는 것이었다. 현재 바라보는 방향을 t라고 이름붙이겠다. 옆의 그림과 같이, 문제에서 북-동-남-서 순서대로 바라보는 방향을 지정했다. 그리고 북쪽을 바라보는 상황에서 앞으로 한칸 전진하면 서쪽, 동쪽을 바라보는 상황에서 앞으로 한칸 전진하면 북쪽, 남쪽을 바라보는 상황에서 앞으로 한칸 전진하면 ..

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제! 이 문제는 그리디 유형이다 알파벳 중에서 가중치가 높은 순서대로 9 8 7 ~ 0 숫자를 부여해주어야 하기 때문이다. 가중치는 자리수 !!! 라고 생각하면 된다 그러면 쉽게 풀린다 예를들어 입력으로 GCF ACDEB 가 입력되었으면 A는 만의 자리이므로 10000 라는 가중치를 가지게 되고 C의경우는 첫번째 단어에서는 10 , 두번째 단어에서는 1000 이므로 총 1010 라는 가중치..

유형 : 그리디 a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1] 의 최소값을 구하는 것이고 사실 문제에서는 a배열만 바꾸고 b배열은 순서 냅둬! 라고 했지만 우리는 최소값만 구해서 출력해주면 되므로...^^ 사실 a배열 순서도 움직여줘도 상관없다 ㅋㅋ a를 오름차순 b를 내림차순 정렬한 후에 각각의 원소들을 for문안에서 곱한 값들을 더해주면 된다 !

1. 그래프 자료구조 union-find 알고리즘은 그래프 자료구조형에서 적용된다. 그래프의 구현방법은 2가지 방식이 존재한다 1) 인접행렬 (Adjacency Matrix) : 2차원 배열을 사용하는 방식 공간복잡도: 노드의 개수가 V, 간선의 개수가 E인 그래프가 있을 때, 인접행렬은 O(V^2) 만큼의 메모리가 필요하다 시간복잡도: 특정한 노드 X에서 다른 노드 Y로 가는 간선의 비용을 O(1)의 시간으로 알아낸다. 2) 인접 리스트 (Adjacency List) : 리스트로 연결하여 사용하는 방식 공간복잡도: 간선 개수만큼인 O(E) 시간복잡도: 특정한 노드 X에서 다른 노드 Y로 가는 간선의 비용을 O(V)의 시간으로 알아낸다. 2. 서로소 집합 서로소 집합은 공통 원소가 없는 두 집합이다. 서..

1. 그래프 자료구조 union-find 알고리즘은 그래프 자료구조형에서 적용된다. 그래프의 구현방법은 2가지 방식이 존재한다 1) 인접행렬 (Adjacency Matrix) : 2차원 배열을 사용하는 방식 공간복잡도: 노드의 개수가 V, 간선의 개수가 E인 그래프가 있을 때, 인접행렬은 O(V^2) 만큼의 메모리가 필요하다 시간복잡도: 특정한 노드 X에서 다른 노드 Y로 가는 간선의 비용을 O(1)의 시간으로 알아낸다. 2) 인접 리스트 (Adjacency List) : 리스트로 연결하여 사용하는 방식 공간복잡도: 간선 개수만큼인 O(E) 시간복잡도: 특정한 노드 X에서 다른 노드 Y로 가는 간선의 비용을 O(V)의 시간으로 알아낸다. 2. 서로소 집합 서로소 집합은 공통 원소가 없는 두 집합이다. 서..

금광 이동방향은 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 이다. 이를 현재 내 위치인 dp[i][j]에서 보면 왼쪽 위, 왼쪽, 왼쪽아래에서 내 위치로 오는 3 가지 경우가 있다는 의미이다 하지만 이렇게 i == 0 인 경우에는 왼쪽위에서 올 수 없으므로 left_top = 0 이다. 그렇지 않은 경우에는 left_top = dp[i-1][j-1] 이다. 다음의 경우는 3가지 방향 모두 유효하니까 경우를 더 나눌 필요 없이, left = dp[i][j-1] i == (n-1) 인 경우에도 왼쪽아래에서 오는 경우는 불가능 하므로 이 경우 left_bottom = 0이라고 처리해 준다. 그렇지 않은 경우는 left_bottom = dp[i+1][j-1] 이다. 그리고 이 값들 중에서 max 값과 dp[i][..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 이 문제를 풀 때 핵심적인 아이디어는, 뒤쪽 날짜부터 거꾸로 확인하는 방식으로 다이나믹 프로그래밍 알고리즘을 수행해야 한다는 것이다 ! 문제에서 주어진 예시 N = 7 인 경우에는 6일과 7일자의 상담을 수행하면 7을 넘기게 된다. 이와 같은 경우를 고려하기 위해서 뒤에서부터 DP를 수행하여 저장한다. 경우를 나누는 것은 두가지로, i번째 날의 상담을 수행했을 때 n을 넘는다면 이 경우는 불가능하니까 value를 0이라고 생각하여 dp 그래프에 0 값으로 처리를 한다. dp[i] = dp[i+1] # 단, 여기서 dp list의 맨 ..

https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 결국 BFS를 이동해서 로봇이 (n,n)에 도달할때까지의 최단거리를 구한다. 1. 벽을 하나 둘러싼 모양으로 확장된 보드를 만들어서 (1,1) ~ (n,n) 이라고 생각하기 쉽게 해준다. 2. 갈수있는 위치를 구하는 함수는 갈수 있는 위치의 리스트를 리턴한다. 3. 갈수 있는 위치는 queue에 넣고, 방문하면 visited에 넣는다. 일반적인 bfs로 , 큐가 빌 때까지 반복한다. 4. 갈..