맴매레인저 맴매레인저

분류 전체보기

• Sorting

  CS/알고리즘 2023. 11. 14. 20:01

  Insertion Sort 1. Strategy 원소를 적절한 순서대로 삽입(Insertion)한다. 첫 번째 원소는 정렬된 상태이다. 임의의 원소 $x$를 꺼낸다. $x$의 적절한 위치를 찾을 때까지 계속해서 배열의 원소들과 비교한다. 이를 모든 원소가 정렬될 때까지 반복한다. 2. Algorithm 입력값 : 정렬되지 않은 배열 출력값 : 오름차순으로 정렬된 배열 void insertionSort(Element[] E, int n) int xIndex; for (xIndex = 1; xIndex < n; xIndex++) Element current = E[xIndex]; Key x = current.key; int xLoc = shiftVacRec(E, xIndex, x); E[xLoc] = cur..

  Read More
• 백준 2178 : 미로 탐색

  백준 2023. 11. 14. 17:20

  1. 문제 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 2. 문제 접근 2차원 배열이 주어지고 목표 지점까지의 경로 탐색 -> 그래프 탐색 최단거리, 즉 그래프 탐색 시 가장 짧은 Depth를 반환해야 함 -> BFS 3. 문제 해결 중복 노드 탐색을 방지하기 위해 노드 방문 여부를 저장하는 2차원 배열 초기화 시작 노드부터 상, 하, 좌, 우로 이동하며 방문 가능한 노드일 경우 BFS에 노드 추가 목표 지점에 도달했을 경우 해당 노드의 Depth를 반환 4. 코드 #..

  Read More
• Analyzing Algorithms and Problem Principles

  CS/알고리즘 2023. 11. 13. 21:51

  Problem Solving Using Computers 컴퓨터를 사용해서 문제를 풀기 위해선 다음과 같은 절차를 거친다. Problem (문제) Strategy (문제 해결 전략) Algorithm (알고리즘) : Input (입력값), Output (결과값), Step (단계) Analysis (알고리즘 분석) : Correctness (정확도), 시간 및 공간 복잡도, Optimality (최적성) Implementation (알고리즘 구현) Verification (알고리즘 검증) Proof 어떠한 논리를 증명하기 위한 방법으로 주로 4가지를 사용한다. Counter Example (반례) Contraposition (대우) Contradiction (귀류법) Mathematical Inducti..

  Read More
• 백준 1946 : 신입 사원

  백준 2023. 11. 12. 18:00

  1. 문제 : https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 2. 문제 접근 완전 탐색 : 모든 지원자의 점수를 비교해야하므로 $N^2$ -> 최악의 경우 십만 * 십만 = 백억번의 계산이 필요. -> Time Limit 정렬 : 두 점수 중 하나를 오름차순으로 정렬한다면 나머지 하나의 최솟값을 갱신해가며 합격한 지원자인지 판단하면 된다. 정렬의 경우 $N\log{N}$이고 이후 배열을 탐색하는 로직은 $N$, 즉, 전체..

  Read More
• 백준 1932 : 정수 삼각형

  백준 2023. 11. 11. 16:54

  1. 문제 : https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 2. 문제 접근 완전 탐색 : 주어진 이진 트리의 높이는 $N$이고 경로의 수는 $2^{N-1}$이므로 모든 노드를 탐색한다면 시간이든 메모리든 모두 초과하게 된다. DP : 방문했던 노드를 중복해서 계속 방문하기 때문에 중복되는 Sub-Tree가 너무 많아 불필요한 계산을 하게 된다. 방문한 노드까지의 값을 미리 저장한다면 중복 방문하는 노드를 제거하여 많은 메모리와 시간을 아낄 수 있다. (메모이제이션) 3. 문제 해결 모든 노드까지의 경로 합을 0으..

  Read More
• 백준 1931 : 회의실 배정

  백준 2023. 11. 10. 20:04

  1. 문제 : https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 2. 문제 접근 회의실을 사용할 수 있는 회의의 최대 갯수를 찾아야 한다. -> 스케줄링 문제 회의실은 한 개만 존재한다 -> 여러 개의 스케줄 중 하나의 스케줄만 활성화가 된다. -> Activity Selection Problem 3. 문제 해결 회의가 끝나는 시간을 기준으로 정렬한다. 끝나는 시간이 같다면 시작하는 시간을 기준으로 정렬한다. 정렬된 배열을 순차적으로 탐색하면서 시간이 겹치지 않는 회의를 찾아낸다. 4. 코드 #include #include #include using namesp..

  Read More
• 백준 1890 : 점프

  백준 2023. 11. 10. 01:03

  1. 문제 : https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 2. 문제 접근 BFS : 다음 노드로 탐색할 수 있는 방법은 두 가지이므로 자식이 2개인 트리를 탐색하는 문제로 치환할 수 있다. 다만, 최악의 경우(모든 노드의 값이 1일 때), 시작점에서 사각형의 절반만 탐색하더라도 $2^N$개의 노드를 탐색해야 한다. 4 bytes * $2^N$만 해도 메모리가 터지는 것을 확인할 수 있다. DP : BFS에서 메모리 초과가 나는 ..

  Read More
• UGUI의 성능 최적화

  게임 클라이언트 개발/Unity 2023. 11. 8. 00:38

  여러 장르의 게임이 존재하지만, 공통적으로 제일 중요한 부분은 사용자 인터페이스를 맡고 있는 UI일 것이다. UI는 사용자와 어떻게 상호작용을 할 것인지도 중요하지만 Unity Profiler에선 UI만 따로 볼 수 있을 정도로 UI의 성능 또한 매우 중요하다. Unity의 UI를 담당하는 Component 중 가장 기본적인 Component는 Canvas일 것이다. Canvas의 Render Mode는 Screen Space - Overlay, Screen Space - Camera, World Space 총 세 가지가 존재하며 이번 UGUI의 성능 최적화는 Screen Space - Overlay 최적화를 목표로 한다. 출처 : Unity Korea 공식 유튜브 https://www.youtube.c..

  Read More