오구의코딩모험

https://www.acmicpc.net/problem/20444 문제 3줄 요약1. 직사각형의 색종이를 가위로 자른다.2. 한 변에 평행하게 자르며, 자를 땐 멈추지 않고 자른다.3. n번의 가위질로 k개의 색종이로 자를 수 있는지 확인하는 코드를 작성하자.  예시를 통해 살펴보자! 4번의 가위질로 9개의 색종이를 만든다면?  위의 그림과 같이가로 2번, 세로 2번을 자른다면 9개의 색종이로 자를 수 있다. 따라서가로로 몇 번을 자르는지,세로로 몇 번을 자르는지에 따라서몇 개의 색종이로 나뉘어 지는지 계산이 가능하다. 계산식을 작성해본다면가로로 자른 횟수 : x세로로 자른 횟수 : 전체 가위질 - x색종이 수 = ( x + 1 ) * ( n - x + 1 )로 표현할 수 있다.  그럼 이 식을 어떤 ..

https://www.acmicpc.net/problem/20207 문제 3줄 요약1. 달력에 1년치 일정을 표시하려고 한다.2. 연속된 일자에 일정이 1개 이상 있다면, 이를 연속되었다고 표현한다.3. 연속된 일정을 하나의 직사각형에 포함하여 달력에 코팅지를 붙일 때, 코팅지의 넓이는?  구현 문제라서 그런가문제부터 길고 뭔가 조건이 좀 많아서 복잡해보인다... 예시를 보면서 이해해보자.  위와 같이 2일 ~ 12일까지 일정은아래의 보라색 코팅지를 붙일 수 있다. 2일 ~ 9일까지는 연속된 일정이기에하나의 직사각형으로 묶고 있고 11일 ~ 12일은따로 직사각형 모형으로 코팅지를 붙였기에 총 면적이 28 (= 24+4) 이다. 일단 일정이 주어졌을 때,위와 같이 달력과 같은 형태로 구현해보도록 하겠다. ..

https://www.acmicpc.net/problem/21921 문제 3줄 요약1. 운영하고 있는 블로그의 방문 기록이 있다.2. 블로그의 X일 동안 가장 많이 들어온 방문자 수와 그 기간을 알고싶다.3. 최대 방문자 수가 0이라면 "SAD" 슬픔을 표현하자  이번 문제는이중 포인터를 활용한 문제이다. 방문자 수를X일 동안의 방문자 수를 일자 별로 구해주기 보다는1일차 부터 X일 동안 더해준 값을 기반으로2일차 ~ 2+X일의 값을 구해주려고 했다.  말로는 어려우니 예시와 그림을 통해 살펴보자.  총 5일 간의 방문 기록 중2일 간 방문자의 수가 최대였을 때, 방문자의 수와 기간은 어떻게 될까?     정답은 3일 ~ 4일차 까지의 방문자 수 합인 7과방문자 수가 7인 기간이 하루 뿐이므로 1이 되겠..

https://www.acmicpc.net/problem/11053 문제 1줄 요약1. 수열 A의 가장 긴 증가하는 부분 수열을 구해라.  위와 같이 가장 긴 증가하는 부분 수열을최장 증가 부분 수열, LIS(Longest Increasing Subsequence) 라고 한다. LIS는DP와 이분 탐색 두 가지 알고리즘을 활용하여 풀 수 있다고 한다. 이번 문제에서는DP를 활용하여 풀어보고다음 글에서는 가장 긴 증가하는 부분 수열 2를 이분 탐색으로 풀고자 한다.  가장 긴 증가하는 부분 수열은문자 그대로 부분 수열이면서, 값이 점점 증가하는 형태를 띄고 있는 수열이다. ex) 수열 A = {10, 20, 10, 30, 20, 50}의 LIS는?{10, 20, 30, 50} 이 최장 증가 부분 수열이 될..

https://www.acmicpc.net/problem/9251https://www.acmicpc.net/problem/1958 문제 3줄 요약1. Longest2. Common3. Subsequence  오늘은 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제를 풀어봤다. 최장 공통 수열은문제에도 설명되어있듯이 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것이다. ex) ACAYKP, CAPCAK → LCS : ACAK LCS와 다른게 LIS라는 것도 있던데..이건 다음에 풀어보자! 일단 LCS의 알고리즘 분류가DP로 되어있다. DP 테이블에 어떤 값을 저장해야하는지도무지 감이 잡히지 않아서바로 유튜브 서칭! https://www.youtub..

