본문 바로가기

전체 글262

[알고리즘 문제] 백준1520 - 내리막 길 www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 처음에 dfs를 생각했다. 근데 출력결과를 보면 최대10억까지 나올 수 있다고 되어있다. 그렇다면 탐색해야 하는 경우의 수는 10억보다 더 많을 것이고...무조건 시간초과가 나온다. 또 각 위치에서 4방향을 움직일 수 있고 가로/세로의 크기가 최대 500이기 때문에 시간 복잡도는 4^250000이 된다. 아무튼 일반적인 dfs로 풀면 안된다. 다음 생각해본 방법은 dp로 푸는 방법이다. 현재 dp[y][x]에.. 2020. 10. 15.
[알고리즘 문제] 백준1197 - 최소 스패닝 트리 www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 � www.acmicpc.net 최소 스패닝이란 모든 노드가 연결되면서 그 간선들의 합이 최소가 되는 트리입니다. 각 간선의 정보를 가중치가 작은순으로 정렬하고 사이클이 형성되지 않도록 간선을 하나씩 추가해주면 됩니다. 여기서 사이클의 형성여부는 각 노드의 부모값이 같은지를 확인하면 되며 코드상에서는 이를 parent[]로 표현하였습니다. #include #include #include usi.. 2020. 10. 14.
[알고리즘 문제] 백준1987 - 알파벳 www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 전형적인 dfs문제 입니다. 알파벳을 체크와 이미 방문한 곳인지를 검사하면서 탐색하고 이동할때마다 max값을 갱신해주는 방법을 사용하였습니다. #include #include using namespace std; int ans = -1; int width, height; char arr[21][21]; int visited[21][21]; int check[91]; int dx[4] = {0, 1, 0,.. 2020. 10. 14.
[알고리즘 문제] 백준3109 - 빵집 www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 � www.acmicpc.net dfs로 문제를 풀 수 있으며 왼쪽 시작점을 1행 ~ R-1까지 시작점을 바꾸어 가면서 각 시작점에서 출발하여 오른쪽 끝에 도착할 수 있다면 +1을 해줍니다. 여기서 무조건 방문할 때마다 visited[y][x]=1을 해주는데, 이는 y,x위치에서 파이프를 연결할 수 있는지, 없는지 모르지만 어쨋든 방문했다를 표시하기 위함입니다. 다른 시작위치에서 y,x를 간다고 하여도 이미 y,x를 거쳐가는 경우 파이프를 연결할 수 있는.. 2020. 10. 13.
[알고리즘 문제] 백준1038 - 감소하는 수 www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 �� www.acmicpc.net 문제는 bfs를 사용하여 해결할 수 있습니다. 743이라는 이후의 숫자는 마지막숫자보다 작은 숫자들, 7432,7431,7430이 올 수 있습니다. 그리고 arr[j]의 값은 j번째 숫자를 의미하며 que를 순회하면서 마지막 숫자에 그보다 작은 숫자들을 하나씩 붙여가면서 반복합니다. #include #include using namespace std; int main() { int N; ci.. 2020. 10. 13.
[알고리즘] 구간 합(prefix sum) 구간 합 알고리즘은 1차원배열에서 i ~ k번째 사이의 값들의 합을 구하는데 사용합니다. 단순히 for문을 사용하여 i~k사이의 값을 더해가면서 할 수도 있지만 이 경우 시간복잡도는 O(N)입니다. 하지만 구간 합 알고리즘의 경우 O(1)성능을 가집니다. 그리고 sum[]이라는 배열을 사용하는데, 이 배열은 현재 인덱스까지의 총 합을 저장하게 됩니다. j번째 바로 앞까지의 총합에 arr[j]번째 값을 더하면 j번째까지의 총합을 의미하기 때문에 이 값은 sum[j]에 저장하며 이는 sum[j] = sum[j-1] + arr[j]가 됩니다. 이후 5,8의 구간합을 구하기 위해서는 sum[8] - sum[5-1]로 한번에 구할 수 있습니다. #include using namespace std; int main.. 2020. 9. 25.
[알고리즘] 투포인터(two pointers) 투포인터는 전혀 알지 못했는데 카카오 코딩테스트 문제를 풀다가 우연히 알게 되었습니다. 처음 봤을 때 2개의 변수값을 조금씩 움직여가는것이 매개변수 탐색과 비슷하다고 생각했습니다. 투포인터는 1차원 배열에서 각각의 index를 가리키는 2개의 변수를 조작해가면서 문제를 해결하는 기법입니다. 투포인터를 백준문제를 보면서 설명하겠습니다. www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 문제는 1차원 배열에서 i번째에서 j번째까지의 합이.. 2020. 9. 25.
[알고리즘문제] 프로그래머스 - 경주로 건설 먼저 최소비용 문제이기 때문에 bfs를 사용했습니다. 처음 23점을 맞고, 코드를 분석하는데 상하좌우 탐색할 때 더 많은 비용을 사용함에도 먼저 탐색했기 때문에 그 경로를 사용하는 오류가 있었습니다. 그래서 이 부분을 해결하는 방법은 다른분의 코드를 참고하였는데, arr[][]에 해당 지점에서의 최소비용을 저장하는 것입니다. 그래서 [4,5]에 방문했을 때 현재 계산된 값이 arr[4][5]에 저장된(이전에 누군가가 방문했을 때의 값)보다 더 작은 경우 arr[4][5]의 값을 갱신해 줍니다. 그리고 그때의 x,y, 방향, sum값을 저장합니다. 기존에는 [0,0]에서 오른쪽과 아래로 이동했을 경우 따로 구했는데 각 지점의 최소비용을 계속 갱신해 주는 방법이라면 그냥 [0,0]에서 시작해도 됩니다. 그리.. 2020. 9. 25.
[알고리즘문제] 프로그래머스 - 키패드 누르기 문제의 핵심은 번호의 위치를 좌표로 어떻게 표혈한 것인가 ? 이다. 그 이후의 다른 부분은 그냥 문제를 읽고 if문으로 처리해주면 된다. y위치는 num/3을 해주고, x위치는 0번째 인덱스 부터 시작하기 때문에 num%3 -1을 해준다. 그리고 제일 오른쪽 번호(3,6,9)에서 처리를 해주어야 하는데 3,6,9에서는 num%3값이 0이 되기 때문에 임의로 2를 넣어주어여 하며, y위치 역시 y위치로 +1값이 되기 때문에 -1을 해주어야 한다. 그 외부분은 문제의 설명대로 구하면 된다. #include #include #include #include using namespace std; int distance(int x1, int y1, int x2, int y2) // 두 점의 거리 { return a.. 2020. 9. 22.

티스토리툴바