본문 바로가기

Algorithm/PS

 (60)
[1일 1알고] 광고 삽입 https://school.programmers.co.kr/learn/courses/30/lessons/72414 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr이번 문제는 구현 문제입니다. 전체 영상 중 광고를 어느 타이밍에 틀지가 문제입니다. 일단 가장 많은 사람이 시청하도록 해야하기 때문에 어느 특정 시점부터 광고를 트는 시간 동안 사람들이 누적 몇초를 시청했는지를 알아야합니다. 그렇다면 동영상 재생시간 동안 매초 몇명이 시청중인지를 계산해야합니다.다만 매번 계산할 수는 없기 때문에 슬라이딩 윈도우 형식으로 계산하면 될 것 같습니다. 그리고 매초 몇명이 보고있는지를 확인하기 위해서는 주어진 logs를 통해서..
[1일 1알고] 여행경로 https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 공항의 수가 최대 10000개이기 때문에 최악의 경우 애매한 측면이 있지만, 그래도 기본적으로 ICN에서 시작한다는 점과, 처음 만난 경로이후 탐색할 필요가 없다는점, 반드시 경로는 존재한다는 점을 통해 일단 dfs 백트래킹을 통해 해결해보았습니다. #include #include #include #include using namespace std;int N;bool isCompleted = false;vector result;void dfs(map>>..
[1일 1알고] 미로 탈출 명령어 https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr일반적인 그리디 문제입니다.k만큼의 이동을 통해서 start에서 end로 도달해야합니다. 중간에 장애물도 없기 때문에 거리 계산은 좌표를 통한 맨하탄 거리를 그대로 사용하면 됩니다.이동이 가능한 경우 중 사전 순 d, l, r, u의 우선순위로 이동해야하기 때문에 이를 고려하면 됩니다. k가 2500이하이며 n, m또한 그에 맞게 50이하이기 때문에 매번 이동을 계산하더라도 전혀 부담이 없을 것입니다. using namespace std;// nxm 미로..
[1일 1알고] 자물쇠와 열쇠 https://school.programmers.co.kr/learn/challenges?order=recent&page=1&search=%EC%9E%90%EB%AC%BC%EC%87%A0 코딩테스트 연습 | 프로그래머스 스쿨개발자 취업의 필수 관문 코딩테스트를 철저하게 연습하고 대비할 수 있는 문제를 총망라! 프로그래머스에서 선발한 문제로 유형을 파악하고 실력을 업그레이드해 보세요!school.programmers.co.kr 이번 문제는 조건을 통해 풀이를 생각할 수 있는 문제였습니다. 자물쇠와 열쇠가 딱 맞게 결합되는 지점이 존재한다면 true아니라면 false를 return하는 문제입니다. 이 때 어떻게 접근해야할지 여러 생각이 들었지만 key = MxM (3굳이 복잡하게 생각할 필요없이 그냥 브루트..
[1일 1알고] 인사고 https://school.programmers.co.kr/learn/courses/30/lessons/152995 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 오늘은 정렬에 관련된 문제입니다. 근무 태도, 동료 평가를 어떤 사원과 비교해 둘 다 저조한 사원이 있다면 인센티브를 받을 수 없습니다.그리고 문제의 목표는 완호(scores[i])의 석차를 아는 것입니다. 따라서 인센티브를 받을 수 없는 사원을 거른 후 완호의 석차를 별개로 다시 구해야할 것입니다.(완호가 걸러지는 경우는 -1) 사원을 필터링하기 위해서는 일단 하나의 조건을 통해 내림차순으로 정렬 후 나머지 조건은 반대로 오름차순으로 정렬해 최댓값만..
[1일 1알고] 표 편집 https://school.programmers.co.kr/learn/courses/30/lessons/81303 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이런 문제는 간단하게 가라로 풀려고 하면 꼭 수렁에 빠지게 되네요 보면 기본적으로 제거한 행(노드)을 저장하기 위한 Stack이 필요할 것입니다.(Z의 규칙이 마지막에 삭제된 노드 복구이기 때문에) 그리고 삭제한 노드를 복구하기 위해서는 단순히 삭제되었다고 bool등으로 체크만 한 뒤 탐색 시 이를 지나치는 방법과아예 연결 리스트로 만들어 구현하는 방법이 있습니다. 저는 제시된 예시의 계산 횟수가 커보여서 연결리스트를 만들었습니다.struct Node{..
[1일 1알고] 모두 0으로 만들기 https://school.programmers.co.kr/learn/courses/30/lessons/76503 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr중요한 것은 주어진 노드들이 트리로서 이어져있다는 것입니다.기본적으로는 주어진 수 a의 합이 0이 아니라면 애초에 성립할 수 없다는 뜻입니다. 따라서 이 경우를 예외처리하고 어제 풀었던 등대문제 처럼 tree DP처럼 풀면 되겠네요https://basaeng.tistory.com/165 [1일 1알고] 2차원 동전 뒤집기https://school.programmers.co.kr/learn/courses/30/lessons/131703 프로그래머스SW개발자..
[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..

티스토리툴바