java

문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 사실 알고리즘 문제를 하루에 한 문제 이상 풀고 있는데, 포스팅을 하지 않았습니다. 왜냐면,, 요새 스프링 공부를 열심히 하다보니... 포스팅을 하지 않는 대신 스프링 공부에 집중해야겠다고 생각했어요! 😅 10월 초 연휴를 아주 재밌게 즐기고 오고 나서, 문득 오늘 푼 알고리즘 문제라도 포스팅해보자! 하고 생각이 들어서 포스팅하게 되었습니다! 풀이 2차원 바텀업 DP로 풀이했습니다. 이 문제는 사실 전에 풀었던 2096번: 내려가기 문제와 유사한 풀이로 가능합니다. 문제의 내용처럼 경로 중 거쳐간 ..

C++에서는 `bool`을 사용하고, Java에서는 `int`로 -1, 0, 1로 구분해서 사용하기 때문에, 혼동이 올 때가 많았습니다. 그래서 항상 헷갈리기에 정리해둔 것을 적어두겠습니다. C++ 오름차순 : `a b` (갈수록 작아진다!) 1차원 배열일 경우 #include using namespace std; #define endl "\n" int main() { int arr[] = {5, 7, 2, 3, 6, 1, 4}; int size = 7; // --------------------------------------------------- // 오름차순 sort(arr, arr + 7, [](const auto& a, const auto& b..

문제 링크 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 이번에는 두가지 알고리즘을 합친 혼종 문제를 풀어보겠습니다.. 이번 문제는 반은 맞고 반은 다른 분의 블로그를 참고해서 풀었습니다,, 언젠가는 대부분의 문제를 저 혼자서 풀 날이 오겠죠??? 그 때를 기다리며 오늘도 열심히 달려보겠습니다~ 풀이 분리 집합(유니온-파인드) + 배낭 문제 풀이로 풀었습니다. 저도 처음에 배낭 문제가 아니라, 그저 분리 집합으로 연결된 아이..

문제 링크 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 오랜만에 DP 문제를 들고 왔습니다! 이 문제는 그 이름도 유명한 가장 긴(최장) 증가 부분 수열 (LIS: Longest Increasing Subsequence) 입니다. 이 문제는 시리즈(1번부터 5번)가 있으며, 나무위키에 등재되어 있을 정도로 잘 알려져 있습니다. 문제를 차근차근 살펴보며 풀이해봅시다! 풀이 DP를 이중선형시간(\(O(N^2)\))으로 메모라이즈하며 ..

문제 링크 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 간단하게 소수 복습을 할 수 있는 문제입니다! 사실 오랜만에 소수 문제를 풀려니, 에라토스테네스의 체를 까먹어버려서(...) 전에 풀었던 소수 문제를 참고해서 문제를 풀었습니다. 복습이 되서 좋았습니다. 풀이 간단하게 소수(정수론) + 투포인터로 풀이가 가능합니다. MAX(`4000000`)까지의 소수를 모두 구해줍니다. 투포인터를 활용해서 부분합을 구한 뒤, 제시된 N과 부분합이 일치한다면 결과값+1 을 해줍니다. 풀이코드 C++ 풀이코드 #include using namespace std; #define endl "\n" const int MAX = 4000001; ..

문제 링크 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 서론 요즘들어 DP 문제를 풀지 않아서 푸는 방법을 잊고 살고 있었습니다. 백준 문제집을 훑어보다가 좋은 DP문제가 있기에 풀어보게 되었습니다. 😄 풀이 문제에서 친절하게 그림으로 설명하듯이, 2*3칸의 구성을 잘 이용해야 합니다. 단순한 DP 풀이를 한 다음, 문제에서 주어진 메모리 제한이 \(4MB\) 여서 메모이제이션 배열의 크기가 일정 이상 커지면 메모리 초과가 발생하기 때문에 메모리 최적화 과정을 거쳐야 문제를 풀이할 수 있게 됩니다. DP 풀이 과정을 우..

문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 서론 문제가 단순해 보이지만, 소수와 백트래킹에 관한 풀이 테크닉을 갖추지 못하면 쉽게 풀 수 없는 문제입니다. 혹시 소수부터 막히시는 분들은 아래 백준 문제(1929번: 소수 구하기)를 먼저 풀고 오시는 것을 추천드립니다. 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 백트래킹에서 막히시는 분들은 아래 백준 문제(15663번: N과..

문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 서론 틱택토는 한 번 해보면 무슨게임인지 바로 알 수 있는 단순한 게임이죠. 오목의 조상? 격 게임입니다. 단순한 구현이지만, 내부 코드의 조건문으로 판단해야 하는 기준이 한두개가 아니기 때문에, 반례를 계속해서 찾으면서 풀어야 하는 문제입니다. 입출력의 예외처리를 연습할 때 풀면 아주 좋은 문제라고 생각합니다. 풀이 이 문제는 5개의 조건문을 통해 풀이가 가능합니다. 1. 'O'의 개수 + 'X'의 개수가 0과 1 사이의 값이고, 2. 'O'의 개수가 'X'의 개수보다 크거나 같고, 3. 'O'와..

문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 서론 상하좌우로 가긴 하는데, 맨 끝까지 간다는 것만 빼면 흔한 BFS 문제입니다. 뻘짓을 제외하면 늘 BFS를 풀던대로 풀었습니다. 풀이 들어온 입력(board)을 재처리 해줍니다. 입력에서 'G'를 '.' 으로 재처리해주고, 따로 저장해줍니다. 그리고 'R'은 Queue에 넣어줍니다(시작지점이기 때문에 재처리 불필요) BFS를 돌려줍니다. 그리고 vst 배열에 이동거리를 저장해줍니다. 다음으로 갈 지점(nx, ny)을 정할 때는 반복문으로 1씩 더해줬습니다. 보드의 크기가 100 이하이기 때문에..

문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 서론 이 문제는 프로그래머스 레벨 2 문제로, 자신이 어느 정도 문제 해결 능력이 있다고 생각하면, 한 번쯤 풀어볼만한 문제입니다.스택뿐만 아니라 정렬(객체 정렬), 선점 스케줄링도 공부해볼 수 있어서 많은 공부가 되는 문제입니다. 사실 문제를 풀 때, 스케줄링이라고 해서 당연히 큐를 이용하는 문제인 줄 알았는데, 두번째 예시를 보고 스택임을 알아차렸습니다... 만만하게 봤다가 예외처리와 흐름정리에 4시간 넘게(...) 잡아먹어버렸습니다...💦 여러가지 시행착오를 거치다가, 아래 코드를 제출하니 풀..