복's

https://www.acmicpc.net/problem/1074 [ 📌 서론 ]내가 마지막에 이 문제를 풀었을 때에는 Silver 1 이었는데, 언제 난이도가 상승 했다.나는 재귀 함수를 설계하는게 이상하게 어려워서 이런 문제로 연습을 많이 했는데, 오랜만에 다시 풀게 되었다.예전 풀이와 비교 했을 때 더 좋아진걸 보니 성장 했음을 느낀다. 풀이 과정에서도 과거에 이 문제를 처음 접했을 때는 문제 접근이 막막 했었고, 풀이도 정말 오래 걸렸는데, 성장이 눈에 보이지는 않지만 아주 조오오오금 늘었다고 생각해도 되지 않을까..?[ 📌 풀이 ]다양한 풀이가 있겠지만 주어진 2차원 배열이 2^N * 2^N 사이즈를 유지하기 때문에 복잡한 계산 없이 풀 수 있고, 4 개의 사분면으로 나눠서 문제를 풀이 할 ..

[ 📌 서론 ]https://www.acmicpc.net/problem/2458 단순히 그래프 탐색으로도 풀이가 가능할 거라고 생각은 되는게 그래프를 정, 역방향 2개 만들고 탐색 알고리즘을 수행한다면정방향: 나보다 큰 키의 학생들역방향: 나보다 작은 키의 학생들선택한 노드 기준으로 다른 학생들과의 키 상하 관계를 알 수 있을 것 같지만, 나는 플로이드-워셜 알고리즘을 연습하기 위해서 알고리즘 분류에서 선택해서 문제를 골랐다.[ 📌 풀이 ]중요한점은 어떤 노드가 크고 작은지가 중요한게 아니라 도달할 수 있는지가 중점이다. 그래프 구성하기도달 여부만 알면 되기 때문에 true/false 로 노드 관계를 구성했다.정방향은 입력으로 주어진다.플로이드-워셜 알고리즘 수행경유 노드를 거쳐서 도달할 수 있는지 ..

https://www.acmicpc.net/problem/11404 플로이드 워셜(Floyd-Warshall) 알고리즘을 접하게 되어서 알고리즘 연습을 위해서 찾다가 풀게된 문제다.예전에 문제를 풀 때 다익스트라 알고리즘은 음의 가중치를 해결하지 못해서 고민하다가 이름만 기억하고 있다가 기회가 왔을 때 문제로 연습 하였다.[ 📌 풀이 ]그래프 구성다른 그래프 문제와 동일하게 출발 -> 도착 (비용) 을 기록할 수 있도록 구성한다.플로이드 워셜 알고리즘경유 노드를 정해서 다른 노드가 지나가면서 INF 로 설정했던 경로를 도달할 수 있는지 체크한다.V^3 시간 복잡도를 갖고, V^2 의 공간 복잡도를 갖기 때문에 불필요한 연산을 최소로 한다.출력 값 포맷 맞춰주기문제에서 요구하는 출력 방식을 맞춰준다. (..

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

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제에 대한 설명은 쉽게 이해 되었지만 접근 방식에 대해서는 쉽게 와닿지 않아서 고민 많이 했다. 고민 하는 것 보다 직접 쓰는게 시간이 덜 아까워서 쓰다 보니까 어느정도 감은 잡았다. 질문 게시판을 통해서 힌트도 접했고 풀이 방법이 한개가 아니였다는걸 알게 되었다. [ 📌 풀이 ] N의 값이 올라갈 때 마다 2가지의 고려 사항이 생긴다 1의 자리가 0 뒤에 0 혹은 1이 와도 이친수가..

https://www.acmicpc.net/problem/14606 14606번: 피자 (Small)예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작www.acmicpc.net 주어진 수를 나누다보면 중복된 값이 나오기 때문에 DP 알고리즘 문제이다.N의 범위가 작게 주어져서 DP 풀이가 아니여도 풀 수 있을거 같은데, 풀이는 메모이제이션으로 풀었다.[ 📌 풀이 ]주어진 수를 최대한 쪼갠다높이가 1 인 피자탑으로 분리 시키라는 조건이 있었기 때문에 1까지 쪼갠다DP 테이블이 비어있다면 값을 채우고, 값이 채워져 있다면 해당 값을 return 한다.DP 테이블을..

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/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 3번째 풀면서 익숙해져버린 문제 스택을 이용하는 문제인데 다른 알고리즘 보다도 스택을 사용하는 어려운 문제가 진짜 힘든 것 같다. [ 📌 풀이 ] 일반적인 완전 탐색의 방법으로는 시간 초과가 나는 문제다. 탑의 개수가 500,000 개까지 들어오는데 매번 탑이 스택에 들어올 때 마다 확인 하는건 좋지 않다. 주어진 규칙을 활용하자. ◀︎⎯⎯⎯⎯⎯⎯🀆 🀆 🀆◀︎⎯⎯⎯︎⎯⎯⎯⎯⎯⎯⎯🀆 ◀⎯🀆 🀆 🀆..