본문 바로가기

Problem Solving

 (152)
[프로그래머스/파이썬] 2023 KAKAO BLIND RECRUITMENT 개인정보 수집 유효기간 문제 해석 문제 풀이 문자열 구현이 주된 문제였다. 생각보다 문자열 다루는게 익숙치 않았고 파이썬이 주 언어가 아니다보니 시간이 좀 걸렸던 것 같다. 문자열 다루기에는 파이썬이 참 편리하고 좋은 것 같다. 이 문제의 핵심은 결국 모든 날수를 더해서 오늘 날짜보다 더 작다면 유효기간이 지난 것으로 간주하고 배열에 넣는 것이다. 코 드 def to_days(date): year, month, day = map(int,date.split('.')) return (year - 1) * 12 * 28 + (month - 1) * 28 + day def solution(today, terms, privacies): answer = [] d_day = to_days(today) terms_map = {i.split..
[프로그래머스/파이썬] 2023 카카오 블라인드 리크루팅 표 병합 문제 해석 문제 풀이 merge와 unmerge 부분을 보고 바로 유니온 파인드(분리집합) 문제임을 알게되었다. 그런데 input을 tokenize할 필요가 있는 문자열 문제로 보여 C++이 아닌 파이썬으로 바꿔 풀게 되었다. (C++에 string split을 구현할 수 있지만 구현 방법이 빠르게 떠오르지 않았다.) 단지 이 문제에서는 단순 분리집합 문제와 다르게 고려해야할 사항이 많았는데 MERGE 를 할 경우 같은 셀이면 무시, 둘 중 한 셀만 있을 땐 그 값만 유지, 모두 값이 있을 땐 왼쪽 윗 셀을 따른다. UNMERGE 되면 지정한 위치가 그 값을 가지게 되고 다른 값들은 모두 초기화된다. Input이 (1, 1) 부터 시작된다. (0, 0)으로 생각하면 틀린다. MERGE 할 때 반대쪽 노드..
[백준/C++] 4779번 칸토어 집합 문제 해석 문제 풀이 보자마자 분할 정복인 것은 알았으나 분할정복을 제대로 이해하고 있지 않아서 선으로 문자열을 먼저 만들고 지워나가는 형식으로 구현하려고 했으나 어려워서 헤맸다. (개인적으로 분할정복이 제일 어렵다) 이 문제는 아래와 같은 패턴이다. N == 2는 N == 1을 2번 더하고 사이에 N==1 만큼의 공백이 있고 N==1은 N==0을 2번 더하고 사이에 공백이 N==0 만큼 존재한다. 따라서 이전 것을 그리고 이전 사이즈만큼 공백을 그리고 이전 것을 그려주는 형식으로 분할하면 되는 문제이다. 정복할 때는 N == 0인 초기상태일 때 ' - ' 를 그린다. 코드 #include using namespace std; int N ; void Div_Con(int n) { int str_sz = ..
[백준/C++] 19539번 사과나무 풀이 처음에는 결국 모든 숫자를 만들 수 있으니 전체 합이 3의 배수인지만 확인하면 되는거 아닌가? 했다. 1 1 1 3 3 이면 반례가 생기는 것을 알게 되었다.. 3의 배수는 만들 수 있는 숫자니 일단 모든 숫자는 3으로 나눈 나머지로 바꾼 후 1의 갯수와 2의 갯수를 비교하면 되지 않나? 했다. 10 1 1이 반례가 되었다. 뭔가 2가 실마리가 되는 것 같은데 20분이 지나서 힌트를 참조했다. 괜히 참조한 것 같다. 조금만 더 고민해볼 걸 결국 3의 배수이면서 2의 갯수가 물뿌리는 토탈 횟수보다 많으면 된다. reason 전체 수의 합이 3의 배수이면 물뿌리개를 동시에 사용해서 며칠이 걸리는지 체크 가능하다. (즉 배수가 아니면 물뿌리개를 동시에 사용해서 만들 수 없는 숫자이다.) 2만큼 성장하는 물뿌리..
[백준/C++/KOI] 2470번 두 용액 이분탐색 풀이 input은 최대 10억 최소 -10억의 정수값으로 10만개 이하가 들어온다. int로 처리할 수 있으며 투포인터로 처리하기 전에 이분탐색으로 풀었는데 투포인터 풀이가 조금 더 쉬운 것 같다. 이분탐색은 푸는데 하루종일 걸렸는데 투포인터는 30분 내로 풀어졌다. (같은 문제라서 그럴지도 모른다.) 투포인터 풀이 링크: https://readble-ko.tistory.com/147 #include using namespace std ; class Best { public: int first ; int second ; int val ; Best(){ first = 0, second = 0, val = 2e31 - 2; } }; int N ; Best best = Best() ; int main() { ios..
[백준/C++/KOI] 2467번 용액 투포인터 풀이 input은 최대 10억 최소 -10억의 정수값으로 10만개 이하가 들어온다. int로 처리할 수 있으며 투포인터로 처리하기 전에 이분탐색으로 풀었는데 투 포인터가 더 쉬운 것 같다. 생각해보면 정렬한 후에 각 용액에 대한 페어를 찾아내면서 최소값을 찾는다는 그리디함이 보장되는 문제였다. 이분탐색 풀이 링크: https://readble-ko.tistory.com/148 #include using namespace std ; int N ; class Best //합이 가장 적은 경우를 best 클래스에 저장했다. { public: int val = 2e9 ; //최대 + 최대 case를 생각해 20억으로 맞춰주었다. int first = 0 ; int second = 0 ; }; int main() { ..
[백준/C++] 19238번 스타트 택시 풀이 문제만 읽어보면 쉬운 문제 같은데 생각보다 함정이 많은 문제였다. [함정1]. BFS로 위쪽, 왼쪽, 오른쪽, 아래쪽 순으로 돌리면 가장 행이 적은 순, 가장 열이 적은 순이 보장되지 않는다. (예시: 왼왼왼, 오오위의 경우 후자가 우선순위이지만 왼왼왼을 먼저 찾게 된다) [함정2]. 어떤 사람의 도착점이 다른 사람의 출발점이 될 수 있다. 혹은 택시의 시작점이 사람이 있는 지점이 될 수 있다. 이 외에도 함정이 좀 있었던 것 같은데 나는 이 2가지를 처리하고 보니 AC를 받게되었다. 코드를 짤 때 로직을 아래와 같이 짰다. BFS_1(현재위치) - 조건에 따라 택시에서 가장 가까운 곳을 찾아서 좌표를 리턴해준다. BFS_2(현재위치, 승객위치) - 현재위치에서 승객 위치까지의 거리를 BFS로 찾아서 넘..
[백준/C++] 17138번 캐슬 디펜스 풀이 최대 N과 M이 15이고 궁수는 3명이니 브루트포스로 실행할 경우 최대 225C3이다. 이는 대략 180만번이고 각각에 궁수가 15턴을 실행할 경우를 계산하면 180만 * 15 * 3으로 8천만번이고 1억번 이내이므로 브루트포스로 풀어낼 수 있는 문제이다. 먼저 궁수 3명의 위치를 선정하기 위해 SetArcher 함수로 모두 구해주었다.이후 Simulate 함수를 통해 15턴동안 어떤 궁수가 어디 위치한 적을 쐈는지를 체크하고 죽인 적은 제거해주었다.이 때 매 턴이 지나가는 것을 15x15 게임맵을 아래로 한칸씩 내리고 위에 0으로만 이뤄진 배열을 추가해주었다. 매 턴마다 PlayOnTurn 함수를 실행시켰으며 이 함수에서 BFS로 가장 가까이 있으면서 가장 왼쪽에 있는 적을 우선적으로 찾아주었다. 만약..

티스토리툴바