알고리즘

리트코드 문제 147linked list로 주어지는 리스트를 삽입정렬을 이용해서 정렬하는 문제

리트코드 179숫자 리스트의 조합 중 가장 큰 수 문자열로 출력하기 functools의 cmp_to_key함수를 직접 정의해서 비교기준 넣어주기 비교기준 : (a + b) vs (b + a)예외) 모두 0 일 경우 "00.."이 출력되기 때문에 "0"되도록 걸러주기 -

리트코드 973번원점으로부터 k번째까지 가까운 점들 출력1초가 좀 넘는다..(거리^2 , index) 튜플을 값으로 넣어준다k번 pop하면서 index값에 해당되는 점들을 리스트에 넣어준다정렬함수를 쓴것과 별 차이가 없다..

리트코드 75번빨간색(0), 흰색(1), 파란색(2) 순서대로 제자리 정렬기본아이디어 : 0과 2를 양끝에 모으자0, 2가 발견될때마다 양끝에 옮기기 inplace정렬 -> swap을 사용해야겠다양끝에 두개의 pointer로 위치를 저장해야겠다head, tail이 양끝

리트코드 704번정렬된 배열에서 target값을 찾아 index값을 반환python에서 재귀 호출 최대수는 1000번으로 재귀알고리즘을 짤 때 넘지 않도록 참고 binary search 알고리즘에서 중간값(Mid)를 구하는 식을 (left + right) // 2로 작

리트코드 33번특정 pivot을 기준으로 정렬된 곳에서 target 이진탐색하기먼저 pivot값을 찾고 그 값을 기준으로 index값을 교정pivot값은 뒤에서 부터 음수 인덱스로 search(선형탐색...)그 뒤로 target을 일밙거으로 이진탐색을 진행하지만 값을

리트코드 240번왼쪽에서 오른쪽 위에서 아래로 오름차순 정렬된 행렬에서 target값 찾기이진탐색을 2차원으로 진행하면되겠다고 생각matrixm이라고 한다면 first_m, first_n, last_m, last_n으로 확장하고 각각 mid를 계산 -> mid_m, m

리트코드 349번두 숫자리스트의 교집합을 반환하는 문제 딕셔너리로 저장후 비교 전부비교이진탐색으로 찾기

리트코드 167번정렬된 리스트에서 두 수의 합이 target값이 되는 인덱스 반환하기투포인터 양끝에서 시작해서 합이 작으면 왼쪽 포인터 이동, 값이 크면 오른쪽 포인터 이동k가 하나의 답이라고 하면 k보다 오른쪽에서 나머지 값 탐색하기k보다 작은곳은 이미 탐색했기 때문

리트코드 191번주어진 수의 1비트의 개수계산int값으로 들어와있기 때문에 2진수로 변환을 한 뒤 문자열을 다루듯이 풀이오랜만에 Count를 사용해봤는데 빈도수 세는 풀이에서 쓸만하다. 반환값이 딕셔너리기 때문에 key값으로 조회하면 된다!

리트코드 136번리스트중 1개만 있는 숫자 찾기 defaultdict을 사용해서 딕셔너리로 개수를 저장해놓자!그닥 참신하지는 않지만 그래도 확실하고 쉬운 방법같으면 0 다르면 1을 반환하는 XOR연산의 특징을 이용 : 이때 0 xor a처럼 0과 연산을 하면 다를때 a

리트코드 461번두 정수의 비트중 다른 비트수 세기xor연산 후에 정수형 리스트로 바꿔서 sum해버리기 -> 1의 개수만큼 나옴xor연산을 하면 다른 곳만 1이나오고 나머지는 0으로 바뀜문자열 다루기

리트코드 393번UTF-8검증하기 먼저 문제에 1-4byte의 문자만 온다고 되어있습니다....ㅠㅠ열심히 테케 틀려가며 최대한 작성해본 코드인데.. 사실 더이상 어디가 틀린지도 모르겠어서ㅠㅠ 일단 UTF라는 개념이 설명만으로 살짝 부족했다고 느꼈습니다. 예를 들면 N

