들어가며요즘 알고리즘, 자료구조를 열심히 공부하고 있는데 그중 DFS/BFS 문제를 집중적으로 공략하고 있습니다. 아직 제가 재귀함수에 익숙하지 않기도 하고, 또 해당 문제는 사실 일반적인 DFS 문제이기는 한데, 얕복 깊복 개념 고려 안하고 막 풀었다가 예상과 다른 결과가 나와서 당황하게 되었던 문제입니다. 해당 이슈를 겪었던게 인상깊고 재밌어서 해당 문제 풀이를 포스팅하게 되었습니다.풀이코딩테스트 연습 - 여행경로 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr로직 설명 사용한 티켓이거나 출발지가 다..
코딩테스트 연습 - 다음 큰 숫자 | 프로그래머스 스쿨 (programmers.co.kr) n은 1,000,000 이하의 자연수 풀이 Time Complexity: O(1) Auxiliary Space: O(1) 아이디어: 오른쪽 대부분의 비트(LSB, Least Significant Bit)는 왼쪽 대부분의 비트보다 빠르게 변화함 이 아이디어는 x에서 1의 가장 오른쪽 문자열을 찾고 패턴의 가장 왼쪽 비트를 제외한 오른쪽 극단으로 패턴을 이동함. 패턴에서 가장 왼쪽에 있는 비트(누락된 비트)를 x의 왼쪽 부분으로 한 위치씩 이동함 상세 설명 해당 추가 테스트 케이스들을 보자. 더 힌트를 얻어보자면.. 여기서 규칙을 발견할 수 있다. 가장 오른쪽에 있는 1 뭉치들에 대해서 일정한 패턴이 보인다. 혹은 논..
코딩테스트 연습 - 영어 끝말잇기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr HashSet 사용 시간 복잡도 O(n) 설명) 1. && 연산자는 순서대로 판별하기 때문에 if 문 내 i > 0 조건이 뒤로 배치된다면 오류남 2. string 마지막 글자 가져오는 법) 총 길이 - 1 인덱스로 가져오거나 아니면 slice(-1) 로 가져올 수 있음 3. 조건 대로 분기점 처리 잘 해주면 됨 4. 문제에서 원하는 답을 계산하는 간단한 규칙 알면 됨
코딩테스트 연습 - 행렬의 곱셈 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 행렬의 곱셈, 행렬의 거듭제곱 – 수학방 (mathbang.net) [0]을 하는 이유는 두 번째 행렬 각 행의 길이 만큼 반복하기 위함 저렇게 안하면 코드는 첫 번째 행렬의 길이만큼 반복함 ⇨ 이 경우, n * n 행렬끼리 곱하는 경우에만 적용이 됨 ⇨ (3x2)*(2x3)이면 두 번째 행렬[3]은 없기 때문에 에러 뜸 소소하게 재미있는 포인트 행렬 곱셈은 6중 포문 쓰면 제일 연산 속도가 빠름 Putting Your ..
코딩테스트 연습 - 카펫 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - 로직 설명 1. yellow 의 약수들을 구해준다. 이때 효율적인 연산을 위해서 yellow 의 제곱근의 정수까지만 구해준다. (1~ yellow 끝까지 순회할 필요없다) → 추가적으로 설명하자면, 약수가 n * m 인 형태임을 기억하자. 약분을 구하기 위해서 n * m 을 진행할수록 n은 커지고, m 값은 작아짐 예를 들어 설명해보자면 24의 약수를 구할 경우 4² < 24 < 5² 이다. x * x 제곱근 (x = 4) ..
8번 테케 에러 해결: 마지막 문자에 공백이 있는 경우 오류 떠서 if문으로 처리해줌 split 연산자 String.prototype.split() - JavaScript | MDN (mozilla.org) 메서드 특징 이용해서 풀이 Splitting with a RegExp to include parts of the separator in the result If separator is a regular expression that contains capturing parentheses ( ), matched results are included in the array. const myString = "Hello 1 word. Sentence number 2."; const splits = myStri..
코딩테스트 연습 - 기능개발 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 1 로직 굉장히 이상한 것 같은데 어쨌든 테케 다 통과하긴 함 내가 생각한 로직 1. 필요한 일수를 구한다. 2. 큰수1 ____ 큰수2 ____ 이렇게 나눠서 보면 됨 개인적으로 보는 지금 코드 문제점 (이따가 더 생각해보거나 다른 사람 솔루션 보기) 1. mutable 하다 (count, stack, maxValue) → 관련 mutable한 코드는 왜 바람직하지 못한 코드인가 (tistory.com) 보면 좋음 2..
코딩테스트 연습 - 롤케이크 자르기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 첫번째 시도 순차적으로 slice 해서 두 배열을 각자 HashSet로 만든 다음에 개수 비교하는 로직 사용 → 시간 초과 시간 초과 이유: topping의 길이가 최대 1,000,000 이기 때문이다. for 문으로 토핑 배열 전체를 순회하면서 slice, set 으로 중복 걸러내면 시간 복잡도 O(n²)임 두번째 시도: 로직 순서 1. olderBrother → 이름을 가진 Map 객체에 key: 토핑 종류 val..
