치킨고양이짱아 공부일지

disjoint set union은 여러 원소들을 서로 겹치지 않는 그룹들로 나눠서 관리한다.이때 각 그룹을 부모 포인터 트리로 관리하며, root 원소의 parent는 자기 자신이다. 코드 class DSU: def __init__(self, n): # 처음에는 모든 원소의 parent를 자기 자신으로 설정하여, 모든 원소가 각각의 그룹을 형성하도록 세팅한다. # parent[i] = i면 i가 루트(대표) self.parent = list(range(n)) # size[root] = 해당 그룹 원소 개수 (union 할 때 작은 쪽을 큰 쪽에 붙이기) self.size = [1] * n def find(self, x):..

문제N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.입력첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]..

삼성에 합격한 현시점에서,삼성 SW 역량 테스트라 불리는 삼성 코딩테스트를 준비하는 분들께 도움이 될만한 글을 써보려고 한다!먼저 벼락치기를 했던 내 상황을 말하자면,코테 준비 경험) 석사 졸업을 앞둔 시점에서 취준 경험이 0이라 코딩테스트를 한번도 준비해본적이 없었다. (백준조차 가입이 안되어있었다;;)언어) 연구에서 사용한 python만 익숙한 상황이였어서 python으로 코테를 쳤다.준비기간) 1달 조금 안되었던것 같다. 대학원생이였기에 1달을 온전히 집중할 수도 없었다. 하지만 임박한 2주는 매일매일 5시간 이상 준비를 하였다. (카페에서 2~3시간 + 스터디카페에서 3~4시간)준비유형) 1번, 2번 중 simulation 유형인 1번 유형만 준비를 하였다. 벼락치기이다 보니 2번 유형까지 준비하..

사실 나는 아직까지 연구에서만 딥러닝을 사용하다보니 모델의 경량화 경험이 없다. 하지만 현업에서 사용하는 로봇, 자율자동차, 스마트폰과 같은 모바일 환경에서는 하드웨어 성능이 제한적인 상황이 많다. 이때문에 모델 경량화를 무조건 고려해야하니,,,,당장 쓸 일이 없더라도 개념을 알아보도록 하자 경량화 방법모델을 경량화 하는 방법은 크게 2가지로 나눌 수 있다. 1) 학습된 모델의 크기를 줄이는 방법2) 네트워크 구조 자체를 효율적으로 설계하는 방법-> 2)의 경우 모델의 구조를 단순화하거나 효율적으로 설계하여 파라미터 수와 연산량을 줄이는 방법으로 중요 아이디어는 불필요한 연산을 줄이고 중요한 피처만 효율적으로 학습할 수 있는 구조로 설계하여 모델의 크기와 계산 복잡도를 최소화하는 것이다. 여기서는 1) ..

최근에 면접을 보면서 모델 관련 지식들을 질문 받았었는데 완전 잘못 말했다....구조도 제대로 파악못하고 썼구나 싶어서 반성이 많이 된 경험이였다. 특히 Transformer의 경우 내가 굉장히 많이 써온 모델인데 구조를 파악 못하고 있다는게...ㅎ공부해보자...Transformer란?Transformer는 입력 시퀀스를 병렬로 처리하여 각 단어가 문맥 내 다른 단어들과의 관계를 학습하고, 이를 기반으로 출력을 생성하는 모델로, Attnetion 메커니즘을 활용해 복잡한 의존성을 효율적으로 캡처하여 다양한 시퀀스 작업에 활용되는 신경망 구조이다. Attention 메커니즘이란?Transformer를 제안한 논문의 이름이 "Attention is All you need"인 만큼 Attention에 대한 이..