리트코드 239번k길이의 윈도우를 처음부터 끝까지 옮겨가며 최대값들 뽑아내기사실 문제는 매우 쉽다. 읽자마자 아래와 같은 풀이는 모두들 생각할 것입니다. 하지만... 당연히도 시간초과가 났고 이 문제의 nums의 범위가 매우 크기때문에 또한 k도 매우 커질 수 있어서

리트코드 424번k번 변경을 통해 만들 수 있는 연속적으로 같은 가장 긴 문자열의 길이먼저 처음에는 투포인터로 첫번째 문자 기준 가장 긴 윈도우 길이를 찾기그 뒤에 max 윈도우 길이만큼 슬라이딩 윈도우빈도수를 계산해서 만약 max를 넘을 수 있다면 오른쪽으로 포인터

리트코드 76번문자열 s중 문자열 t를 포함하는 최소 부분문자열 출력 가장 왼쪽을 기준으로 오른쪽 옮겨가며 처음으로 substring 찾기왼쪽 땡겨주며 substring이 유지되는 최소길이 찾기 substring깨지면 슬라이딩 윈도우하면서 더 짧은 substring찾기

리트코드 406번사람의 키와 자기보다 같거나 큰 사람의 수가 차례로 주어질 때 모두 만족하는 줄세우기 자신의 키이상인 사람이 앞에 몇명이나 있는지 매번 계산해주는 것은 매우 비효율..\-> 항상 자신보다 크거나 같도록 하자 : 내림차순 정렬을 해서 제일 큰 사람부터 넣

리트코드 122번주식 차트를 보고 낼 수 있는 가장 많은 수익 구하기매번 상승세일 때 마다 이익을 봐야 최대 이익을 구할 수 있다!price와 min_price를 매번 비교하면서 더 작은 값을 극소값으로 저장price - min_price인 profit의 최대를 찾기위

리트코드 621번같은 일을 n간격안에는 다시 하지 않는 최단 스케줄 시간을 구하라 우선순위 큐 : 남은 일의 길이와 일 키워드를 담은 튜플 (4,"A")Counter : 최초에 일의 횟수를 세기위해Queue : n번안에 다시 반복되지 않게 하기 위해 대기시키는 곳 그리

리트코드 621번같은 일을 n간격안에는 다시 하지 않는 최단 스케줄 시간을 구하라 우선순위 큐 : 남은 일의 길이와 일 키워드를 담은 튜플 (4,"A")Counter : 최초에 일의 횟수를 세기위해Queue : n번안에 다시 반복되지 않게 하기 위해 대기시키는 곳 그리

리트코드 134번주요소를 연료고갈 없이 한바퀴 돌 수 있는 시작점 구하기 시작점, 끝점 초기화 : 맨끝차액계산 -> gas1,2,3,4,5 - cost3,4,5,1,2 = -2,-2,-2,3,3 차액이 음수가 되지 않도록 순서를 정해주면 된다!차액들의 sum이 음수면

리트코드 455번최대한 많은 아이들에게 쿠키 나눠주기 쿠키의 크기와 아이들이 만족하는 최소쿠키크기를 정렬앞에서부터 아이가 원하는 쿠키 매치해주기

리트코드 169번과반수 이상을 차지하는 숫자 찾기이 문제의 포인트는 O(N)의 시간복잡도와 O(1)의 공간복잡도로 푸는 것이다. 따라서 브루트 포스로는 구할 수 없습니다. counter는 O(N)의 복잡도를 갖습니다. 하지만 most_common이 sort함수를 내부적

리트코드 241번괄호를 이용해 가능한 모든 계산결과 출력예시 : "3+2\*1-5+4" 라는 식이 주어진다면 연산기호를 기준으로 앞뒤를 나눠준다 -> 숫자가 두자리일 수 도 있어서 항상 숫자가 짝수인덱스인것은 아님 (divide)처음에는 (3)+(2\*1-5+4) 이렇

