poksul_log

관련 알고리즘 : 배열 문제 링크 : https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 문제 풀이 시간복잡도를 계산하는 능력이 타 친구들에 비해 현저하게(...) 떨어지는 것 같아 관련 문제를 들고왔다. 처음에는 내가 평소에 짜던 것처럼 이중for문을 돌며 모든 경우를 검사하게 했지만 역시나! 시간 초과 오류가 뜨게 되었다. 어찌보면 당연하다. 수의 범위가 (1 ≤ n ≤ 100000, 1 ..

관련 알고리즘 : DP 문제 링크 : https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 n자리 숫자 중 계단수(각 자릿수마다 있는 수의 차이가 1인 수)의 개수를 구하는 문제이다. '일의 자리 숫자가 무엇인가' 와 'n(자리수)'를 기준으로 dp 식을 세우면 문제를 해결할 수 있다. n=2인 경우를 예를 들어 생각해보자. 일의 자리 십의 자리 개수 0 1 1 1 2 1 2 1, 3 2 3 2, 4 2 4 3, 5 2 5 4, 6 2 6 5, 7 2 7 6, 8 2 8 7, 9 2 9 8 1 십의 자리 숫자가 일의 자리 숫자가 무엇이느냐에 따라 영향을..

📍 다이나믹 프로그래밍이란? 여러 개의 하위 문제를 먼저 푼 후, 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 컴퓨터는 연산 속도와 메모리 공간에 한계가 있기 때문에, 이를 최대한으로 활용해야 한다. 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수가 있는데, 이를 이용한 방법이 바로 DP이다. 📍 다이나믹 프로그래밍이 쓰이기 위한 조건 큰 문제가 작은 문제로 나눠질 수 있어야 한다. 작은 문제에서 구한 정답은 이를 포함하는 큰 문제에서도 동일하다. 다이나믹 프로그래밍은 1번 조건에 의해 분할 정복과도 비슷한 성질을 지니고 있지만, 분할 정복과 달리 문제들이 서로에게 영향을 끼친다. 📍 피보나치 수열 문제를 통해 알아보는 DP 다이나믹 프로그래밍의 대표적 예로 피보나치 수열 문제..

📍 스택(Stack) 삽입과 삭제가 한 쪽 끝에서만 이루어지는 데이터 구조 ▶ 특징은 다음과 같다. LIFO(Last In First Out) 방식으로 동작 top(가장 최근 스택에 삽입된 원소의 위치) => 포인터는 1개 ! 기본 기능 원소 추가(stack.push) - 시간복잡도 O(1) 원소 제거(stack.pop) - 시간복잡도 O(1) top 원소 확인 - 시간복잡도 O(1) 바로 원소에 접근 가능하기 때문에, 시간 복잡도는 모두 O(1)이다. ▶ 장점 top에만 접근이 가능하기 때문에, 데이터 확인, 추가, 제거가 빠르다. (시간복잡도 O(1) 소요) ▶ 단점 top 이외의 다른 위치에서의 데이터 확인/추가/제거가 불가능하기 때문에, 이를 탐색하려면 스택에 있는 모든 데이터를 top부터 하나씩..

§ Rigidbody란? Object에 물리 효과를 적용시키기 위해 사용하는 것. Gravity, Mass 등의 값을 조절하여 현실과 비슷한 물리효과를 낼 수 있다. 아래의 코드를 통해 Player에 부착된 Rigidbody Component를 가져올 수 있다. Transform Component와 달리, Rigidbody는 Object에 기본적으로 붙어있지 않으므로 GetComponent 등과 같은 메서드를 통해 가져와줘야 한다. private Rigidbody playerRb; // get rigidbody of the player void Start() { // player에 부착된 Rigidbody Component 가져오기 playerRb = GetComponent(); } Rigidbody의 ..

📍백트래킹이란 ? 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 즉, 해를 찾을 때 중간에 해가 아니어서 막힐 경우, 이전 단계로 되돌아가 해를 다시 찾는 기법 📍백트래킹의 쓰임 최적화 및 조합, 결정 문제를 풀 때 쓰인다. 주로 DFS(깊이 우선 탐색)와 묶여서 잘 쓰이는데, DFS는 가능한 모든 경로를 탐색한다. 따라서, n이 큰 경우 경우의 수를 줄여야 할 필요성이 있다. → 이 때 백트래킹을 사용하여 불필요하거나 불가능한 경로를 사전에 차단하는 것을 통해 경우의 수를 줄일 수 있다. 즉, 가지치기를 할 수 있다는 것 ! ▶ DFS와 쓰일 때 흐름은 다음과 같다. DFS로 모든 경우의 수를 탐색할 때, 조건문을 걸어 불가능한 경우를 정의하고, 해당 상황일 때 탐색을 중지 이후 ..

지난 몇개월간 학교 공부와 더불어 서버에 대해 공부해보겠다고 이것저것 해보느라 유니티에 소홀해졌다. 그래서 잊어버린 지식들을 채우고, 기초를 더 탄탄히 하고자 unity에 대해 다시 배우고 정리하려고 한다. 기초는 탄탄해서 나쁠 것이 없으니! Unity learn의 Unity Essentials와 Junior Programmer 코스를 참고하였다. Learn game development w/ Unity | Courses & tutorials in game design, VR, AR, & Real-time 3D | Unity Learn Free tutorials, courses, and guided pathways for mastering real-time 3D development skills to m..

관련 알고리즘 : BFS 문제 링크 : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 풀이 지도를 모두 돌며 연결되어 있는 단지의 개수와 단지 당 집 개수를 찾아야 하므로 bfs(너비우선탐색)을 이용한다. 플로우는 다음과 같다. 더보기 string을 통해 입력 처리 map 완전탐색을 통해 아직 방문하지 않고 & 좌표값이 1인 경우(집이 있는 경우) 부터 bfs 시작 상하좌우 탐색 이후, 지도 밖의 범위일 경우 반복문 탈출 이미 방문한 곳일..

📍 new? C에서의 malloc과 같은 역할로, heap 상에서 메모리를 할당함 ▶ 사용법 Type* pointer = new Type; // Type 크기의 공간을 할당, pointer에 주소값 전달 // example int* p = new int; // int 크기의 공간 할당, 주소값 p에 넣기 /* 배열에 사용 시 */ Type* pointer = new Type[size]; // example int* list = new int[10]; 📍 delete? C에서의 free와 같은 역할로, heap 상에서 메모리를 해제함 이 때, delete로 해제할 수 있는 공간은 사용자가 new를 통해 할당한 공간만 해당한다. *p = 10; delete p; // p에 할당된 공간 해제 /* 배열 해제 ..

관련 알고리즘 : BFS 문제 링크 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 풀이 며칠이 지나면 토마토들이 익는 지 "최소 일수"를 구해야 하므로 bfs를 사용한다. 토마토들의 상태(-1, 0, 1)을 배열에 저장 익은 토마토들을 큐에 넣기 익은 토마토들 상하좌우 토마토들 방문 여부 확인 안 익은 토마토가 존재 시, day++ 하여 날짜를 증가시키고 익었다 처리 해당 토마토를 큐에 넣기 위의 과정 반복 C++ 코..