https://www.acmicpc.net/problem/15724 문제 3줄 요약1. 네모 왕국의 1X1의 단위 구역을 여러 개 묶으려고 한다.2. 4개의 숫자로 직사각형 범위를 알려준다.3. 해당 직사각형 범위의 내에 살고 있는 사람 수를 구해보자.  DP가 아닌 완전 탐색으로 처음 접근했더니시간 초과로 통과가 되지 않았다..! 직사각형의 시작 좌표와 (1,1)가고정이 아니기에 DP 테이블을 사용할 수 있나? 에 대한의문이 생겼다. 결국 코딩도사인 GPT에게DP를 어느 부분에 적용하면 좋을지 도움을 받았다.  DP 테이블에 (1, 1)부터 해당 좌표까지의직사각형 합을 저장(메모이제이션) 해두는 것이었다. 그 후(1, 1) 부터 (x1, y1) 의 인원 수와(1, 1) 부터 (x2, y2) 의 인원 수..

https://school.programmers.co.kr/learn/courses/30/lessons/388353  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  문제 3줄 요약1. 일주일동안 지각하지 않은 직원은 상준다.2. 본인의 희망 출근 시각 + 10분까지 출근해야만 한다.3. 상을 받는 직원은 몇 명일까요?  주말에 일정이 생겨서1차 예선은 참가하지 못하고 2차 예선만 참가하였다..! 그런데프로그래머스에 1차 예선 문제가 올라온 것을 보고하나씩 풀어봐야지 싶었다! 1번은코테에서 종종 봤던 시간 계산과 관련된 문제였다. 60분이 넘어가면 1시간을 추가해주는 연습을 할 수 있는 문제라생각하고 ..

https://www.acmicpc.net/problem/22942  문제 3줄 요약 1. 원의 중심이 x축 위에 존재하는 원들이 존재 한다.2. N개의 원들의 중심 x좌표와 반지름이 주어진다.3. 각 원들이 서로 교점이 생기는지 않는지 확인해봐라.  문제에서 N의 최대 값이 200,000 으로원을 하나 받을 때마다 그려진 원들을 전부 비교하기엔N(N-1)/2 정도의 연산이 필요하니대충 계산해봐도 200억 번의 연산이 필요하다.  따라서원이 그려질 때마다 겹치는지 겹치지 않는지범위 값을 담아두고 비교하는 형식이 필요할 것이다. 일단원의 중심 좌표, 반지름을 통해각 원의 최소 좌표와 최대 좌표를 vector에 담아 비교 연산에 필요한 값들을 세팅해주었다. int n;cin >> n;vector> circl..

멀티스레드와 동기화 기법: 게임 서버와 병렬 프로그래밍  멀티스레드는 게임 서버와 같은 고성능 프로그램에서 필수적인 요소입니다.이번 글에서는 Web Server와 Game Server의 차이, 멀티스레드와 동기화 문제, Atomic과 Mutex, Deadlock의 위험과 해결법을 중심으로 학습한 내용을 정리합니다.    1. Web Server와 Game Server의 차이 Web Server (HTTP Server)- Web Server는 질의/응답 형태로 작동합니다.  * ex) 테이크아웃 전문 식당처럼 요청에 대한 응답을 빠르게 처리.Game Server (TCP Server, Binary Server, Stateful Server)- Game Server는 실시간 상호작용(Interaction)을..

게임 개발에서 배우는 그림자 처리와 애니메이션 기법  게임 개발에서 그림자 처리, 지형 렌더링, 픽킹(Picking), 애니메이션(Skinning)은 사실적인 그래픽 구현과 상호작용을 위해 중요한 역할을 합니다.이번 글에서는 Shadow Mapping, Tessellation, Terrain, Picking, Animation(Skinning)과 관련된 개념과 원리를 정리해 보았습니다.      1. Shadow Mapping Shadow Mapping이란?- Shadow Mapping은 빛의 기준으로 앞에 물체가 있을 경우 그림자를 표현하는 기술입니다.   - 그림자는 빛의 방향과 물체 간의 관계를 계산하여 생성됩니다.   그림자 품질 개선   - 그림자가 깨지지 않으려면, 그림자를 그리는 화면 크기를..