백준 10872번팩토리얼재귀를 이용해서 탑다운으로 풀었습니다 팩토리얼은 재귀로 풀기에는 1~n까지 누적곱을 구하는 것이기 때문에 반복문으로도 쉽게 구할 수 있습니다. 재귀보다 코드 짜기가 쉽고 불필요한 함수호출이 없어서 좋은 것같아요 🤗

백준 10870번 피보나치 수 풀이1. 재귀 + 메모이제이션 탑다운 풀이2. 재귀 + 메모이제이션 바텀업

백준 11729번

백준 2798번주어준 수를 넘지 않는 가장 가까운 3개의 숫자합 구하기 이문제는 N의 범위가 100이하기 때문에 브루트포스로 구현해도 충분히 되는 문제이때 3중 for문을 돌려도 되지만 for문으로 하나의 숫자를 투포인터로 나머지 두개의 숫자를 결정하는 방식으로 풀었습

백준 2231번주어진 숫자를 분해합으로 갖는 가장 작은 수 구하기 여기서 분해합은 자기자신과 각 자리 수의 합을 말합니다 ex) 23 -> 23+2+3N의 범위가 10^6이하기 때문에 1~N까지 전체 탐색제일 작은 수를 찾아야하기때문에 1부터 돌리면서 발견하는 즉시 r

백준 7568번덩치 순으로 순위 출력하기덩치는 몸무게와 키가 모두 커야 큰 것i는 처음부터 끝까지 돌며 j는 i보다 앞에 위치한 사람들을 포인트i,j를 비교 : 덩치가 더 큰 사람이 있다면 bigger에 기록(문자열비교와 int비교는 다르다!!!)마지막 answer리시

백준 2447번재귀를 이용한 별찍기 크게 첫줄, 둘째줄, 세번째로 3구역으로 나눠서 생각하기반복되는 규칙 : N/3의 패턴으로 둘러싸기 -> 첫줄은 3번반복, 두번째 줄은 중간만 비우기, 세번째 줄은 3번반복따라서 L에 매번 패턴을 한줄씩 넣어서 넘긴다. ex) 9

백준 2751번nlogn의 성능으로 수 정렬하기 결과는 통과! 하지만 2292ms로 생각보다 속도가 안나왔습니다.. 다른 성능좋은 제출들을 살펴보니 PyPy3로 선택을 했더라구요.. 그래서 언어를 PyPy3로 똑같은 코드를 돌려보니 1428ms로 거의 절반정도 줄었습

백준 2750번주어진 수 오름차순으로 정렬하기정렬함수가 이미 최적화가 되어있어서 좋은 성능을 내는 것 같습니다 입력이 들어올때마다 삽입정렬을 해봤습니다역시 정렬함수보다 성능이 안좋네요🥲이 문제는 정렬할 수의 개수가 적어서 여러 정렬알고리즘이 가능할 것같아요

백준 1018번주어진 패턴에서 최소의 수정으로 8x8크기의 체스판을 만들기 isChess함수 : 이 함수는 체스판 시작점(x,y)를 넣어주면 체스판으로 만드는데 변경해야할 최소 블럭수를 반환해줍니다. change0은 흰검흰검...체스판을 만들기위해 change1은 검흰

백준 1426번특정규칙을 따르는 N번째 수 구하기 666을 포함하는 N번째 숫자를 찾아야합니다. 자리수에따라 여러 규칙들이 적용되는것같아 저는 그냥 1부터 숫자를 하나씩 증가하면서 666이 포함되어있는 숫자들을 셌습니다..ㅎ 그래서 N번째가 나오면 반환했습니다. 코드도

백준 18870번자기보다 작은 수의 개수정렬을 한 뒤에 딕셔너리에 각 숫자보다 작은 숫자의 개수를 기록 set으로 중복을 제거하고 각 수의 인덱스를 딕셔너리에 저장 리스트 내포와 딕셔너리 내포로 코드줄이기

