알고리즘이 재미있다

https://school.programmers.co.kr/learn/courses/30/lessons/258707 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제도 저번에 봤었는데, 시간이 없어서 제대로 분석하지 못했었다. 다시 여유 있을 때 지문을 읽어보니 단순 구현 문제였다. 핵심 직관적으로 생각하면 순간순간 카드를 받을지 말지에 대한 모든 케이스를 생각해야 할 것 같지만, 실제로는 모든 카드를 다 받고 사용할 때 코인을 제출하면 된다. 정답 코드 import java.util.ArrayList; import java.util.List; cl..

https://school.programmers.co.kr/learn/courses/30/lessons/258709 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 예전에 시도했다가 시간초과가 떴던 문제이다. 사실 이전에 풀 때도 시간초과가 날 거라고 거의 확신하고 푼 문제였기에 이번에 시간이 남아서 다시 풀어보았다. 핵심 이번 문제는 구현, 조합, 이분탐색을 사용해야 한다. 내가 맨 처음 접근한 방법은 완전탐색인데 이는 10개 중 5개의 주사위를 고르는 방법 10C5와 각각의 주사위의 합 6^5과 나머지 주사위들의 합인 6^5를 전부 비교해야 하기에 약 ..

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://www.acmicpc.net/problem/9335 9335번: 소셜 광고 진욱이는 새로운 소셜 네트워킹 회사를 만들기로 결심했다. 하지만 기존의 페이스북 이나 트위터 같이 인기있는 소셜 네트워크 서비스는 이미 수십억의 사용자를 가지고 있고, 진욱이는 이들과 www.acmicpc.net 오랜만에 백준을 풀었는데 재미있는 문제가 있어서 가져왔다. 백트래킹을 통한 완전탐색 문제이다. 핵심 각각의 사람마다 광고를 보여줄지, 안 보여줄지 선택한다. 최대 인원은 20이다 -> 2^20 이므로 충분히 가능한 시간이다. 정답 코드 import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { ..

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://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번의 움직임만에 도달해야 하기에 남은 거..