2022 하반기 오전 1번 문제인 '싸움땅' 문제 풀이입니다. 1. 문제 링크https://www.codetree.ai/ko/frequent-problems/problems/battle-ground/description 삼성 코딩테스트 기출 문제 설명: 싸움땅 | 코드트리삼성전자 코딩테스트 기출 문제 싸움땅의 상세 설명입니다. 문제 요구사항을 정확히 파악하고 효율적인 알고리즘을 설계해보세요.www.codetree.ai 2. 한줄평bfs, dfs 없는 노가다 시뮬레이션 문제! 확실히 최근 기출이 훨씬 어려운것 같다..3년전만 해도 훨씬 낫네🥲 3. 코드N, M, K = map(int, input().split())dx = [-1, 0, 1, 0]dy = [0, 1, 0, -1]board = []for i..

2024 오후 하반기 1번 문제였던 '메두사와 전사들' 문제 풀이입니다. 1. 문제 링크https://www.codetree.ai/ko/frequent-problems/problems/medusa-and-warriors/description?introductionSetId=&bookmarkId= 2. 한줄평알고리즘이 어렵진 않지만 챙겨야할 디테일이 너무너무 많은 문제ㅠㅠ문제 조건에 전사가 0명 이상이라고 해서 0명일때는 전사위치 정보를 입력 안받도록 처리했었습니다..하지만 문제를 보면 '다음줄에 M명의 전사 좌표가 나온다'고 되어있으므로 전사가 0명일때도(M=0일때도) 빈 line을 입력받아야한다는것! 그래도 코테 전에 이런 디테일 때문에 틀려봤으니 실전에서는 같은 문제로 틀릴것 같진 않네요☺️ 3. 풀..

2023 상반기 오후 1번 문제인 '메이즈러너'의 Python 풀이입니다.  1. 문제 링크https://www.codetree.ai/ko/frequent-problems/problems/maze-runner/description 삼성 코딩테스트 기출 문제 설명: 메이즈 러너 | 코드트리삼성전자 코딩테스트 기출 문제 메이즈 러너의 상세 설명입니다. 문제 요구사항을 정확히 파악하고 효율적인 알고리즘을 설계해보세요.www.codetree.ai 2. 한줄평난이도 자체는 진짜 괜찮았는데 가장 작은 박스를 찾을 때 좀 깔쌈하게 해보려다가 엣지 케이스에 걸려서 1트에 틀린 문제..그냥 심플하게 구현하는게 젤 좋은것 같습니당😂 3. 풀이 N, M, K = map(int, input().split())board = ..

2024 상반기 오후 1번 문제로 나왔던 '마법의 숲 탐색' 문제의 python 풀이입니다. 1. 문제 링크https://www.codetree.ai/ko/frequent-problems/problems/magical-forest-exploration/description 삼성 코딩테스트 기출 문제 설명: 마법의 숲 탐색 | 코드트리삼성전자 코딩테스트 기출 문제 마법의 숲 탐색의 상세 설명입니다. 문제 요구사항을 정확히 파악하고 효율적인 알고리즘을 설계해보세요.www.codetree.ai 2. 한줄평시뮬레이션 문제의 경우 시간초과가 나는 경우가 거의 없었는데 시간 초과가 나서 도대체 뭐가 문제일까 고민했는데 치명적인 실수를 했더라구요..저의 경우 가장 깊은 행을 구할 때 dfs를 사용했는데 1->2->3..

2023 상반기 오전 1번 문제로 나왔던 '포탑 부수기' 문제의 python 풀이입니다. 1. 문제 링크https://www.codetree.ai/ko/frequent-problems/problems/destroy-the-turret/description 삼성 코딩테스트 기출 문제 설명: 포탑 부수기 | 코드트리삼성전자 코딩테스트 기출 문제 포탑 부수기의 상세 설명입니다. 문제 요구사항을 정확히 파악하고 효율적인 알고리즘을 설계해보세요.www.codetree.ai 2. 한줄평문제 자체는 어렵지 않았습니다. simulation + bfs로 최단 경로 찾는 문제입니다. 찾는거에서 영역 밖을 통해 이동할 수 있는게 좀 새롭긴 했지만 구현자체는 쉬웠습니다. 다만 역시나 그렇듯 조건이 너무 많아서 놓치기가 쉬워요..