본문 바로가기

분류 전체보기67

[코드트리/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.
[백준/C++] #16933 벽 부수고 이동하기 2, 3 (BFS) 문제https://www.acmicpc.net/problem/16933  구상백준 14442번 벽 부수고 이동하기 문제에다가 낮/밤 조건이 추가된 문제였다.  이런 문제는 깊이 우선 탐색(DFS)로 풀기가 어렵다. 이유는 다음과 같다. 최단 경로 보장: DFS는 특정 경로를 완전히 탐색한 후에야 다른 경로를 탐색하기 때문에, 탐색 초기에 찾은 경로가 반드시 최단 경로라고 보장할 수 없다. 반면 BFS(Breadth-First Search)는 모든 경로를 동시에 탐색하며, 처음으로 목표에 도달하는 경로가 최단 경로임을 보장한다.낮과 밤의 전환: 이 문제에서는 낮과 밤이 번갈아가면서 바뀌는 조건이 있다. BFS는 단계별로 탐색하기 때문에 이 조건을 자연스럽게 처리할 수 있는데, DFS에서는 상태를 추적하며 .. 2024. 7. 31.
[백준/C++] #1509 팰린드롬 분할 (DP) 문제https://www.acmicpc.net/problem/1509 구상확실히 골드 1이 느껴지는 문제였다. 그래도 차근차근 접근하니 옳은 풀이까지 도달할 수 있었다. 역시나 DP말고 특별한 접근 방식이 떠오르지 않아서 DP로 접근을 했다. 작은 길이의 팰린드롬 분할의 개수의 최솟값을 통해 더 큰(긴) 팰린드롬 분할의 개수의 최솟값을 구할 수 있었다.  그래서 처음에는 흔한 다른 DP문제들과 유사하게 접근을 했다. 흔한 DP 문제들은 DP배열의 특정 값이 답이 되는데, 그래서 나도 DP[i][j]가 str[i]~str[j]문자열에서 팰린드롬 분할의 개수의 최솟값이라고 잡고 문제를 접근했다. 그런데, 특정 크기의 문자열이 팰린드롬인지 확인하는 로직이 필요했다. 팰린드롬 여부를 어떻게 확인할까? 생각하다가.. 2024. 7. 24.

티스토리툴바