본문 바로가기

전체 글83

[알고리즘] Segment Tree, lazy propagation 1. Segment Tree 세그먼트 트리는 트리 형태의 데이터를 활용해 어떤 구간에 대한 정보를 활용하는 데 사용한다. 아직 블로그 글에서 세그먼트 트리를 다루지 않았지만, 후에 다루어 볼 것이고, 먼저 lazy propagtion의 적용을 이 글에서 다루어 볼 것이다. 2. lazy propagation 느린 전파라고도 말하지만, 게으른 전파가 알고리즘을 더 잘 나타낼 수 있는 단어라고 생각하여 게으른 전파라 부르겠다. 세그먼트 트리에서 게으른 전파는 값을 갱신할 때 특정 값이 아니라 범위의 값을 변경할 때 사용한다. 세그먼트 트리는 log(N)으로 가능하지만, 범위의 값을 경신하기 위해 Nlog(N)의 연산이 필요하게 된다. 그래서 갱신을 트리의 모든 값에 항상 적용하는 게 아니라 필요할 때만 하는.. 2022. 8. 19.
나의 디지털 노트 일지 나는 공부한 것을 문서로 정리하는 것을 좋아한다. 하지만 그 방법과 과정을 잘 이해하지 못하여 때로는 많이 더 난잡해졌다는 느낌도 들었고, 그 방법과 형식을 여러 차례 바꾸어가기도 했다. 이 글에서는 내가 기록을 해온 과정과 각각의 특징 그리고 지금 나는 어떻게 하고 있는지를 다루어 볼 것이다. 공책 필기 아마 대부분이 그러하듯, 나도 공부 내용을 종이 공책에 순서대로 정리하는 방법으로 시작했다. 하지만 정리를 잘하는 편은 아니었다. 가끔 그림이나 간단한 표 등을 활용하여 구성했지만, 내가 정리한 것을 한눈에 잘 이해하지 못한다는 느낌을 받았고, 그래서 해결 방법에 대한 고민을 했다. 이 고민의 결과는 두 가지 방법으로 해결할 수 있었다. 컬러 코딩 속지 추가, 교체가 가능한 공책(바인더) 사용 1. 컬.. 2022. 8. 14.
[SSAFY] SSAFY를 마무리하며 SSAFY의 마지막 SSAFY가 끝난지는 한 달이 넘었다. 프로젝트들도 정리하고, 여러 고민을 하며 시간이 꾀나 많이 지났다. 아마 마지막 SSAFY관련 게시글이 될 것 같다. 나름 길었던 1년의 과정을 정리하고, 혹시나 나중에 읽게 된다면 누구에든 도움이 되었으면 좋겠다. SSAFY의 시작 SSAFY를 신청할 때 개발자라는 큰 방향성은 고민했지만, 상세한 방식과 과정은 고민해보지 못했다. 다양한 것을 준비하고 공부한다고 생각했지만, 지금와서 돌아보면 방향성이 틀렸다고 생각되는 부분도 많고, 섬세한 고민을 하지 않으려 했던 것 같다. 단순하게 접근해서 해결할 수 있을 것이라 생각했다. 지금은 전공자는 코딩테스트로 시험 보는 것으로 알고 있는데, 당시에는 적성 검사와 같은 방식의 시험을 모두를 대상으로 실.. 2022. 8. 5.
[Python] 백준 13258 복권 + 은행 문제 링크 : https://www.acmicpc.net/problem/13258 13258번: 복권 + 은행 두 번째 예제의 경우에 첫 주가 지난 후 1/3의 확률로 (3, 2, 2)가, 1/3의 확률로 (2, 3, 2)가, 1/3의 확률로 (2, 2, 3)이 된다. 둘째 주에 (3, 2, 2)는 기댓값이 3.4286이 되고, (2, 3, 2)와 (2, 2, 3)은 기댓값이 2.2857 www.acmicpc.net 1. 접근 방법 간단한 확률 계산 문제로, 기댓값을 알아내면 된다 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/13000/13200/13258.py GitHub - mintropy/PS:.. 2022. 8. 5.
[Python] 백준 1655 가운데를 말해요 문제 링크 : https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 1. 접근 방법 입력을 계속 받으며 중간 값을 출력해야 한다. 이때, 입력이 많기 때문에 계속 정렬을 한다거나 탐색을 하면 시간 초과가 날 것으로 보인다. 그렇기 때문에 중간값을 기준으로 큰 값, 작은 값을 각각 보관하고, 입출력이 많을 수 있기 때문에 heap 구조를 활용했다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintr.. 2022. 8. 3.
[Python] 백준 20149 선분교차 3 문제 링크 :https://www.acmicpc.net/problem/20149 1. 접근 방법 문제는 매우 간단하다. 두 선분의 끝점이 주어지고, 교차하는지 판별하면 된다. 하지만 이를 해결하기 위한 과정은 간단하지 않을 수 있다. 우선, 선분 교차와 관련하여 CCW 지식이 있으면 더욱 편하게 해결할 수 있다. 그리고 선분 위치에 따라 분류하여 작업을 진행해야 한다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/20000/20100/20149.py GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다. 다양한 알고리즘 문제 풀이 저장소입니다. Contribute to min.. 2022. 7. 25.
[SSAFY] 자율 프로젝트 회고 0. 프로젝트 소개 및 정리 GAN을 활용한 인공지능 생성 시스템, GanDa(간다) - 인공지능 훈련용 이미지를 GAN을 활용하여 생성 - GAN훈련 모델 업로드/다운로드 지원 - 다양한 GAN모델을 활용한 사용 기술 스택 - 프론트 : TypeScript, React - 백 : FastAPI - 인공지능 : PyTorch - 기타 : Gitlab CI/CD + Docker, Nginx 기여도 - 백엔드 80% - 대부분은 백엔드 코드를 작성 - FastAPI 기반 웹 서버 관련 학습 및 팀원과 공유 - 인공지능 20 % - PyTorch를 활용한 인공지능 모델 활용 방법 학습 및 공유 - StyleGAN을 활용한 이미지 생성 모델 훈련 및 활용 1. 프로젝트를 시작하며 프로젝트 주제 선정 이번 프로젝.. 2022. 7. 18.
[Python] 백준 5527 일루미네이션 문제 링크 : https://www.acmicpc.net/problem/5547 5547번: 일루미네이션 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 www.acmicpc.net 1. 접근 방법 BFS를 응용하여 해결하는 문제인데, 육각형 구조에 따라 추가적인 고려사항이 생긴 문제이다. 그리고 단순히 육각형의 수를 원하는 것이 아니라 모서리의 길이를 구하여야 하므로, 조금 더 복잡한 과정이 필요할 수 있다. 처음에는 각 선분을 좌표로 하여 탐색하려 했다. 어차피 한붓그리기 형태가 될 것이므로 구현은 조금 복잡할 수 있지만, 쉽게.. 2022. 7. 11.
디자인패턴 - 전략 패턴 전략 패턴을 사용하지 않고, Duck이라는 슈퍼클래스를 기반으로 각 구현체는 슈퍼클래스를 상속받아서 생성한다고 하자. 그러면 구현이 단순해 보일 수 있지만, 다른 문제를 마주치게 될 것이다. 예를 들어 오리가 나는 행동을 추가하고 싶다면, Duck클래스에 그러한 행동을 추가하는 방식으로 해결할 것이다. 여기서 큰 문제를 마주하게 된다. 특정 행동을 하거나 하지 않는 오리가 있다면, 또는 특정 행동을 다르게 하는 오리가 있다면 어떻게 해야되는가? 이는 다음과 같은 경우를 의미한다. 어떤 오리가 수영하지 않는다고 하면, Duck클래스를 상속받은 후, 메서드 오버라이드 하여 특정 행동을 제한해야 하는가? 오리마다 우는 방식이나 소리가 다르다고 하면, 우는 행동은 모두 재작성해야 하는가? 이 방식은 상속받는 클.. 2022. 6. 28.

티스토리툴바