프로그래머스 풀이 (85) 썸네일형 리스트형 프로그래머스 - 등굣길(C++) 처음 봤을 때는 응? 이거완전 BFS인데... 라고 생각했으나 일단 (왜인지는 몰라도) 테케 정확도도 통과하지 못했다. 이후에는 문제 분류인 DP로 풀어나갔다. 그러나 얼추맞는 것 같은데 이상하게 통과가 안되서 알아보니 학교의 위치는 m,n 이었다 ! 이 때문에 테스트 케이스를 어느정도 통과했으나 아직 예외가 존재했고 예외를 찾는데는 얼마안걸렸지만 구현이 좀 걸렸다. 일단 풀이 방법은 다음과 같다. 1. x, y 에서 x가 0이거나 y가 0이면 모두 DP[x][y] 는 1이다. 최소로 갈 수 있는 값이 1개 밖에 없다. 2. DP[x][y] 는 현재 위치의 왼쪽과 위의 합이다. 왜냐면 집이 왼쪽 위에 있기 때문이다. 여기까지가 기본이다. 3. 1번에서 [0,1], [0,2] , [0,3] 중 0,2 가 .. 프로그래머스 - 징검다리 건너기(C++) 문제를 보고 든 생각은 이번에도 구현보다는 효율성 문제겠구나 싶었다. https://school.programmers.co.kr/learn/courses/30/lessons/64062 첫번째 생각 : 한 번씩 돌려보면서 -1 하고 돌이 0이되면 0의 갯수확인 -> 당연히 시간초과다. 돌의 최대가 2억이다. 두번째 생각 : 주어진 배열을 오름차순으로 정렬한다. 그리고 0번부터 n번까지 돌려보며 0의 갯수를 확인한다. 이때 첫번째와 달리 정렬된 0번부터 바로 stones를 0으로 정해서 숫자를샌다. 이러면 시간복잡도가 O(N^2) 이기때문에 정확도테스트에선 통과하지만 효율성 테스트를 한개도 통과할 수 없다. 세번째 생각 : 드디어 이분탐색이 떠올랐다. "어 설마.." 하면서 생각은 났지만 구체적으로 구현방법.. 프로그래머스 - 단속카메라(C++) 탐욕법으로 분류된 문제이지만 사실상 그냥 구현이라고 봐야할 것 같다. 우선 항상 이런 문제를 보면 정렬을 떠올려야한다. 결과는 같지만 차가 들어오는 순서에 따라 연산이 달라지기 때문이다. 먼저 이 문제는 들어오는 첫번째 들어오는 시간을 기준으로 오름차 정렬하고 푸는게 가장 편하다. 1. i번 차의 나가는 지점을 기준으로 정해둔다. 2. i+1번 차가 들어오는 지점이 현재 기준점보다 오른쪽이다. 즉 기준 카메라로 커버할 수 없으면 카메라를 한개 추가하고 현 i+1번 차의 시작점으로 기준을 다시 잡는다. 3. i+1 번 차가 나가는 지점이 기준점보다 왼쪽이거나 같다. 즉 기준 카메라로 커버할 수 있다. 그럼 카메라의 위치를 i+1번이 나가는 지점으로 바꾼다. 왜냐하면 카메라로 많은 차를 커버해야하기 때문이다.. 프로그래머스 - [1차]캐시 LRU가 무엇인지 알아야 풀 수 있는 문제다. 컴퓨터구조, 운영체제, 데이터베이스 등 필수 과목에서 한번씩 나오는 개념인데 가장 사용한 지 오래된 것을 캐시에서 빼내겠다는 뜻이다. 캐시는 매우 유용하지만 너무 커지면 오히려 느려지고 무엇보다 비용이 많이든다. 예를들어, 캐시의 크기가 3이고 캐시에 A B C 순서로 들어왔다고 하자, 그리고 D가 들어왔다. -> 가장 사용한지 오래된(들어온지 오래된) A가 빠지고 B C D 형태가 될 것이다. 그런데 D가 아니라 A가 들어왔다면, 캐시 히트로 캐시에는 변화없다. 그 다음 D가 들어왔다면? -> A는 들어온지 가장 오래되었지만 방금 캐시 히트로 썼기 때문에 사용한지 가장 오래됐고 사용한적 없는 B가 빠진다. 그러므로 A C D 형태가 된다. 이 알고리즘을 작.. 프로그래머스 - 이중우선순위 큐(C++) 요즘 정말 캡스톤 때문에 정신이 나갈 것 같고 학교 수업따라가기도 힘들어서 PS할 시간이없다,,, 먼저 이 문제를 보고 떠올린 키워드는 세개였다. 1. 이름부터 그렇듯 min우선순위 큐 2. max우선순위 큐 3. 덱 그리고 가장 끌렸던 것은 덱이었다. 1. 숫자를 받는다. 2. 숫자를 받다가 명령이 나오면 덱을 정렬하고 pop_front or pop_back한다. 이 방법은 명령시마다 한번씩 sort해줘야하기 때문에 좋은풀이가 아니라고 생각했다. 그러나 테스트케이스가 적어서 통과할 수 있었던 것 같다. #include #include #include #include using namespace std; vector solution(vector operations) { vector answer; dequ.. 프로그래머스 - 베스트앨범(C++) 난 해시 문제를 별로 안좋아하지만 map의 사용법을 익힐 겸 문제를 추천받아 풀어봤다. 이런 생구현 문제는 확실히 먼저 구하는게 뭔지 확실히 해두고 차근차근 풀어가는게 빠르고 좋다. 처음 풀 때 중구난방하게 막 풀다가 결국 내가 내 코드를 못알아봐서 결국 다시 풀었다. 1. 장르별로 뭐가 가장 많이 재생됐고, 그 목록을 벡터로 만듦. 2. 가장 많이 재생된 장르부터 검사하며 고유번호, 재생수 형태로 매핑 3. 매핑한 컨테이너를 정렬. compare 함수 만들기 4. 반복 #include #include #include #include using namespace std; bool comp(pair& a, pair& b) { return a.second > b.second; } bool compare(pa.. 프로그래머스 - 카카오 프렌즈 컬러링북(C++) 기본적인 그래프 탐색 문제이다. 각 좌표에서 그래프 탐색 후 방문체크를 한다. bfs를 해도되지만 각 타일에서 다음 타일과 비교해야하는 부분도 있으니 dfs로 풀이했다. 그러나 bfs로 풀이해도 문제없다. 유사한 문제 - https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net #include using namespace std; int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; int M; int N; int ar.. 프로그래머스 - [3차]자동완성 (C++) Trie 자료구조를 공부하게 된 이유가 바로 이 문제 때문이었다. https://tigerfrom2.tistory.com/74 문자열 관리 자료구조 - 트라이(Trie) 개념/구현 C++로 PS를 공부할 때나 코딩테스트를 볼 때 문자열 문제가 나오면 일단 짜증이난다. 파이썬은 문자열 다루기가 편하다는데 C++는 아무래도 문자열을 다룰때 힘든 면이 많다. 문자열 문제가 나오 tigerfrom2.tistory.com 대표 실습 문제라고도 할 수 있는데 Trie 자료구조에서 변수하나를 추가해줘야한다. 개념에서 알 수 있듯, 트라이 자료구조는 트리의 형태로 go -> gone 순으로 추가한다고 치면 g, o는 두번 방문될 것이고 n, e는 한번 방문될 것이다. 즉, 노드에 따로 방문 횟수를 저장한다. 그렇다면,.. 이전 1 ··· 6 7 8 9 10 11 다음
