알고리즘이 재미있다

https://school.programmers.co.kr/learn/courses/30/lessons/72415 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dfs와 bfs를 활용하는 문제이다. 난이도 자체가 어렵기보다는 빡코딩이라 실수하기 쉽다. 핵심 카드를 뒤집는 순서에 따라 카운팅이 달라지게 된다. 따라서 dfs를 통해 모든 순열을 탐색해 여한다. 중요한 점은 같은 종류의 카드가 2개가 있기 때문에 이를 어떤 카드를 먼저 뒤집느냐도 중요하다. -> 뒤집은 이후에 해당 위치가 달라지기 때문임. 이후 최단거리의 합들을 모두 더하면 된다. 정답 코드 ..

https://leetcode.com/problems/eliminate-maximum-number-of-monsters/ Eliminate Maximum Number of Monsters - LeetCode Can you solve this real interview question? Eliminate Maximum Number of Monsters - You are playing a video game where you are defending your city from a group of n monsters. You are given a 0-indexed integer array dist of size n, where dist[i] is the initi leetcode.com 정렬을 이용한 간단한 ..

https://leetcode.com/problems/number-of-flowers-in-full-bloom/ 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 현재의 people 위치에서 꽃이 몇 개가 있는지를 체크하는 문제이다. 매우 단순한 방법으로 브루트포스를 생각할 수 있지만, 시간복잡도 때문에 우선순위 큐를 활용하여 풀 수 있었다. 핵심 문제의 요구 ..

매일 알고리즘을 풀지만 최근에는 알고리즘에 대한 블로깅을 조금 소홀히 하였다. 어느 순간 취미활동인 느낌이 들기도 하였다. 아직도 많이 부족하지만 나름 많은 문제를 풀고, 옛날 생각도 나서 알고리즘 사이트에 대한 나의 생각을 적어보면 재미있겠다는 생각이 들어서 작성하게 되었다. 모든 내용은 온전히 개인적인 의견이며, 단순히 재미용으로 봐도 무방하다. 백준 https://www.acmicpc.net/ Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 아마 제일 유명하다고 생각한다. 굳이 설명 안 해도 모두 다 알 것이다. 대부분의 사람들이 처음 알고리즘 문제를 접하는 곳이 아마 백준이라고..

https://leetcode.com/problems/shortest-path-visiting-all-nodes/?envType=daily-question&envId=2023-09-17 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 최단경로를 찾는 문제이다. 즉 bfs를 활용하여 풀 수 있다. 핵심 최단경로를 찾는 문제이지만, 방문한 곳을 다시 갈 수 있다...

https://leetcode.com/problems/reconstruct-itinerary/ 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 이 문제와 거의 유사한 문제를 프로그래머스에서 풀었던 기억이 난다. 그때도 dfs를 사용하여 풀었다. 핵심 문제 자체는 되게 단순하다. List에 시작점, 도착점을 저장해 둔 상태인데, 계속해서 이어나가면 된다. 단 정..

https://school.programmers.co.kr/learn/courses/30/lessons/81303 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음 보자마자 생각난 방법은 링크드 리스트였다. 아마 정석적인 풀이 방법이 링크드 리스트라고 생각한다. 하지만 이 문제는 StringBuilder를 사용하면 쉽게 풀 수 있다. 핵심 StringBuilder의 함수를 잘 사용하면 매우 쉽게 풀 수 있다. 정답 코드 import java.util.Stack; class Solution { public String solution(int n, int ..

https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 완전탐색을 하면 시간초과가 발생하는 문제이다. bfs와 dfs 중 원하는 것을 골라서 풀 수 있다. 핵심 bfs든 dfs든 break 포인트를 걸어주어야지만 시간초과를 막을 수 있다. 또한 사전순으로 탐색하기에 탐색 조건의 순서를 사전순으로 배치하면 더 쉽게 풀 수 있다. 이 문제에서 재미있는 점은 방문한 곳을 한 번 더 방문할 수 있다는 것이다. 다만 k번의 움직임만에 도달해야 하기에 남은 거..

https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr DFS로 풀 수 있는 문제이다. 핵심 n의 크기가 작기 때문에 dfs를 통한 완전탐색을 사용하여 풀 수 있다. 즉 모든 경우의 수를 구하고 그때의 점수를 비교하는 방식으로 풀면 된다. 정답 코드 import java.util.ArrayList; import java.util.List; class Solution { private final List results = new ArrayList(); ..

https://school.programmers.co.kr/learn/courses/30/lessons/17678 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 구현문제이며 상당히 재미있는 문제라고 생각된다. 핵심 우선 내가 처음 시작 전 설계를 한 주석이다. /** * pq를 만들어서 timetable의 데이터를 분단위로 바꿔서 넣어줌 * 시작시간 9시 부터 t간격으로 n번 timetable의 데이터가 시간보다 작거나 같으면 poll해줌 최대 m까지 * 만약 m이 전부 가득차면 마지막 뺀시간의 -1을 저장, m이 가득안차면 출발시간을 저장 */ 사실 단..