본문 바로가기

Algorithm

 (72)
[1일 1알고] 등대 https://school.programmers.co.kr/learn/courses/30/lessons/133500 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr1일 1알고리즘이라고 해놓고 빼놓는 날이 생기네요다시 힘내보겠습니다 연관된 간선을 모두 활성화하는 가장 적은 노드의 수를 골라야합니다. 처음에는 문제를 잘못이해해서 간선이 아니라 노드를 활성화해야한다고 착각해서 오래걸렸네요. 예를 들어 1-2-3-4-5-6 과 같이 연결되어있다면 최소 값이 2가 아니라 문제에서는 3이라는 의미입니다.문제는 Tree DP를 이용하는 문제입니다.Tree DP의 경우 leaf node부터 시작해 결과를 끌어모으는 형태의 dp..
[1일 1알고] 2차원 동전 뒤집기 https://school.programmers.co.kr/learn/courses/30/lessons/131703 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr구현 문제입니다. 어떻게 뒤집어야하는지는 하나의 열 혹은 행에 대한 상태를 결정하면 나머지는 뒤따라옵니다. 하나의 열을 결정하면 target에 맞추기 위해 행의 flip상태가 모두 결정나고 반대로도 마찬가지입니다. 따라서 첫번째 열을 뒤집은 경우, 그대로 둔 경우로 나눠 이후 구현해나가면 됩니다. 문제는 XOR를 적극적으로 사용할 것을 권장하는 것 처럼 보입니다.flip을 하기 위한 가장 간단한 방법은 0과 1로 이루어진 기존 값에 XOR1을 하는 것이..
[1일 1알고] 디스크 컨트롤러 https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr디스크 컨트롤러는 우선순위를 사용하는 문제입니다. 이런 문제는 어떻게 풀지는 머리속에 생각이 나지만 막상 구현을 하려니까 헷갈리는 문제가있네요// 한 번에 하나의 작업만 수행 가능한 하드디스크 // 우선순위 디스크 컨트롤러를 사용함// [번호, 시각, 소요시간]// 1.소요시간(짧은것) 2.요청시각(빠른것) 3.작업번호(작은것) 순으로 우선순위가 높음// 작업 중간에 스위칭 되지는 않음// 작업을 마치는 시간과 새로운 작업이 추가되는 시점이 같다면 작업 ..
[알고리즘 알아보기] 이분 탐색 https://basaeng.tistory.com/162 [1일 1알고] 징검다리 건너기https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr차례대로 건너가며 디딤돌의 내basaeng.tistory.com 오늘 문제를 풀어보니 꼭 이분 탐색(이진탐색)은 헷갈리는 경우가 많더라고요아무래도 제대로 알아본적이 없어서 그런 느낌입니다. 이번 기회에 간단하게라도 알아보겠습니다.이분 탐색이분 탐색은 말그대로 전체를 두 부분으로 나눠가며 탐색하는 알고리즘입니다. "0부터 100가지의 숫자 중 내가 생각하는 숫자를 맞춰..
[1일 1알고] 징검다리 건너기 https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr차례대로 건너가며 디딤돌의 내구도를 감소시킵니다.이 때 k를 넘는 칸을 한번에 뛸 수 없기 때문에 이를 처음으로 만족하는 값을 찾는 것이 문제입니다. 이번 문제는 조건을 보면 배열의 크기가 20만 이하이며 원소가 2억이하이기 때문에 매번 시뮬레이션을 실시한다면 시간을 충족하지 못할 것임을 바로 알 수 있습니다. 그렇기 때문에 1부터 시작해서 감소시켜가며 계산할 수는 없습니다. 다행히도 원소의 크기는 최대 2억이지만 배열의 크기가 20만이기 때문에 이분탐색..
[1일 1알고] 보행자 천국 https://school.programmers.co.kr/learn/courses/30/lessons/1832 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr특정 조건을 지키며 이동가능한 모든 경우의 수를 계산하는 문제입니다. 1인 경우 일반적인 장애물입니다.2일 때가 중요한데 2는 회전을 할 수 없도록 하는 표지판입니다.따라서 r, c위치정보 + 방향에 대한 정보가 필요한 것을 알 수 있습니다. 또한 문제에서 MOD를 하라고 하는 것으로 보아 경우의 수가 매우 커질 수 있음도 알 수 있습니다.저는 그래서 일단 city_map과 별개로 이동하는 가짓수를 체크하는 dist_map을 별도로 만들었습니다. 이는 3..
[1일 1알고] 연속 펄스 부분 수열의 합 https://school.programmers.co.kr/learn/courses/30/lessons/161988 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제가 Lv3이지만 실제적으로 어려운 문제는 아닙니다. 펄스 수열은 [1, -1, 1... 꼴과 [-1, 1, -1... 꼴로 나누어지는데, 그렇다면 그냥 이 두가지 경우에 대해 계산한 후 최종결과를 내면 됩니다. 기본적으로 넘어오는 sequence에 펄스수열을 미리 계산한 뒤 (미리 계산하지 않아도 되겠네요)이에 대해 가질 수 있는 부분 수열의 최댓값을 구하는 것이 답입니다.using namespace std;long long solution(vec..
[1일 1알고] 블록 이동하기 https://school.programmers.co.kr/learn/courses/30/lessons/60063 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr소위 말하자면 빡구현 문제입니다. 기본적으로 2차원 NxN 배열 내에서 벽을 피해가는 문제이며 최단거리로 이동해야하기 때문에 BFS계열 탐색을 사용해야합니다. 이 문제의 특징으로는 이동하는 주체인 로봇이 2x1 크기라는 것이고, 회전이 가능하다는 점입니다. 따라서 이동의 처리는 상하좌우 4방 + 회전의 경우를 고려하며 가로와 세로를 별도로 생각해야합니다.가로와 세로에 대한 거리 측정을 3차원 배열로 묶어서 처리할 수도 있겠지만 저는 가로, 세로를 각각 담..

티스토리툴바