Blog for Programming

1. 문제 및 예시 실행 결과  중구난방으로 알고리즘 문제를 풀다 이러면 아무것도 안 될 것 같아서 내가 약한 유형의 문제를 우선적으로 공부해야겠다는 생각해 DP문제를 쭉 풀어보았다. 바킹독님의 블로그에서 공부하고 있는데 풀이가 달라 한 번 정리해보았다. 출처: https://www.acmicpc.net/problem/25792. 본문  DP는 데이터 구조를 먼저 생각해보고 점화식을 세우는 두가지의 단계로 나뉜다고 생각한다. 물론 점화식을 세운다는 것 자체가 안 되는 문제이기에 구현 다음으로 손에 익어야하는 문제가 아닌가 싶다. 어쨎든 해당 문제의 데이터 구조와 점화식은 다음과 같이 정했다.데이터 구조: cache[i] = i번째 계단으로 얻을 수 있는 점수 중 최대값. 이제 데이터 구조를 구하는 점화식..

1. 문제 및 예제  카카오 문제에 신나게 달려들었다가 멘탈 박살났다. 처음 들어갈때는 "이게 왜 LV.2야 ㄷㄷ" 라는 생각이 들었는데, 풀다보니 "이게 왜 LV.2야?" 라는 생각이 계속 들었다. ㅋㅋ 임의로 생성된 노드를 구하는 방법이 진입 간선과 진출 간선의 수를 가지고 구한다는 생각을 하지 못해 결국 남의 풀이를 찾아 보았다. 역시 카카오는 기발한 생각으로 쉽게 문제를 풀 수 있거나 문자열과 같이 미친 집중력과 피지컬을 요구하는 쌩짜 구현 이 둘로 나뉘는 것 같다. 불평 해봤자 달라질 건 없으니 해당 방법으로 임의의 노드를 구하고 각 그래프의 종류를 구했다. 각 그래프의 종류를 구하는 방법은 어렵지 않았다. (솔직히 간선의 수로 다 해결할 수 있는 문제였구나를 나중에 깨달았다.)https://s..

1. 문제 및 예제 Level 2 문제들을 쭉 풀어가던 도중 PCCP 기출문제 두 문제가 공개되어 바로 풀어보았다. BFS 알고리즘이 핵심이지만, 더 빠른 알고리즘을 위해 범위를 저장하는 부분이 필요하였다. https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 시간 복잡도 때문에 BFS로는 풀 수 없다. O(N^3)이기 때문에 다른 방법을 생각해야 했다. 내가 생각한 방법은 다음과 같다. 아래와 같은 입력이 주어졌다고 가정하자. 이렇..

1. 문제 및 예제 그리디와 구현을 살짝 섞은 듯 했다. Queue를 사용하긴 했는데 차마 BFS느낌은 아니었다. 카테고리가 Greedy에 있는데 이건 어디까지나 알파벳을 바꾸는 비용을 구하는 과정이지 전체적인 정답은 BFS 혹은 구현으로 구해야한다는 생각이 든다. 이런 분류 때문에 정답률이 낮은건지... 설계한 내용 그대로 한 큐에 정답이 맞아 기분이 좋았던 문제이다. 물론 풀이시간은 좀 길었다. 여러가지 예외를 생각해서 설계하느라 그런 것 같다. 어떤 사람들은 그냥 자동으로 예외처리가 된다던데... 그런 사람들이 부러울 뿐이다. ㅎㅎ https://school.programmers.co.kr/learn/courses/30/lessons/42860 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포..

1. 문제 및 예제 이건 입력되는 데이터의 최대값만 봐도 전부 돌리는 Brute force라는 것을 알았다. DFS와 조합 중에 고민하였는데 이는 사치라는 생각을 깨닫고 조금 더 빠르게 구현할 수 있도록 재귀 함수를 사용해 조합을 구현해보았다. 최대의 후보키를 구하는 문제여서 햇갈릴 수 있는데 속성이 작은 쪽부터 순차적으로 올라간다면 이 부분은 해결된다. 카카오의 문제들은 항상 높은 집중력을 요한다... 구현 문제를 기본적으로 효율적이게 접근할 수 있는 사람이 유리할 것 같다. https://school.programmers.co.kr/learn/courses/30/lessons/42890 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, ..

1. 문제 및 예제 지문 그대로 구현하면 됐다. 오히려 지문을 이해하면서 시간이 조금 오래 걸린 문제였다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 문제를 쪼개는 것보다는 그냥 각 기능을 하는 함수를 이번 단원에서는 소개하는 것이 훨씬 효율적이라고 생각한다. - get_uv() 해당 함수는 u와 v를 분리하는 함수이다. 여는 괄호와 닫는 괄화의 갯수가 항상 같기에, 간단하게 각 괄호의 수만을 count하는 방식으로 함수를 구현했다. 클린 코드를 만들어보고 싶어서 vector을 return해준다. vector get_uv(string str..

1. 문제 및 예제 Brute force 문제임을 알았지만, 어느 정도 돌려야할지 모르겠어서 초반에 시간 초과가 좀 나온 문제다. 그것만 정하면 알고리즘을 세우는데는 문제가 없었다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 문제를 나누는건 간단하다. 1. 가장 큰 값이 전체 합의 반 보다 크거나, 전체 합이 홀수면 -1을 반환. 2. 만약 두 큐의 합이 같다면 count를 정답으로 반환. 3. 큰쪽의 원소를 pop하여 작은쪽에 push 4. 위의 과정 300000만큼 반복(전체 원소를 이동시키는 수) 다음은 전체 코드이다. #inclu..

1. 문제 및 예제 엄청난 구현 문제. 설계를 잘 하면 그렇게 어렵지 않게 해결할 수 있다. 중요한 점은 한 배열에서 사라질 모든 블럭을 찾아낸다는 것 같다. 블럭이 포함되어 있다는게 조금 까다로웠다. https://school.programmers.co.kr/learn/courses/30/lessons/17679 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 문제를 나눠보았다. 1. 블록을 터트리고 터진 블록의 갯수를 반환한다. 2. 터진 블록을 아래로 내린다. 다음은 전체 코드이다. #include #include #include #in..