알고리즘 공부
-
프로그래머스-숫자블록알고리즘 공부 2023. 2. 10. 06:15
https://school.programmers.co.kr/learn/courses/30/lessons/12923 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오늘 풀어볼 문제는 프로그래머스의 숫자블록 문제이다. 이 문제 같은 경우 예전에 한번 풀어본 적 있는데 그저께 지문과 테스트케이스가 새롭게 바뀌었다고 해서 다시 한번 풀어보았다. 이전에 풀었을 때에도 한 번에 맞지 못하고 우여곡절 끝에 맞았던 기억이 있던 문제여서 더 집중해서 풀어보았다. 풀이 아이디어: 가장 큰 약수를 찾는 것이 이 문제의 목적이다. 하지만 가장 큰 약수는 최대 10,000,00..
-
프로그래머스-하노이의 탑알고리즘 공부 2023. 2. 9. 05:13
https://school.programmers.co.kr/learn/courses/30/lessons/12946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오늘 풀어볼 문제는 프로그래머스의 하노이의 탑이다. 이 문제는 예전에 비슷한 문제로 단순히 회수만 구하는 문제를 접해본 기억이 있어서 그때의 아이디어를 이용해서 구현하였다. 풀이 아이디어: n-1번째 하노이의 탑을 만드는 방법을 이용해 n번째 하노이의 탑을 만들 수 있다. 1. n-1번째 하노이의 탑을 3번째 기둥이 아닌 2번째 기둥에 옮겨준다. 2.1번째 기둥의 마지막 원판을 3번째 기둥으로 옮..
-
프로그래머스-N-Queen알고리즘 공부 2023. 2. 8. 05:44
https://school.programmers.co.kr/learn/courses/30/lessons/12952 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오늘 해결해볼 문제는 프로그래머스의 N-Queen 문제이다. 이 문제를 처음 보았을 때는 다이나믹으로 해결해볼까 라고 생각했다. 하지만 더 생각해보니 대각선의 경우를 생각한다면 다이나믹으론 해결이 불가능하겠다는 판단이 들었다. 그래서 다음으로 생각한 것이 DFS/BFS를 사용해 보는 것이었다. 나는 그 중 deque를 이용한 BFS를 사용해보겠다고 생각했다. 풀이 아이디어: 가장 첫 열의 경우 모..
-
프로그래머스-배달알고리즘 공부 2023. 2. 6. 04:52
https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오늘 풀어볼 문제는 프로그래머스-배달이다. 이 문제는 전형적인 최단거리 문제이다. 나는 이 문제를 다익스트라 알고리즘을 통해 풀어보았다. 정말 오랜만에 사용하는 알고리즘이라 처음에 조금 헤매기도 했다. 그래도 이론적인 부분을 이해하고 있으니 우여곡절 끝에 구현할 수 있었다. 풀이 아이디어: 간단하게 다익스트라 알고리즘을 통해 각각의 노드에 대해 최단거리를 구한 뒤 K보다 작은 것들의 개수를 세주었..
-
프로그래머스-[1차]프렌즈 4블록알고리즘 공부 2023. 2. 5. 04:59
https://school.programmers.co.kr/learn/courses/30/lessons/17679 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오늘은 어제 풀다가 아이디어만 떠오르고 다 풀지 못했던 프로그래머스-[1차]프렌즈 4블록 문제를 풀어보았다. 이 문제를 풀면서 가장 많이 오류가 발생했던 것은 for구문을 여러개 쓰면서 변수가 겹쳤던 것이다. 예를 들어 위에서 m을 이미 정의 했는데 for구문의 변수로 m을 지정하는 등 신경쓰지 않으면 평소에 사용하던 변수를 자꾸 사용해 앞서 정의된 것들이랑 겹치게 정의가 되는 것이다. 이런 것들..
-
프로그래머스-[1차]캐시알고리즘 공부 2023. 2. 4. 06:01
https://school.programmers.co.kr/learn/courses/30/lessons/17680 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오늘 풀어볼 문제는 프로그래머스의 [1차]-캐시 문제이다. 이 문제는 처음 보았을 때 LRU(Least Recently Used) 알고리즘이 무엇인지 몰라 자꾸 풀이를 틀렸었다. 단순히 최근에 사용한 것들을 캐시에 저장한다고 생각해 단순하게 구현하였더니 틀렸던 것이다. 그래서 검색을 통해 알아보니 LRU는 hit과 miss를 통해 캐시를 계속해서 갱신해준다. cache를 확인했을 때 hit이면 알..
-
프로그래머스 호텔 대실알고리즘 공부 2023. 2. 3. 04:58
오늘은 코딩테스트 문제 2문제를 풀었다. 하나는 어제 고민했던 프로그래머스-방금그곡 문제이고 하나는 오늘 따끈따끈하게 올라온 호텔 대실 문제였다. 사실 호텔 대실 문제는 단순한 그리디 문제였고 방금그곡 문제는 조금 복잡하게 해결했다. 그래서 더 간단하게 작성해보고 싶어서 아직 만지고 있는 문제라 오늘은 호텔 대실 문제를 해결해보고자 한다. https://school.programmers.co.kr/learn/courses/30/lessons/155651 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 아이디어: 단순하게 대실 시작 시간 순서로 정렬 후..
-
프로그래머스(전화번호 목록)알고리즘 공부 2023. 2. 2. 04:56
https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오늘 풀었던 문제 중 가장 떠올리기 힘들었던 문제였다. N의 길이가 1,000,000이고 완전탐색을 이용하면 O(N^2)의 경우의 수가 발생해서 시간복잡도 문제가 발생하였다. 그래서 어떻게 해야할지 계속 고민하다 맨 앞의 숫자만 비교하면 되는거 아닌가? 라는 생각이 들었다. 그래서 정렬을 통해 맨 앞의 숫자가 비슷한 것 끼리 나열 후 양 옆의 수를 비교해주기로 했다. def solution(pho..