Ustory

코테 스터디가 좋은 연이 되어서, 99클럽 알고리즘 스터디 1기에도 참여하게 되었습니다 😀클럽장님과 Q&A 시간 후에 자극받아서 문제를 조금 풀어보았어요.  💡 문제https://www.acmicpc.net/problem/1158 요세푸스 순열을 출력하는 문제였습니다. 생각보다 간단하지만 무서운 문제 n명의 사람이 원형으로 앉아 있을 때, 매번 k 번째 사람을 제거해 나가면서 최후의 생존자를 찾는 문제입니다. 이 문제에서는 제거되는 사람들의 순서를 출력하는 것이 목표 !  요세푸스 순열이란?n과 k가 자연수이고, k 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.출처 : 위키백과  요구사항 n : 사람의 수k : 제거될 사람의 순서(갱신되는 새로운 원에서 k번째 사람..

Problemhttps://leetcode.com/problems/minimum-suffix-flips/ Sol초기 '0'으로만 이루어진 문자열 s의 특정 인덱스 i부터 n-1까지 flip 했을때 '0'과 '1'로 이루어진 target과 똑같아 질 수 있는 최소 flip 수를 세는 문제 해결 방법👀 처음에 단순하게 생각해서 그냥 반복문으로 풀었습니다. for문이 안팎으로 돌다보니까 최소의 수를 보장할 수도 없고 시간복잡도가 O(n^2)이 나오는 효율 바닥 코드가 나왔습니다. 혹시나 했는데 역시나 test case는 통과했지만 submit을 하니까 Time Limit Exceeded가 떴습니다. T.T  class Solution: def minFlips(self, target: str) -> in..

꾸준히 잘 써오다가 28일차 TIL을 놓쳐버렸어요 🥲 다시 킵고잉~Problemhttps://leetcode.com/problems/iterator-for-combination/Sol오늘 문제는 주어진 문자로부터 주어진 길이의 1. 모든 조합을 생성하고 2. 다음 조합을 반환하고 3. 다음 조합이 있는지 확인하는 class CombinationIterator를 완성하는 문제였습니다. combinations을 사용한 코드와 그렇지 않은 코드 2가지로 해결해보았습니다.itertoools.combination 사용👀 Python 내장 모듈인 ‘itertools’의 combinations를 활용하면, 입력된 반복 가능한(iterable) 객체에서 주어진 길이의 조합을 생성할 수 있습니다.  from iter..

Problemhttps://leetcode.com/problems/find-the-original-array-of-prefix-xor/ SolXOR 연산으로 prefix된 배열을 통해서 원래의 배열을 찾는 문제: 주어진 배열의 각 요소는 해당 위치까지의 누적 XOR 값을 나타내며, 원래 배열을 복원하는 것이 목적! 해결 방법👀 복원해야하는 origin_arr를 초기화하고, 반복문을 통해 prefix 배열의 값에 차례대로 접근하여 원래 값을 찾아내는 방식으로 해결하였습니다.1. origin_arr : 찾으려고 하는 원래 배열- 첫번째 원소는 pref의 첫 번째 원소와 동일2. 반복문- origin_arr[i] = pref[i] 번째와 pref[i-1] 번째 값을 XOR 한 값(^)3. 정답 시간복잡도 O..

Problemhttps://leetcode.com/problems/subrectangle-queries/ Sol✅ 주어진 메소드 2개를 이용하여 class SubrectangleQueries를 완성하는 문제class SubrectangleQueries 는 'rows x cols' 크기의 직사각형을 정수 matrix 로 받아들입니다. method 1) updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)왼쪽 위 좌표가 (row1, col1)이고 오른쪽 아래 좌표가 (row2, col2)인 부분 직사각형의 모든 값을 newValue로 업데이트지정된 부분 직사각형의 범위 내의 모든 값을 새로운 값으로 변경한다는 의미method 2) ..

다시 풀어보기Problem코딩테스트 연습 > 그래프 > 순위 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  Sol주어진 경기 결과를 분석했을 때 순위를 명확하게 알 수 있는 선수의 수를 세는 문제 해결 방법👀 처음에는 어차피 방향([a,b]는 a가 b에게 이김)이 정해져있으니 wins 만 카운트 하면될 것 같아서 시작했는데 너무 복잡해지고 자꾸 틀려서 GPT의 도움을 받았습니다. +) 스터디 시간 코치님께서는 플로이드-워셜 알고리즘을 사용하셨다고 합니다. 초기에 떠올린 아이디어로 하려면 요걸 활용하면 좋을 것 같습니다. 한번도 공부를 안해봐서 다음에 해봐..

Problem그래프 / 가장 먼 노드 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  Sol1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제 🌱 참고그래프를 적절한 형태의 자료구조로 변환하고 생각해야 했던 문제였습니다.  아래 도서를 참고하여 공부했습니다. Do it! 알고리즘 코딩 테스트: 파이썬 편“코딩 테스트를 제대로 준비하려면 어떤 문제를 얼마나 풀어야 할까?” 곧 코딩 테스트를 앞둔 취업 또는 이직 준비생이라면 누구나 이런 고민을 할 것이다. 《Do it! 알고리즘 코딩 테스트 - 파이썬 편》에 그 답이 있다. 네이버, 카카오, 삼성, 라..

Problemhttps://leetcode.com/problems/capacity-to-ship-packages-within-d-days/ Solclass Solution: def shipWithinDays(self, weights: List[int], days: int) -> int: # days 동안 다른 항구로 짐 옮기기 # i 번째 짐 무게 == weights[i] 주어진 순서대로 실어야함 # 각 날마다 컨베이어 벨트 위의 짐들을 배로 옮길거야 # weight

Problem 입국심사 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  Sol각 심사관이 심사하는 데 걸리는 시간 times가 주어졌을 때 n명의 사람이 입국 심사를 받는데 걸리는 최소 시간을 구하는 문제 Binary Search  데이터가 정렬된 배열에서 검색 범위를 반으로 줄여가며 target을 탐색하는 알고리즘 입력 데이터가 정렬된 상태에서 적용Binary Search의 >>핵심 아이디어분할 정복(Divide and Conquer)탐색 범위를 절반으로 분할 ➡️ 탐색 속도 빠름보통 처음 Low과 전체 검색 공간 High의 중간 인덱스 "mid"를 찾아 ..

Problemhttps://leetcode.com/problems/count-square-submatrices-with-all-ones/ Sol0과 1로 만들어진 행렬(matrix)에서 1로 만들 수 있는 정사각형의 최대 개수를 구하는 문제  Dynamic Programming 어떤 단계에 있을 때 처음부터 여기에 어떻게 왔는지는 중요하지 않다. 바로 그 앞 단계에서 어떻게 여기까지 왔는지 중요 특정 위치 i에 도착해있다고 가정하고  '그럼 그 전에도 어떻게든 알아서 잘 왔겠지' 라는 생각으로 푸는 형식입니다.  🌱 참고Dynamic Programming lectures Dynamic Programming lectures www.youtube.com문제는 짧은데 생각해내는데 너무 오래걸려서 냅다 유튜브..