공부해볼라는 스토리

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42578# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 와우 진짜 이문제 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 골때리고,, 많이 배운 문제 나왜래 바보임? 싶은 2-1) 조합 풀이 일단 나는 조합으로 접근했어서 첨에 진짜 초단순하게 그 분야 의상만 입기 + (안에는 조합으로 이제 2, 3, 4, ... 조합돌리기) + 전체 한번에 입기 이렇게 분리해서 생각했는데 진짜 바보였다. ## 내 code ## import collections imp..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42576 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 2-1) parti 라는 dict을 하나 구상한다. 2-2) 각 사람이름 마다 1씩 할당해주면서 dict 구성하고, 2-3) 이제 완주 목록 돌리면서 dict 하는데 오류뜨면 한사람만 완주못했기 때문에 그사람, 만약 전체 잘돌아가면 dict value 중에 1이라도 남은 동명이인이 완주못한 경우임 2-4) 그래서 k, v 바꿔서 1인거 찾아내기!! ## code ## impo..

1. 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 2. 풀이 정말 정말 오랜 숙원을 풀었다 ㅋㅋㅋㅋㅋ 하 보니까 2년전에도 못풀었던데 DP는 진짜 나한테 어려웠는데 눈앞에 닥친 코테때문에 겁나 열심히 하는중 메모리 초과 -> 맞았습니다!!! 의 여정입니다. 1) 먼저, 저는 솔직히 다른 방법이 크게 생각이 안나서 고민을 많이한게 [1] 배낭문제처럼 테이블로 풀기 [2] 한 리스트에 계속 max 값 업데이트하는 방식 이정도로 고민했는데,, 결론적으로..

실4 1. 문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 2. 풀이 실버 수준의 그리디/DP 문제이다. 예전에 그리디하게는 풀었었는데, DP로도 풀고 싶어서 다시 풀었다!! 1) Greedy 방법 1-1) 우선 그리디하게 풀어야하니까, 현재상황에서 가장 최선이도록 욕심을 부려야한다 == 5키로를 최대한 들자 ! 1-2) 따라서 간단하다. 현재 주어진 숫자에 5로 나눠서 나눠지면 바로, 아니면 3씩 줄여가면서 5의 배수를 찾아가는지 해보면된다. 마지..

브1 1. 문제 https://www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 2. 풀이 코테 준비하면서 구현 문제가 중요하다고 하길래 추천 문제를 풀고있다. 구현 문제들이 브론즈 문제들 추천이 많아서 일단 오랜만에 푸는데, 속도를 더 올려서 빠르게 마무리 할 수 있도록 해야겟다ㅜ___ㅜ 구간합을 구하는 문제인데, ## code ## import sys ''' - 시작 점, 끝점 구해서 ~ 시작 숫자 같은 경우, 뒤에만 고려 ~ 달라서 앞, 중간, 뒤로 나눠서 더하기 ''' sta..

1. 문제 https://leetcode.com/problems/maximum-subarray/description/ 2. 풀이 오늘은 DP 공부를 하면서 배낭문제나, 피보나치로 타뷸레이션/메모이제이션을 공부했다. 개중에 처음으로 배운 'Kadane's Algorithm'을 배우게 되어서 남긴다! 카데인 알고리즘은 하나의 배열에서 연속된 부분합의 최대를 구할때 용이하다. 1) 카데인 알고리즘 적용 1-1) 현재 max, 전체 max 변수를 설정한다. 1-2) nums[0]을 각각 최대값 저장 변수에 할당해줬다면, 이제 그 뒤로 얘를 더하는게 클지, 안더하고 다음 nums[i] 자체가 클지 판단한다. 1-3) 현재max / 전체max 중 무엇인가가 더 클 것이고, 그럼 이 curr_max를 best_max..

1.문제 https://leetcode.com/problems/3sum/description/ 2.풀이 문제는 세 가지 수의 합이 0이 되는 경우의 수를 모두 구하는건데, 여기서 중복이 없어야한다. 리스트가 커져서 그냥 브루트포스로 풀게되면 o(n^3) 으로 너어어무 느려진다. 그래서 좀 더 빨리 풀 수 있는 방법이 투 포인터인데, 왜 투포인터일까? 바로 하나를 고정시키고 나머지만 움직이면 되기 때문이다. 투 포인터는 정렬된 배열에서 유용해서 정렬해주는게 좋다. 1) 우선 리스트를 순서대로 정렬해줘야한다. 이게 오래걸려보여도 한 번 정렬해주는게 후일을 위해 좋다,, -> O(nlogn) 정도니 할만하다. 2) 이제 세 수를 i, j, k라하면, i를 고정시키는데 nums - 2 까지 돌려야한다. 2개는 ..

1. 문제 https://leetcode.com/problems/shortest-path-in-binary-matrix/description/ 2. 풀이 이 문제는 BFS 푸는게 가장 간단할듯하다. 가중치없는 bfs라서, matrix 좌표에 따른 현재 cost 계산해서 가는 방식으로 하면 될듯!! 1) 이진 매트릭스 크기랑 같은 방문확인 매트릭스를 구축하고, 8방향 이동가능해서 이동 반경을 설정한다(dx,dy). 2) stack은 [x, y, cost]를 저장해서 bfs로 순회할 수 있게 하는 스택이다. 3) 방문했는지, 안했는지 체크하면서 순회하며 이전 cost에 1씩 더해가며 계산한다. 4) 이 방법이 최단 거리를 보장하는 이유는, 최종 도착지를 만나면 멈추는데, 먼저 왔다는건 빠르게 왔다는 의미이기..

1. 문제 https://leetcode.com/problems/trapping-rain-water/description/ 2. 풀이 일단 풀이는 참고하면서 공부중입니당 우선 구체적 풀이 전 뭔가 인사이트를 생각해보자면 빗물이 받아지는 부분은 붙어있는 막대라면 높이 차이가 날때, 높이가 0이면 옆 막대 vs 이전 막대 높이에 영향을 받는다 1) 투포인터 (two-pointer) 자, 우선 좌 와 우에서 각각 시작한다고 생각해보자 1-1) 0과 length-1에서 시작, 이 두 인덱스가 만날때까지 진행한다 1-2) 둘의 최대높이가 각각 있다고 가정하면, 그게 더 작은걸 다음인덱스로 이동한다 ==> 이 이유는 낮은 막대가 물의 양을 결정하기 때문임, 단순하게 생각하면 막대가 3개뿐이면 [1,0,2], 2를 ..

리트코드를 시작했숨니다 우하하,, 시작은 항상 잼이써 매일매일 잔디를 심읍시다 [문제] https://leetcode.com/problems/number-of-islands/description/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com [풀이] class Solution: def numIslands(self, grid: List[List[str]]) ..