Devlog

1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 정수 N이 있습니다. i자리의 수와 j자리의 수를 서로 바꾸는 작업을 K번 반복해서 나온 수들 중, 최댓값을 구하는 문제 입니다. DP+브루트포스로 푸는 방법과 그래프 탐색으로 푸는 방법이 존재하지만 원리는 거기서 거기이기 때문에 여기선 그래프 탐색으로 푸는 방법만 설명하려고 합니다. 사실 N, K범위가 작기 때문에 브루트포스 방법이 먹혔던 거지 범위가 길었으면 시간초과가 발생 할 풀이 입니다. 그리디가 아닌 이유 얼핏 보면 그리디 처럼 보입니다. 수들을 이리저리 움직여서 수의 최대값을 맞추는 문제 처럼 보이기 때문입니다. K번 이..

1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 문제 위와 같은 3x3 퍼즐이 있을 때 퍼즐위의 숫자들을 오름차순으로 정렬할 수 있는 최소 이동 횟수를 구하는 문제입니다. 얼핏보면 그냥 평범한 백트래킹 혹은 BFS 문제처럼 보이지만 메모리 제한(25MB)이 걸려있습니다. 접근 일반적인 BFS를 이용한 최소 비용을 구하는 문제들은 visited라는 방분 여부 변수를 사용하는데 이 문제에서는 visitied 배열을 9차원 배열로 선언해야 합니다. (ex: visited[0][1][2][3][4][5][6][7][8]) 그렇게 되면 visited의 크기는 9^9가 되는데 이 길이는 억단위를 ..

백준에서 타일 채우기 문제는 2개가 있습니다. 하나는 너비의 범위가 30 이하이고 다른 하나는 10^18입니다. 1탄 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net N = 2일 때 깔 수 있는 타일의 형태를 그려봅시다. 접근 N = 2일 때 둘 수 있는 경우의 수는 총 3입니다. 이렇게 보면 N = 1일 때의 경우의 수는 존재하지 않습니다. 그 이유는 높이가 3이기 때문에 타일의 각도가 [세로, 가로], [가로, 세로] 혹은 [가로, 가로, 가로]입니다. N = 1에 맞게 깔려면 오직 세로 형태만 깔아야 하는데 이때 세로의 길이는 항상 짝수가 되므로 높이가 3인 경우에는 N = 1 형태로 깔 수가 없습니다. 결국 깔린..

내가 당분간은 그래프, 트리 문제 안푼다고 했는데... 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 문제 민식이 부터 말단 사원 까지 소식을 전파했을 때 걸리는 시간의 최솟값을 구하는 문제 입니다. 착각하기 쉬운 점이 있다면 현재 위치의 간부가 부하들에게 전파를 할 때, 모든 부하들을 전파한 다음, 부하들이 전파를 하는 것이 아니라 간부가 부하 1명에게 전파를 하면 그 다음에는 간부가 아직 전파하지 않은 부하에게 전파함과 동시에 이미 전파된 부하도 같이 자신의 부하에게 전파를 하게 됩니다. 아래의 그림 처럼요...

개요 프로젝트, 특히 서버 관련 프로젝트를 진행하다 보면 가끔씩 이런 생각을 하게 됩니다. 이거 만약에 트래픽이 순식간에 몇천 몇만 개 들어오면 어떡하지? 똑같은 객체를 순식간에 몇 만개를 만들면 메모리가 터지지 않을까? 아니 애초에 굳이 내용물까지 똑같은 객체를 여러 개 만들 필요가 있을까? 예를 들어 외부 리소스와 상호작용하는 모듈 같은 경우(데이터베이스, 캐시 등...) 특정 리소스만 바라보기 때문에, 특수한 경우가 아닌 이상 내용물까지 동일한 객체만 생성하게 됩니다. 이 똑같은 객체 혹은 인스턴스를 생성했다가 삭제했다가, 수천수만 번을 반복하는 것은 시간 뿐만 아니라 메모리 낭비입니다. 이러한 낭비를 막으려면 한번 할당 하고 그 이후에는 할당된 인스턴스만 따로 불러오면 생성/삭제를 더이상 반복할 ..

파이썬 백엔드에 대한 상당히 주관적인 견해를 쓴 거라 반박 시, 님 말이 다 맞음 개발자 취업을 위한 파이썬 백엔드 프레임워크 코스(원티드 프리온보딩 2차 백엔드 코스)를 참여해서 5주 정도 진행했다. 프레임워크는 주로 DJango를 사용했는데, 이전 부터 DJango 사용법은 알고 있었지만, 그래봐야 야매로 배운 탓에 어떻게 코딩을 해야 하는 지 몰랐고, 이 프로그램을 통해 간신히 제대로 배울 수 있었다. 그리고 여러 기술 스택에 대한 내 개인적인 생각이 일부 바뀌게 되었는데, 이 중 가장 크게 바뀐 분야갸 파이썬 백엔드 프레임워크의 선택이다. 파이썬 백엔드 프레임워크의 선택 자금까지 나는 MicroService는 Flask/FastAPI가, 조금 규모가 큰 분야부터는 DJango를 쓰는게 디폴트(물론..