일지
-
JUNGOL...170일지 2021. 12. 22. 14:32
Intermediate_Coder/그래프탐색-DFS/치즈 문제 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모칸에 엑스친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어 가게 된다. 의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후 에 녹아 없어져서 와 같이 된다. 다시 한 시간 후에는 에서 ‘c’로 표시된 부분이 녹아 없어져서 과 같이 된다. ..
-
JUNGOL...169일지 2021. 12. 21. 21:33
Intermediate_Coder/그래프탐색-DFS/치즈 문제 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모칸에 엑스친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어 가게 된다. 의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후 에 녹아 없어져서 와 같이 된다. 다시 한 시간 후에는 에서 ‘c’로 표시된 부분이 녹아 없어져서 과 같이 된다. ..
-
JUNGOL...168일지 2021. 12. 20. 15:20
Intermediate_Coder/그래프탐색-DFS/치즈 문제 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모칸에 엑스친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어 가게 된다. 의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후 에 녹아 없어져서 와 같이 된다. 다시 한 시간 후에는 에서 ‘c’로 표시된 부분이 녹아 없어져서 과 같이 된다. ..
-
알고리즘...94일지 2021. 12. 20. 15:11
해시 테이블 충돌 해결 원소를 저장하려고 할 때 이미 다른 원소가 저장되어 있는 경우 충돌이 발생하게 된다. 이를 해결하는 방법으로 다음과 같은 방법들을 사용한다. 체이닝 같은 주소로 해싱되는 원소를 연결 리스트로 관리, 적재율이 1을 넘을 수 있음 검색, 추가, 삭제 시 해싱 후 연결 리스트를 통한 연산이 추가된다. 개방 주소 방법 어떻게든 주어진 해시 테이블 내에서 충돌을 관리, 적재율이 1을 넘을 수 없음 선형 조사 충돌이 일어난 바로 직후를 확인하여 처리를 진행하는 방식 특정 영역에 원소가 몰리는 경우 성능이 떨어진다. 이차원 조사 충돌 직후의 위치를 보는 대신 이차 함수에 따라 검색 폭을 넓히면서 확인하는 방식 여러 원소가 동일한 초기 해시 함숫값을 가지면 동일한 폭으로 검색하게 되므로 성능이 ..
-
알고리즘...93일지 2021. 12. 15. 08:20
해시 함수 해시 함수는 해시 테이블에서 키 값을 테이블의 인덱스로 만들어 주는 함수로 다음의 성질을 가진다. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. 계산이 간단해야 한다. 만약 데이터가 어느 한 인덱스에 몰려서 저장되게 된다면 충돌이 자주 발생하여 성능에 악영향을 미치기 때문에 입력된 데이터가 해시 테이블 전체에 골고루 나누어 저장되는 것이 상당히 중요하다. 해시 함수는 대표적으로 두 가지 방법이 존재한다. 나누기 방법 주어진 데이터를 해시 테이블의 크기로 나눈 나머지를 인덱스로 사용하는 방법 해시 테이블의 크기는 2의 멱수(2ⁿ)에 가깝지 않은 소수(prime number)를 택하는 것이 좋다. h(x) = x mod m 곱하기 방법 주어진 데이터를 0과 1 사이의 소수(decimal)..
-
유니티 화면 비율 고정 처리...24일지 2021. 12. 14. 17:30
최대화 처리 최대화 처리를 위해 먼저 화면에서 사용할 수 없는 영역을 제외한 최대 크기를 알 수 있어야 한다. 이를 위해 윈도우 창의 border와 작업 표시줄의 크기를 가져와 해당 크기를 모니터의 사이즈에서 빼도록 한다. // 윈도우 창 border 사이즈 RECT windowRect = new RECT(); RECT clientRect = new RECT(); GetWindowRect(m_hwnd, out windowRect); GetClientRect(m_hwnd, out clientRect); int windowBorderSizeX = (windowRect.Right - windowRect.Left) - (clientRect.Right - clientRect.Left); int windowBord..
-
JUNGOL...167일지 2021. 12. 14. 15:19
Intermediate_Coder/그래프탐색-DFS/영역 구하기 문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다. 와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다. M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그..
-
알고리즘...92일지 2021. 12. 14. 13:56
해시 테이블 개요 해시 테이블은 원소의 위치가 값에 의해 계산되어 결정되는 자료구조이다. 해시 테이블의 값을 정하는 건 해시 함수인데, 이 함수를 통해 각각의 원소의 자리를 상수 시간에 계산할 수 있다. 단, 테이블의 모든 영역에 값을 적절하게 분배하도록 만들지 못하는 경우 인덱싱이 필요하게 되어 성능이 떨어질 수 있게 된다. 따라서 해시 함수의 성능이 중요하게 된다. 이때 해시 테이블에 원소가 차 있는 비율을 적재율이라 하며, 테이블의 크기가 m 이고 테이블에 저장된 원소의 개수가 n이면 적재율은 n/m이 된다. 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