Algorithms
알고리즘 문제를 풀며 정리한 접근과 풀이 기록
이 선반의 목적
문제를 다시 풀 때 떠올릴 접근과 실수 패턴을 축적하는 선반입니다.읽는 길
풀이보다 먼저 조건을 쪼개고 선택지를 좁히는 사고 흐름을 봅니다.읽는 순서
기록 순서
- 01
#[프로그래머스][연습문제] 3 x N 타일링 풀이
문제풀러가기✈유명한 DP 문제 2 x N 타일링의 업그레이드 버전 이젠 세로의 길이가 2가 아니라 3이다!!DP 공식을 잘 유도하면 쉽게 풀 수 있다!!자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기dp 공식을 유도해야하는데 순서대로 잘 그려보
- 02
[프로그래머스][2019 kakao] 블록게임 해설
정답률 : 5.85%문제풀러가기피지컬을 극복하려는 프로도의 피빠진 노력게임의 규칙은 간단하다.위에서 검은색 블록을 떨어뜨린다.검은블록을 포함하여 특정 블록이 직사각형의 형태가 되면 그 블록을 지울 수 있다.특정 블록은 무조건 한 개체여야하며 다른 개체와 섞여서는 안된다
- 03
[프로그래머스][2019 kakao] 길 찾기 게임 문제 해설
정답률 : 7.40%문제풀러가기"전무"로 승진한 라이언이 왕따인 이유를 알려주는 문제."전무" 라이언이 x, y 좌표값을 주면 우리 친구들이 x, y 를 전부 순회를 마친 팀이 이기는 "라이언만" 재미있는 게임이다.x, y 좌표는 사실상 트리의 구성요소라고 생각하면 된
- 04
[프로그래머스][2019 kakao] 무지의 먹방 라이브 문제 해설
정답률: 정확성 42.08% / 효율성 5.52%문제풀러가기특별한 먹방을 하려는 무지. 회전테이블에 각각의 음식을 놓아두고 자신 앞의 음식을 1초 동안 섭취 한 다음 회전판에 의해 다음 음식을 1초동안 섭취하는 특이한...회전하는데 걸리는 시간은 없다고 본다.빈 그릇이
- 05
[프로그래머스][2019 kakao] 후보키 문제 해설
정답률 : 16.09%문제풀러가기input 으로 들어오는 릴레이션의 정보를 토대로 후보키 를 생성할 수 있는가에 대한 문제최소성과 유일성을 만족해야한다유일성 : 해당하는 릴레이션에 대해 유일하게 식별 가능해야한다.최소성 : 키를 구성하는 속성 중 하나라도 제외 하는 경
- 06
[프로그래머스✈][2020 kakao] 자물쇠와 열쇠 문제 풀이
정답률: 7.4%문제풀러가기✈고고학자로 위장한 도굴꾼 튜브는 고대 유적지에서 자물쇠를 발견했습니다.가지고 있는 열쇠가 이 자물쇠에 맞는지 사방으로 끼워보고 돌려서도 끼워보고 해서 자물쇠를 열어 발굴할 수 있는지 확인하려고 합니다. 문제를 푸시오.자세한 문제 설명과 제한
- 07
[프로그래머스][2020 kakao] 기둥과 보 설치 문제 해설
정답률 : 1.9%문제풀러가기죠르디 는 기둥과 보를 이용하여 벽면 구조물을 자동으로 세우려고 한다. 2차원 벽면 n x n 의 격자칸이 주어지고, 기둥과 보를 설치하고 제거하는 명령어가 주어 질 때 해당 명령어가 실행 가능하다면 실행하라.자세한 문제 설명과 제한 사항은
- 08
[프로그래머스✈][2020 kakao] 가사 검색 문제 풀이
정답률정확성: 34.4%효율성: 0.8%문제풀러가기✈너 TRIE 자료구조 아냐?자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기트리가 아니다 T.R.I.E. 다.TRIE 자료구조는 단어의 각 글자를 Node 로 보고 자료를 저장하는 자료구조입니다
- 09
[백준🔉][16234] 인구이동 문제 해설
정답비율 : 36.044%문제풀러가기✈1 x 1 모양의 사각형이 n x n 만큼 펼쳐진 땅이 있다고 가정한다.각 사각형은 나라를 지칭하며 그 안에는 백성들의 숫자가 있다.매우 자유로운 이 대륙의 특정한 나라는 다른 나라의 인구수와 비슷하다면 연합을 하여 연합국 간 인구
- 10
[프로그래머스✈][2019 kakao 겨울 인턴십] 불량 사용자 문제 해설
문제풀러가기✈우리가 사용자를 밴 할껀데 사실 나도 누가 밴 해야하는지 원본을 잃어버렸어... 혹시 가능한 경우의 수... 니가 좀 구해줄래? 일단 한번 보고 다 밴하던가 할게....문자열에 별표가 들어있다. 이 문자열의 별표는 알파벳과 숫자로 대체 가능하다. 조건에 맞
- 11
[프로그래머스✈][2020 kakao] 동굴 탐험
문제풀러가기✈우리 프로도는 특정한 규칙을 세워서 동굴의 각 방들을 탐험 하려고 한다. 해당 규칙을 만족하게 계획을 세우고 모든 방을 탐험할 수 있는지 탐색하라!자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기루트부터 각각의 방들을 탐색하며, 선행
- 12
[백준🔉][14501] 퇴사 문제 해설
정답비율 : 47.669%문제풀러가기✈우리팀에서 가장 열심히, 돈을 위해 직장을 다니던 훌륭한 백준 직원이 퇴사를 하려고 한다.퇴사하기 전까지 가장 많은 돈을 버는 (가장 많은 일을 하는게 아닌) 계획을 짜고 수행하려 한다.백준이가 돈을 많이 벌 수 있게 도와주자.자세
- 13
[프로그래머스✈][2017 카카오코드] 4단 고음 해설
🛑🛑 아이유 팬은 주의 🛑🛑🛑🛑 아이유 팬은 주의 🛑🛑🛑🛑 아이유 팬은 주의 🛑🛑🛑🛑 해당문제를 풀지 말고 돌아가길 권고 🛑🛑문제풀러가기✈우리 지은이는 3단 고음을 넘어 4단 고음을넘어2147483647 단 고음을 연습중이다.우리 지은이는
- 14
[프로그래머스✈][2019 kakao 겨울 인턴쉽] 징검다리 건너기 해설
문제풀러가기✈"우리 돌다리는 약해유.."니니즈 친구들이 라이언 선생님과 함께 가을 소풍을 가는 중에 징검다리를 만났다. 이 징검다리의 돌은 매우 연약하여 여러번 밟으면 부서지고 더이상 사용할 수 없다. 돌마다 내구도가 주어질 때 건널 수 있는 니니즈들의 최대 인원 수를
- 15
[프로그래머스✈][연습문제] 섬 연결하기 풀이
문제풀러가기✈섬을 연결해!! 최소비용으로!뭐? 어디서 본 거 같은데 ??자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기최소신장트리를 푸는 유명한 2가지 방법이 있다.크루스칼 알고리즘프림 알고리즘솔직히 둘이 좀 헷갈린다. 최소비용 부터 시작하는게
- 16
[leetcode][15] 3sum 문제풀기!
문제풀러가기✈숫자를 엄청 줄게!!숫자 3개를 뽑아서 그 숫자들의 합이 0 이 되는 부분집합좀 찾아줘!자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기숫자 세개를 뽑아서... 0 을 만드는지 확인하면 된다!.다만 3개 전부 완전탐색을 돌려버리게 된다면 타임아웃이 뜨
- 17
[leetcode][16] 3sum closet 문제풀기!
문제풀러가기✈이번에도 숫자를 엄청 줄게!!숫자 3개를 뽑아서 그 숫자들의 합이 내가 원하는 숫자랑 가장 가까워지는 값을 찾아줘!!자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기이번에도 숫자 세개를 뽑아서... 더해서 ... 원하는 숫자와 얼마나 가까운지 체크하면
- 18
[📣top interview question] Remove Duplicates from Sorted Array Solution 문제풀기!
문제풀러가기✈정렬된 배열을 하나 줄게!중복된 숫자 없는 배열을 갖게 해줘!!자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기문제를 잘 읽어보면, 다른 배열을 만들어서 사용하지 말고 추가 메모리는 하나만 사용하라고 명시되어있다!.이 문제는 채점할 때 다음과 같이 하
- 19
[📣top interview question] Best Time to Buy and Sell Stock II 문제풀기!
문제풀러가기✈어떤 물건의 가격이 매일 달라..매일 달라지는 가격을 줄테니...나를 부자로 만들어줘!!자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기가격이 언제 꺾이는지 (하강하다 상승, 상승하다 하강) 에 포인트를 주면 될 것 같다.하강하다가 상승한다면 그 지점
- 20
[leetcode][30] Substring with Concatenation of All Words 문제풀기!
문제풀러가기✈문자열과 단어집을 줄테니 단어집의 모오오오든 단어를 포함하는 문자열의 부분 집합을 찾아줘!!자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기단순히 Brute force 기법을 쓴다면 시간제한에 걸리게 된다.자료구조 Map을 통해 특정 문자를 logN
- 21
[leetcode][31] Next Permutation 문제풀기!
문제풀러가기✈다음 순열 구해라.자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기솔직히 말해서 다음 순열이 뭔데? 뭔데? 하면서 한 5분은 찾아봤다.다음 순열은 예를 들면 다음과 같다.숫자 1,2,3,4 각각 하나씩 있다. 이를 통해 순열을 만들어보면1,2,3,44
- 22
[leetcode][32] Longest Valid Parentheses 문제풀기
문제풀러가기✈"(" 또는 ")" 로만 구성되어 있는 문자열을 줄거야!!유효한 괄호들의 가장 긴 길이를 구해줘!자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기유효한 괄호의 조건은 ")" 가 나왔을 때 "(" 의 개수와 대조해보면 된다!!"()()" -> 유효하다!
- 23
[leetcode][40] Combination Sum II 문제풀기!
문제풀러가기✈숫자들을 줄게. 그 숫자들을 조합해서 내가 원하는 숫자가 나오는 조합을 찾아줘!단, 그 찾은 조합끼리 중복이 있으면 안돼!! 그리고 특정 숫자를 내가 준 개수보다 더 많이 쓰면 안돼!!!!자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기모든 경우를 다
- 24
[leetcode][42] Trapping Rain Water 문제풀기!
문제풀러가기✈내가 말이야.. 특이한 목욕탕을 만들고 싶거든.. 근데 물이 얼마나 필요할지 잘 모르겠어.. 니가 좀 구해줄래?자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기대표적으로 이런 문제는 대부분 2 pointer 문제더라!!일단 물 높이를 생각해보자. 인풋
- 25
[leetcode][43] Multiply Strings 문제풀기!
문제풀러가기✈숫자 두개를 문자열로 줄테니 곱해줘!근데 숫자가 엄청 커 ㅎㅎ;;;자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기BigInteger 를 쓰면 매우 쉽지만, 그러라고 문제 푸는거 아니잖아 ? ? ?나는 우리가 학창시절 때 배웠던 곱셈 방식을 이용했다.
- 26
[leetcode][44] Wildcard Matching 문제풀기!
문제풀러가기✈간단한 정규식 패턴을 줄게.'?' 이건 하나의 문자를 대체할 수 있는 놈이야.'\*' 임마 이거는 빈 문자를 포함해서 문자열을 대체할 수 있는 놈이야.자 이제 내가 문자열을 줄테니까 이전에 준 패턴으로 만들 수 있는 놈인지 판단해줘!자세한 문제 설명과 릿코
- 27
[leetcode][45] Jump Game II 문제풀기!
문제풀러가기✈처음 인덱스에서 마지막 인덱스에 도달하려면 몇 번 점프해야할까?해당 인덱스에서 최대 얼마나 뛸 수 있는지는 알려줄게!자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기주어지는 인풋의 길이가 최대 30,000 이기 때문에 최소 O(nlgn) 기법을 써야