알고리즘/백준 BAEK JOON
-
19237.어른상어알고리즘/백준 BAEK JOON 2020. 9. 17. 00:12
이번에 풀어볼 문제 역시 따끈따끈한 최신문제 백준의 19237 어른상어이다. 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 예전에 아기상어라는 문제를 푼적이 있는데 백준에 어른상어와 청소년상어가 추가되었다. 그 중 어른상어의 문제이다. 난이도는 복잡한 구현만 해결하면 충분히 풀 수 있는 거같다. 시간이 좀 오래걸렸지만 큰 틀(완성직전)까지는 나쁘지않은 시간이 걸린거 같다. 다만 예외처리까지 설계하는 힘은 아직 부족한거 같다. 이 문제는 왜인지 모르게 로봇청소기 문제..
-
19236.청소년상어알고리즘/백준 BAEK JOON 2020. 9. 9. 03:09
이번에 풀어볼 문제는 백준 19236 청소년 상어이다. 괜찮은 문제인거 같다. 문제를 어느정도 풀면서 갑자기 느낀 것인데 정답률은 난이도가 아닌거 같다. 정답률이 높은 문제들은 구현만 제대로하면 다른 예외처리 같은 것이나 함정(히든케이스)같은 것이 없는 문제라 정답률이 높고 낮은 문제들은 함정(히든케이스)가 있어서 낮은거 같다는 생각이 들었다. 여튼 이 문제는 시뮬레이션 문제이다. 이 문제에서 얻어갈 수 있는 것은 idx에 대한 내용을 굳이 구조체의 변수로 가져가는 것이 아니라 배열의 순번으로 가져는 방법도 괜찮은 방법이다. 그리고 함수 로직의 순번에 대한 내용이다. 당연한 이야기지만 여러 함수들을 구현해야할 때는 큰 함수와 작은 함수에 대한 구별이 필요하고 큰 함수 속에 작은 함수가 들어가도록 구현하는..
-
19238.스타트 택시알고리즘/백준 BAEK JOON 2020. 8. 30. 18:20
이번에 풀어볼 문제는 백준의 19238번 스타트 택시이다. 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 제일 최근에 나온 문제로 역시나 시뮬레이션이다. 난이도는 19%라고 나와있지만 함정만 잘피하면 풀 수 있다. 이 문제를 다 구현하고 시간을 어느정도 잡아먹었는데.. 그 이유는.. 문제의 조건 하나를 읽어놓고 구현하다가 까먹었다. ( "최단 거리가 같은 경우 가로, 세로 좌표가 작은게 우선이다" 라는 조건이다.. ) 항상 조건들은 잘 적어 놓고 빼먹지 말자!!! 함정은..
-
1197.최소 스패닝 트리알고리즘/백준 BAEK JOON 2020. 8. 20. 22:40
이번에 풀어볼 문제는 백준 1197번 최소 스패닝 트리이다. 이전 포스팅에서 스패닝 트리를 공부했다면 이번에는 간선에 가중치가 들어있어서 최소한의 간선으로 연결하되, 가중치도 최소로 진행하는 최소 스패닝 트리 문제를 풀어보았다. 직접 구현하는 방법에 대해서 공부할 수 있는 문제이다. 이해가 안간다면 코드를 보거나 그림을 그려서 공부해보자 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 � www.acmicpc.net 이 문제는 크루스칼 알고리즘과 프림 알고리즘으로 풀이할 수 있다. 크루스칼 ..
-
9372.상근이의 여행알고리즘/백준 BAEK JOON 2020. 8. 20. 00:36
이번에 풀어볼 문제는 백준 9372의 상근이의 여행이라는 문제이다. 9372번: 상근이의 여행 문제 상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다. 하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려� www.acmicpc.net Spanning Tree에 대해서 공부할 수 있는 문제이며 최소 신장 트리(MInimum Spanning Tree)까지 공부할 수 있었다. Spanning Tree : 방향이 없는 그래프에서 모든 정점들을 연결함과 동시에 순환경로가 없는 형태를 의미한다. => 만약 이와 같은 상황에서 가중치가 포함되고 최소 가중치만을 이용하여 연결하는 경우를 최소 신장 트리라고 한다. 이 문제를 잘 읽어보면 일단 최소 ..
-
1932.정수 삼각형알고리즘/백준 BAEK JOON 2020. 8. 19. 21:37
이번에 풀어볼 문제는 백준 1932번 정수 삼각형이다. 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 정말 쉬워보이지만 자신의 인접한 대각선의 숫자로만 합을 구해야한다는 점을 해결해야만 이 문제를 풀 수 있다. 이 문제를 푸는 방법은 대표적으로 DP 동적계획법을 사용하는 것이다. * 제일 꼭대기의 값 부터 값을 누적해서 진행하되 겹치는 부분은 둘 중 큰 값으로 누적하면 된다 * 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..
-
1074.Z알고리즘/백준 BAEK JOON 2020. 8. 15. 17:36
이번에 풀어볼 문제는 백준의 Z이다. 재귀함수를 이용하여 탐색을 하는 문제인데 재귀함수를 잘 활용해야 풀 수 있는 문제이다. 개인적으로 쉬워보이지만 난이도가 상당하다고 느꼈다. 이런 문제를 잘풀어야하는데.. 흑흑.. 1074번: Z 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 �� www.acmicpc.net 이 문제를 푸는 포인트는 두 가지이다. 1. 재귀함수에서 조건을 통해 굳이 확인할 필요없는 탐색 순번은 그 카운트 만큼 더해주고 넘어가기 2. 4등분해서 탐색하되 크기에 상관없이 이러한 탐색이 진행되도로 재귀함수를 짤 수 있어야 한다 ..
-
15686.치킨배달알고리즘/백준 BAEK JOON 2020. 8. 11. 00:43
이번에는 오랜만에 백준의 문제를 풀어보았다. 15686 치킨배달이라는 문제이고 재귀함수 조합에 대한 공부를 하기 좋은 문제 같다. 난이도나 유형은 이전의 요리사와 상당히 비슷한 문제같이 느껴진다. 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 다행이 풀어내는데 성공했고 풀어내면서 느낀점은 설계의 중요성이다. 재귀함수를 두 번 진행했기에 설계를 잘못하면 너무 복잡해지므로 꼭 설계가 끝나기전까지는 코딩하지말자!! 이 문제의 풀이 과정은 다음과 같다. 1. 치킨의 좌표들 중에 M개를 선택하는 ..