본문 바로가기

분류 전체보기101

[백준/C++] #1005 ACM Craft (DP) 문제https://www.acmicpc.net/problem/1005구상문제를 보다가 문득 그래프는 없겠지..?라는 생각이 들었다. 만약 그래프에 사이클이 존재한다면, 사이클을 이루는 건물들 간에는 순환 의존 관계가 형성된다. 즉, 건물 A를 짓기 위해 건물 B가 필요하고, 건물 B를 짓기 위해 건물 C가 필요하며, 건물 C를 짓기 위해 다시 건물 A가 필요하게 되는 모순이 발생한다. 이러한 상황에서는 어떤 건물도 완성될 수 없으므로 건물 건설이 불가능하다. 문제에서 모든 건물이 완성될 수 있다고 나와있었기에 그래프에 사이클이 포함되지 않는다는 것을 확증할 수 있었다.!! 구한 이전 건물의 건설 소요시간을 구했다면 다음 건물의 소요시간을 구하는 로직만 짜면 되기에 dp 알고리즘을 사용하는 문제라는 생각이.. 2024. 8. 9.
[백준/C++] #1913 달팽이 (Simulation) 문제https://www.acmicpc.net/problem/1913  구상나는 보통 문제에 명시되어있는 조건들을 이용해서 풀이를 찾는 편이다. 입력 조건이 홀수인 자연수 N이라고 나와있었고, 도출해야 하는 최종 배열의 (0,0) 값이 항상 홀수인 자연수의 제곱이 되는 수였다. 그래서 아래 사진과 같이 한겹 한겹 따로 계산해주는 방식을 택했다. 그리고, 상단, 우측, 하단, 좌측 순서로 몇개씩 배열에 넣으면 될까 그림을 그려봤는데, 2 -> 4 -> 6 -> .. 이런식으로 규칙이 명확해서 더 쉽고 빠르게 풀어낼 수 있었다.  시뮬레이션에서는 다시금 첫값, 끝값이 중요하다는 것을 깨달았다.   풀이 + 코드#include#include#include#include#include#define MAX 101.. 2024. 8. 5.
[코드트리/C++] 배열 회전 (Simulation) 문제https://www.codetree.ai/training-field/search/problems/array-rotation/description?page=1&pageSize=20&name=%EB%B0%B0%EC%97%B4+%ED%9A%8C%EC%A0%84 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 사각형 자체를 돌리는게 아니라서, 껍질별로 각각 돌려야 한다.수학적으로 무슨 규칙이 있지 않을까해서 상신오빠랑 머리 좀 싸매다가 결국 그냥 가장 처음 생각해낸 방법으로 코드를 짰다 ㅋㅋㅋㅋ 역씌 원초적인게 답이다. 일단 시간복잡도 안에 들어올 수 있다.. 2024. 8. 5.
[백준/C++] #10026 적록색약 (BFS/DFS - Flood Fill) 문제https://www.acmicpc.net/problem/10026 구상기본적 flood fill문제였다. 몇개의 섬이 있는지 판단하면 되는, 정말 간단한 문제였다. 그냥 문제 읽자마자 flood fill이라는 걸 알 수 있었다. 그리고, 아래를 보면 알 수 있다 싶이 bfs로 풀게 되면 메모리 초과가 났다. dfs로 풀어야 한정된 메모리 안에서 풀렸다.  코드 + 풀이1) 메모리초과 난 BFS  풀이BFS가 너비 우선 탐색으로 인해 많은 노드를 메모리(큐)에 저장해야 해서  노드의 연결이 많을 경우, 저장되는 노드 수가 많아져, 메모리 초과의 가능성이 있다. #include#include#include#define MAX 101#define endl "\n"using namespace std;/*1.. 2024. 7. 31.

티스토리툴바