복's

https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 소수를 구하는 문제 + 그래프 or 백트래킹을 통한 완전탐색 문제라고 생각했다. 처음에는 에라토스테네스의 체를 사용해서 문제를 풀었었는데 주어진 메모리가 4MB로 적어서 메모리 초과가 났다. 범위가 주어지고 같은 수에 대해서 여러번 소수 판별을 해야할 것 같아서 에라토스테네스의 체가 적합할 것 같았는데 메로리 초과는 예상 밖이였다. [ 📌 풀이 ] 소수를 판별하는 방법 제곱근을 이용한 ..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제의 본질은 최단거리를 구하는 문제로 그래프 탐색중에서 BFS 알고리즘을 사용해서 푸는 문제다. [ 📌 풀이 ] 일반적인 BFS 로직에 조건 하나 추가 해주면 된다. 조건: 타겟으로 하는 층에 도달할 시 종료 [ 📌 주의 사항 ] 목표로 하는 층 보다 높아지거나 낮아 지는건 조건에서 필요 없다. 목표 층을 넘어가도 다시 내려가거나 올라가면 도달하는 최단거리가 있음 다음 층을 연산할 때 인덱스를 넘기면 안된..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 트리가 주어지고 그래프를 구성해서 그래프 탐색 알고리즘을 사용해서 푸는 문제이다. 목표는 리프 노드의 개수를 구하는 것이고, 고려 조건은 단 1개로 1개의 지워지는 노드가 있다는 점이다. [ 📌 풀이 ] 루트 노드를 기록해두었다. (탐색 시작 기준을 정하기 위해서) 지워지는 노드가 있기 때문에 임의의 노드를 기준으로 탐색을 하게되면 안된다. 지워지는 노드는 그래프에 넣지 않았다. 지워지는 노..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 물 수위에 따라서 수면에 잠기지 않은 붙어있는 영역을 구하는 문제로 간략하게 설명할 수 있을거 같다. 그래프 탐색 알고리즘을 사용해서 문제를 접근했다. [ 📌 고려사항 ] N은 2 이상 100 이하 -> 지역의 총 크기는 100 * 100이 최대 사이즈다. H(높이)는 1이상 100 이하 -> 최대 101번의 높이에 대해서 실행해야 한다. [ 📌 풀이 ] 1. 입력받은 영역들 중에가 가장 높은 지대의 높..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 30분 잡고 풀었는데, 시간내에 풀지 못했던 문제로 정글 코치님이 주신 힌트를 기반으로 기숙사로 돌아가서 다시 풀었다...... 사실 힌트 받고, 다시 푸니까 5분정도 걸렸던 것 같다. 힌트의 키워드는 '이분 탐색'인데 트럭이 적재 가능한 중량이 '1,000,000,000' 이라는걸 보고, 생각하지 못한것이 안타깝고, 이게 경험의 z차이인..