꾸준함

[Programmers] 표현 가능한 이진트리

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 해당 문제의 핵심은 서브 트리 내 루트가 반드시 1이어야 한다는 점입니다. 알고리즘은 다음과 같습니다.1. 주어진 십진수를 이진수로 변환한 뒤 포화이진트리 형태가 아니라면 포화이진트리 형태가 되도록 0을 추가해 줍니다.2. 1번에서 구한 이진수의 가운데를 시작으로 모든 서브 트리 내 루트 노드가 존재하는지 확인합니다.2.1 2번 조건이 성립하면 1, 성립하지 않으면 0을 answe..

[Programmers] 미로 탈출 명령어

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 사전순으로 가장 빠른 경로를 구해야 하므로 그리디 하게 [d, l, r, u] 순으로 백트래킹하면 되는 문제였습니다.시간을 단축시키기 위해 현재 지점과 탈출 지점 사이의 맨해튼 거리를 구해 거리가 안될 경우 가지치기를 진행했습니다.  개발환경: Programmers IDE   지적, 조언, 질문 환영합니다! 질문 남겨주세요~

백준 1344번 축구

문제 링크입니다: https://www.acmicpc.net/problem/1344 문제 지문으로부터 메모이제이션을 적용할 수 있는 상태값은 구간, A팀 득점 수, B팀 득점 수임을 유추할 수 있습니다.따라서 세 상태값을 기준으로 DP를 적용하여 풀면 되는 문제였습니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[Programmers] 등산코스 정하기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 다익스트라 알고리즘을 활용하여 풀 수 있는 문제였습니다.일반적인 다익스트라 알고리즘처럼 가중치를 더해나가는 것이 아니라 등산로 내 최대 가중치를 업데이트하는 방식으로 코드를 작성해야 했습니다.  개발환경: Programmers IDE   지적, 조언, 질문 환영합니다! 질문 남겨주세요~

[Programmers] 고고학 최고의 발견

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/131702?language=cpp 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 백준 14927번 전구 끄기와 비슷한 문제였습니다. 알고리즘은 아래와 같습니다.1. 첫 번째 행에 대해 모든 경우의 수를 구한 뒤2. 두 번째 행부터 바로 위 행의 시곗바늘을 12로 만들도록 처리합니다.3. 위와 같이 진행할 경우 1 ~ (N - 1)행의 시곗바늘은 모두 12를 바라보고 있습니다.3.1 따라서 마지막 행의 시곗바늘이 모두 12를 바라보고 있을..

백준 17837번 새로운 게임 2

문제 링크입니다: https://www.acmicpc.net/problem/17837 문제에서 주어진 대로 풀면 되는 문제였습니다.저는 같은 칸에 여러 개의 말이 위치할 수 있고 쌓인 순서를 토대로 로직이 달라질 수 있기 때문에 stack 자료구조를 사용하여 말이 쌓인 순서를 표현했습니다,. * moveDir[4]를 {1, 0}이 아닌 {0, 1}로 해놓고 맞왜틀 이러고 있었네요... 아까운 내 시간 개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

백준 1535번 안녕

문제 링크입니다: https://www.acmicpc.net/problem/1535 전형적인 Knapsack DP 문제였습니다.세준이의 체력이 0이어도 기쁨을 못 느낀다는 것이 핵심이었습니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

백준 1513번 경로 찾기

문제 링크입니다: https://www.acmicpc.net/problem/1513 문제 지문으로부터 메모이제이션을 적용할 수 있는 상태값은 현재 위치(y, x), 방문한 오락실 개수, 그리고 직전에 방문한 오락실 번호임을 유추할 수 있습니다.따라서 네 상태값을 기준으로 DP를 적용하여 풀면 되는 문제였습니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

벡즌 12865번 평범한 배낭

문제 링크입니다: https://www.acmicpc.net/problem/12865 전형적인 Knapsack DP 문제였습니다.주의할 점은 동전 2 문제와 달리 각 물건은 하나씩 존재한다는 점입니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

백준 12852번 1로 만들기 2

문제 링크입니다: https://www.acmicpc.net/problem/12852 연산을 하는 횟수의 최솟값은 DP를 통해 간단하게 구할 수 있는 문제였습니다.문제는 " N을 1로 만드는 방법에 포함되어 있는 수"를 출력하는 것이었는데 이는 DP에 사용했던 cache 배열을 역추적하며 구할 수 있었습니다.테스트해 본 결과 top-down 방식으로 구현할 경우 N이 100만 일 때 stackoverflow가 발생하는 것 같은데 AC를 받는 것으로 보아 데이터 추가가 필요해 보입니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~