백준 10814번나이순으로 정렬해서 이름과 나이 둘다 출력반복적으로 입력을 받아야함 -> sys.stdin.readline()이차원 배열일 때 python의 정렬함수는 default로 첫번째 인자비교후 같으면 두번째인자 순으로 정렬해준다따라서 지금은 나이로만 정렬을 해

백준 1181번두가지 기준으로 단어정렬하기 기준1순위: 길이가 짧은 순2순위: 사전순 단 같은 단어 여러개는 한번만 출력 2순위로 먼저 정렬 후 1순위로 정렬readline()은 개행까지 같이 받기때문에 정렬해서 출력시 개행도 계속 같이 따라다니게 됩니다 -> rstr

백준 11066번: 연속되게 파일을 합치는 가장 적은 비용구하기일단 처음 이 문제를 접했을 때 연속되게 합쳐야된다는 것을 잊고.. 문제 그대로 합쳐진 것과 원본들 사이에 두개를 골라서 합쳐가야하는 상황으로 해석했다;; 그래서 우선순위큐사용해서 두개씩 pop하면 되는거네

주어진 규칙에 따라 이진트리를 만들고 순회하며 출력하는 문제 문제는 아래와 같이 흩뿌려진 노드를 이진트리로 만들고 전위순회, 후위순회를 하면서 풀면 되는 문제입니다.이 문제를 보고 먼저 두단계로 나뉜다고 생각했습니다. 1\. 이진트리를 잇고2\. 이진트리를 출력한다그

규칙에 맞게 표편집을 한 뒤에 처음과 비교하여 결과를 출력하는 문제규칙은 아래와 같습니다."U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다."D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다."C" : 현재 선택된 행을 삭제한 후, 바로 아

실제 번호는 이게 아니었던 것 같은데(프로그래머스 기준 왜 어려운것들이 앞에있지??? 만약 저 순서대로 나왔다면 좀 많이 당황했을 듯..) 쉬운문제들부터 리뷰하도록 하겠습니다.이때는 3차에 거쳐서 코딩테스트를 봤더라고요. 그래서 그런지 1차는 전체적으로 지금에 비하면

오늘은 2018 1차에 이어 3차 코테를 풀어봤습니다. 전체적으로 문자열조작 문제들이 많았고 난이도도 요즘 카카오 코테에 비하면 낮은 편이었습니다 이 문제는 음악의 일부분(m)을 듣고 어떤 음악인지 맞추는 것입니다. 정렬조건은 재생길이가 긴 음악이고 만약 같다면 mus

일단 인턴십 문제기 때문에 공채보다는 쉬운감이 있었고 2022 인턴십과 비슷하거나 조금 더 어려웠다. 굉장히 쉬운 문제였고 python뿐만 아니라 다른 언어도 replace가 제공이 된다면 쉽게 풀수 있었던 문제였다. 카카오는 이렇게 첫번째 문제에 문자열 조작이나 노가

카카오 2020 공채 코딩테스트를 5시간동안 풀어보았다. 한번씩 풀어봤던 문제들이라 처음푸는 것처럼은 아니지만 그래도 여전히 부족한 점들이 있었다.굉장히 특이한 문제이다. 일단 문제에서 시키는대로 하면되는데 결국 재귀함수를 작성하게된다. 여기서 문제는 어떻게 "균형잡힌

오늘은 카카오 2021 공채 코테를 풀어보았다. 5시간동안 총 5솔을 했고 6번은 1시간 40분이나 도전했는데 비트마스킹으로 풀어도 5개가 시간초과가 났다. 아마 뭔가 로직을 더 다듬었어야 했을 것같은데 그 부분도 살펴봐야겠다.이 문제는 순서대로 잘 풀면 되는 문제였다

가장 최근 기출인 2022 공채 코테를 풀어봤습니다. 2022는 난이도가 다른 해에 비해 평이하게 나왔다는 평이 많더라고요. 하지만 마지막 문제는 정말 건들지도 못할정도로 어렵더라고요. 저는 처음풀어보는 것은 아니지만 4시간동안 6개를 풀었습니다!이 문제는 사용자들끼리