코딩 해파리

안녕하세요! 오늘은 백준 2457번 "공주님의 정원" 문제를 해결한 과정과 그 과정에서의 사고 흐름을 공유하려고 합니다. 이 문제는 그리디 알고리즘을 활용하여 해결할 수 있는 흥미로운 문제입니다.문제 분석:이 문제는 공듀님의 정원에 피어 있는 꽃들의 개화 기간이 주어졌을 때, 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 하기 위해 선택해야 하는 최소한의 꽃의 개수를 구하는 것입니다.접근 방법:1. 꽃의 개화 기간을 시작일과 종료일로 정렬합니다.2. 현재 날짜부터 시작하여 가장 늦게 지는 꽃을 선택합니다.3. 선택한 꽃의 종료일을 새로운 시작일로 설정하고 과정을 반복합니다.4. 모든 기간을 커버할 때까지 이 과정을 반복합니다. 코드 구현 :#include #include #incl..

안녕하세요! 백준 27113번 잠입 문제에 대한 분석과 해결 방법을 소개해드리겠습니다. 이 문제는 그리디 알고리즘을 활용하여 해결할 수 있는 재미있는 문제입니다. 이번 문제의 경우에는 solved에서 제공하는 난이도 기준으로는 골드 5에 해당합니다! 근데 사실... 고려할 사항도 너무 많고, 예외처리가 빡쌔기 때문에... 체감 난이도는 훨씬 높다고 생각합니다!문제 분석:이 문제는 N개의 행과 M개의 열로 이루어진 격자 모양의 적군의 기지에서 최 상병이 안전하게 탈출할 수 있는지를 판단하는 문제입니다. 각 행에는 센서가 있어 최 상병의 이동을 방해할 수 있습니다. 우리의 목표는 최 상병이 첫 번째 행의 가장 왼쪽 칸에서 시작하여 마지막 행의 아무 칸으로 이동할 수 있는지 확인하는 것입니다.그리디 알고리즘 ..

오늘은 백준 22862번 "가장 긴 짝수 연속한 부분 수열 (large)" 문제를 해결한 방법과 생각의 흐름을 공유하고자 합니다! 이 문제의 경우에는 solved에서 제공하는 난이도 기준 골드 5에 위치하고 있습니다! 난이도로 보면... 크게 어렵진 않을 것 같은데 고려할 사항들이 조금은 있습니다!문제 분석:이 문제는 주어진 수열에서 최대 K개의 홀수를 제거하여 얻을 수 있는 가장 긴 짝수 연속 부분 수열의 길이를 찾는 것입니다. 수열의 길이가 최대 1,000,000이므로 효율적인 알고리즘이 필요합니다.접근 방법:이 문제를 해결하기 위해 수열의 길이를 고려한다면, O(N)에 해당하는 시간복잡도로 풀어야 한다고 생각했기 때문에, 투 포인터(Two Pointers) 기법을 사용했습니다.구현 과정:1. 입력 ..

오늘의 문제는 백준 21736 "헌내기는 친구가 필요해"입니다! 굉장히 공감이 가는 내용을 가지고 있는 문제입니다...ㅎㅡㅎ...; 이 문제는 solved 기준 실버 2에 위치한 문제로 BFS나 DFS로 푸는 문제들 중에선 쉬운 문제에 속합니다!! https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 사실 이 문제가 BFS와 DFS로 풀리는 문제를 많이 접해보시지 않으신 분이라면, 왜 이게 쉬운 문제에 속하는 지 이해가 안 가실 수 있습..

오늘 가져온 문제는 백준 1717번 집합의 표현입니다! 이 문제는 현재 solved 기준 골드 5에 위치하고 있습니다 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 이 문제를 푸는 데에 가장 필요한 개념은 분리집합$($disjoint_set$)$입니다. 분리 집합은 다들 Union-Find라고도 부르기도 하는데요! 개념 자체가 어렵지 않기 때문에 가볍게 한 번 언급하고 넘어가자면! "문제 상황 속에서 어떠..

오늘의 문제는 14940 쉬운 최단거리 문제입니다! 현재 solved 기준 실버 1에 위치한 문제네요! https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 이 문제는 보자마자 느낌이 오시겠지만, 너비 우선 탐색$($BFS$)$ 문제입니다! 나쁘게 말하면 전형적이고 진부하지만, 좋게 말하면 BFS의 굉장히 정석적이고 처음 너비 우선 탐색에 대해 배우고 익히기 좋은 문제라고 생각합니다! 일단 이 문제는 2차..

오늘의 포스팅은 1450 냅색문제 입니다! solved에서 제공하는 난이도 기준 골드 1에 위치하고 있습니다!https://www.acmicpc.net/problem/1450 1450번: 냅색문제첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다.www.acmicpc.net  이번 문제도 저번의 포스팅처럼 중간에서 만나기 라는 개념을 또 사용합니다!이번 문제는 저번에 풀었던 것보다 조금은 더 이해하기 힘들게 응용하기 때문에, 저번 포스팅을 보지 않으셨거나 중간에서 만나기라는 개념을 처음 접해 보셨다면 아래의 링크로 한 번 확인하고 오시는 것을 추천드립니다!!htt..

오늘 풀어볼 문제는 백준 7453번 합이 0인 네 정수 입니다! https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 이 문제를 효율적으로 풀기 위해 기본적으로 깔고 가야 하는 알고리즘? 최적화 방식? 은 Meet In The Middle = 중간에서 만나기 입니다! 번역하니까 열라 하찮은 느낌이네요...ㅋㅋㅋㅋ 굉장히 매력적인 방법이니 한 번 집중해서 뜯어보시길 권유드립니다! 일단 이름에 걸맞게 구현 방식이 굉장히 직관적입니다....

내 첫 포스팅은 23082번 균형 삼진법 문제이다. https://www.acmicpc.net/problem/23082 23082번: 균형 삼진법 균형 삼진법은 밑이 \(3\)이고, 자릿수가 \(0\), \(1\), \(-1\)로 이루어진 기수법이다. 이를 이용해 별도의 부호를 사용하지 않고서도 모든 정수를 유일한 방법으로 나타낼 수 있다. 십진수를 입력 받 www.acmicpc.net 이 문제를 선택한 이유는... 뭐... 구글에 검색해서 잘 나오지도 않고... 인하대 학우들이나 오픈 콘테스트 나가는 사람들이 언젠가 IUPC를 준비할 때 도움이 되지 않을까 하는 마음에 작성해 본다! 균형 삼진법 문제의 첫 접근 자체가 어지럽다. 이게 뭔 말인가... 싶기도 하고, 구현 자체를 쌩으로 하나하나 해야 하는..