본문 바로가기

분류 전체보기83

백준 11444번 - 피보나치 수 6(C++) 문제백준, 골드, https://www.acmicpc.net/problem/11444풀이 날짜: 2025.3.17.풀이 시간:  총 3시간 51분사용 언어: C++문제 해설수학을 이용한 문제로, 공식을 모르면 풀 수 없다. 여기서는 도가뉴 항등식을 이용하여야 하며, 이를 활용하여 분할정복을 사용하여야 시간복잡도를 최적화할 수 있다.내가 구했던 식 중 하나가 바로 도가뉴 항등식의 특수해로, $a_{2n}$에 대한 식까지는 어떻게든 유도했는데 그다음으로 넘어가는 데에 실패하여 다른 글을 찾아보게 되었다.도가뉴 항등식은 피보나치 등식을 활용하여 변형한 것인데, 도가뉴 항등식은$$ a_{m+n}=a_{m-1}a_n+a_m a_{n+1} $$을 말한다(단, $a_n$은 피보나치 수열의 n번째 수).도가뉴 항등식과.. 2025. 3. 18.
ECS(Entity Component System)란 (DOD와 ECS, ECS와 메모리 구조) ECS가 무엇인지, 언어와 관련 없이 개념을 정리해놓고 싶어서 글을 정리해 봅니다.공부한 바를 제가 이해한 대로 정리한 것이므로, 틀린 점이 있다면 가감 없이 지적해 주시면 감사하겠습니다.해당 글은 특히 다음 영상을 주로 참고하였습니다(https://www.youtube.com/watch?v=7UphiG8UtTg). 1. DOD를 어떻게 적용해야 할까?ECS에 대해 이야기하려면, DOD, 즉 데이터 지향 설계에 대한 이야기를 한번 짚고 넘어가야 한다. ECS란 DOD를 어떻게 적용할지에 대한 고민에서부터 출발한 개념이기 때문이다.데이터 지향 설계(DOD; Data-Oriented Design)란 객체 지향 설계(OOD; Object Oriented Design)에서 발생할 수 있는 비효율적인 데이터 접근.. 2025. 3. 18.
백준 9328번 - 열쇠(C++) 풀이 정리 개요백준, 골드 1, https://www.acmicpc.net/problem/9328풀이 날짜: 2025.2.26.풀이 시간: 10:16~11:37(1시간 21분)알고리즘 분류: 구현, 그래프 탐색 문제사용 언어: C++문제 해설해당 문제는 단순히 그래프 탐색을 구현하는 문제이다.다만 여기서 조사 조건이 여러 개 걸리면서, 따져야 할 상황이 많아지고 있다.나는 탐색하는 방식을 다음과 같이 결정했다.모든 테두리에 대해 *이 아닌 곳은 통과가 가능하다.우선, 탐색할 수 있는 곳을 모두 탐색한다.탐색하는 과정에서 모든 문은 열 수 있으면 열고, 아니면 위치를 저장해 놓는다.탐색 과정에서 $가 나올 때마다 document 개수를 증가시킨다.탐색을 완료한 후, 열리지 않은 문을 조사한다.열리지 않는 문은 다시 .. 2025. 2. 26.
백준 2075번 - N번째 큰 수: 약간 더 빠른 코드 문제백준, 실버 3, https://www.acmicpc.net/problem/2075풀이 날짜: 2025.2.4.풀이 시간: 11:03~11:29(26분)알고리즘 분류: 정렬, 우선순위 큐사용 언어: C++문제 해설해당 문제는 상위 N번째 값을 구하는 문제이지만 두 가지 특징이 있다.메모리 제한이 걸려 있다. 12MB의 제한이 있다.모든 수는 자신의 한 칸 위의 수보다 더 크다.첫 번째 특징을 생각해보면, 해당 문제는 NN (1≤N≤1500)의 보드가 주어지고 각 값의 절댓값이 10억보다 낮으므로 자료를 모두 저장하는 데에 최소 1,5001,5004Byte=2,250,0004Byte = 9,000,000Byte, 즉 약 9MB의 메모리가 필요하다.이것만 해도 메모리 제한이 아슬아슬하므로, 만약 정렬을 .. 2025. 2. 4.
백준 1311번 - 할 일 정하기 1 문제백준, 골드 1, https://www.acmicpc.net/problem/1311풀이 날짜: 2025.1.29.풀이 시간: 15:17~16:30, 안 돼서 GPT 킴, 17:28에 DFS 방식으로 해결(총 2시간 11분)알고리즘 분류: 비트필드를 이용한 다이나믹 프로그래밍사용 언어: C++문제 해설해당 문제는 비트필드를 이용한 다이나믹 프로그래밍을 활용하는 문제이다.문제의 정답을 탐색할 때 탐욕법이나 다른 방법을 사용할 수 없으므로, 완전 탐색으로 모든 경우의 수를 측정해야 한다. 그런데 4명의 사람이 순차적으로 1-2-3-4번 일을 맡는 경우와 2-1-3-4번 일을 맡는 경우, 뒤의 3-4번 일의 비용을 계산할 땐 중복 계산이 발생하게 된다.이러한 중복 계산을 피하려면 상태를 저장하는 비트필드 기.. 2025. 1. 29.
백준 1562번 - 계단 수 풀이(C++) 1562번-계단 수문제백준, 골드 1, https://www.acmicpc.net/problem/1562풀이 날짜: 2025.1.28.풀이 시간: 약 2시간알고리즘 분류: 다이나믹 프로그래밍, 비트마스킹, 비트필드를 이용한 다이나믹 프로그래밍사용 언어: C++문제 해설‘1562 계단 수’는 비트필드를 이용한 다이나믹 프로그래밍을 필요로 하는 문제로, 해당 알고리즘을 활용하는 문제 중 가장 기초적인 문제이다.‘2098 외판원 순회’ 문제가 해결되지 않아 시도해보았는데, 난이도는 더 쉽지만 개념을 안다면 꽤 간단하게 해결할 수 있는 문제였다.비트필드를 이용한 다이나믹 프로그래밍은 ‘현재 상태’를 필요로 하는 문제에 유용하게 사용된다. 일반적인 다이나믹 프로그래밍에서는 정점 번호에 대한 정보나, 문자열의 인덱.. 2025. 1. 28.
백준 9252번 - LCS 2 문제백준, 골드4, https://www.acmicpc.net/problem/9252풀이 날짜: 2025.1.22., 2025.1.23풀이 시간2025.1.22: 11:34~12:31, 20:31~21:09(38분, 포기),2025.1.23: 11:19~12:58(1시간 47분)총 3시간 22분알고리즘 분류: 다이나믹 프로그래밍사용 언어: C++ 문제 해설해당 문제는 LCS(Longest Common Subsequence, 최장 길이 부분 수열) 알고리즘을 통해 문제를 풀어야 한다.LCS 알고리즘에 대해서는 전혀 몰랐는데, 이번 기회에 배우게 되어 정리해보았다.(LCS에 대한 설명은 그림으로 정말 잘 정리해주신 분이 계셔서 공유하고자 합니다. 본 글은 해당 글을 참고하여 작성하였습니다: https://v.. 2025. 1. 24.
백준 1018 체스판 다시 칠하기 문제백준, 실버4, 1018번: 체스판 다시 칠하기풀이 날짜: 2024.12.27풀이 시간: 11:37~12:07사용 언어: C++문제 해설해당 문제는 MxN 보드에서 조건을 만족하는 8x8 부분 보드를 찾는 문제이다.이때, 체크무늬 형태로 보드를 색칠해야 하는데, 체스판 보드의 색상은 잘못 칠해져 있을 수도 있으므로 체크무늬 형태로 칠해야 한다. 색은 하양, 검정 두 개가 있는데, 좌측 상단이 검정으로 시작할 수도 있고 하양으로 시작할 수도 있으므로 두 케이스를 모두 검사해야 한다.해당 문제를 브루트포스 방식으로 접근하는 사람들이 굉장히 많고, 해당 방식으로 해도 이 문제를 푸는 데에는 충분하다.다만 컴퓨터비전 시간에 적분 영상 알고리즘에 대해 듣게 되어서, 한번 적용해볼 수 있지 않을까 해서 적용해보.. 2024. 12. 27.
Unity - Terrain이 빛나는 문제(URP 모바일, Unity Engine 2022버전 이하)Unity - Terrain이 빛나는 문제(URP 모바일, Unity Engine 2022버전 이하) 유니티 엔진을 통해 3D 게임을 제작하던 와중에, Terrain으로 제작한 맵이 이상하게 빛이 나는 상황을 겪었다. 마치 금속 재질처럼 Specular reflection이 강하게 나타나는 상황이다.해당 문제는 유니티 커뮤니티에서 제기된 것으로, 유니티 측에서는 실제 엔진의 버그가 맞다고 답변하였다.Unity 2023 버전에서 해당 문제가 해결되었지만, 그 이하 버전인 2022, 2021 버전을 사용한다면 여전히 발생한다(2020은 있는지 알 수 없음).문제 상황일반적으로 Mesh를 배치하여 맵을 제작할 땐 각각에 Materials를 적용한다. 그래서 Specular 수치를 조절해서 빛의 반사가 어떻게 적용될지 조절한다.그런데 Terrain을 기반으로 맵을 적용했더니 위 사진처럼 Terrain이 금속 재.. 2024. 9. 3.

티스토리툴바