전체 글 (403) 썸네일형 리스트형 [프로그래머스 LV3] 불량 사용자 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/64064?language=cpp# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 순열 조합 백트래킹 문제라고 파악하는 것은 어렵지 않다.그러나 문제의 핵심은 "어떤 사용자를 조합할 것인가?" 이 문장이 핵심이다. ABCD , ABC, AB , BCD 사용자가 존재하고 밴 사용자로 **C, *** 가 있다고 예를 들어보자. 사용자들을 밴의 개수인 2개씩 조합하면 ABC, ABABC, BCDABCD, ABC 이런식으로 조합할 수 있다. 그리고 사용자로 모두 조합시키고 밴 사용자와 1대1 대응인지 체크하.. [백준 22234번] 가희와 은행 (C++) https://www.acmicpc.net/problem/22234 큐를 사용하여 시뮬레이션 하는 문제가 이전에 코딩테스트에 출제되어서 이번에 도장깨기를 하고자 풀어보았다. 큐 문제를 풀 때는 가장 중요한 것이 보통 시뮬레이션이 동반되기 때문에 문제를 정확히 파악하는 것이 중요하다.그리고 그림으로 그려가면서 어떤 지점에서 큐를 사용할지 가상으로 시뮬레이션해보는 것이 매우 중요한 것 같다. 이 문제를 시뮬레이션 해보면 위 시뮬레이션을 보자. 1, 2에서 새로운 아이디가 들어왔는데 1이 아직 안 끝났으므로 맨 뒤로 들어간 모습이다. 이것을 의사코드로 생각해보면 if 현재 고객의 상담이 끝나면: 이후 온 사람들이 있는지 검사하고 이전에 온 사람들이 있으면 큐에 삽입 그렇다면 이제 온 사람들을 관리할 큐가 하.. [프로그래머스LV2] 땅따먹기 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/12913 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 처음엔 백트래킹으로 구현했는데 시간초과가 났다. 4^10만이기 때문에 말도안되는 시도였다.그래서 DP를 생각했고 백트래킹에 접목했는데 틀렸다. 그리고 좀 더 유심히 문제를 보니 열은 반드시 4로 주어지는 문제였다. 그래서 Bottom-Up 방식 DP를 생각해냈다. 결국 i번 행에서는 i - 1행의 3가지 경우 중 하나만 올 수 있고 그 중 최댓값을 구하면 되기 때문이다. 그래서 다음과 같은 점화식이 생긴다. DP[i][j] = value[i][.. [프로그래머스LV3] 등굣길 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/42898?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이 문제를 처음 풀었던 2023년 5월에도 bfs로 풀면 되지 않을까 생각했고 무려 2024년 10월에도 같은 생각을 해서 틀렸다는 점에서 반성이 필요하다. 동적계획법을 보고 다익스트라여서 dp라고 한건가 생각했는데 아니었다. 100 * 100 이고 아무리 다익스트라를 사용한다 해도 결국은 2^100*100 이 되어버린다. 그래서 이 문제는 그냥 dp로 중복을 제거하여야한다. dp에 어떤 정보를 담아야할까? 난 처음에 이.. [백준] 1, 2, 3 더하기 4 (C++) https://www.acmicpc.net/problem/15989 DP는 언제나 너무 어렵다... 내가 바보인것도 있지만 DP 배열을 1차원으로 둘지 2차원으로 둘지 파악하는 것도 매우 까다롭다. 요즘 코딩테스트에서는 DP가 많이나오진 않는 것 같은데 그래도 연습이 필요하다. 이 문제는 1, 2, 3으로 N을 만들 수 있는지 물어보는 전형적인 DP문제이다. 당연히 1차원 배열로 풀어보려 했는데 잘 안되서 구글링을 통해 찾아봤다. 상상치도 못한 2차원 배열이 나왔다. dp[i][1] = 1로 만들 수 있는 경우의 수dp[i][2] = 2를 포함하여 만들 수 있는 경우의 수dp[i][3] = 3을 포함하여 만들 수 있는 경우의 수 이렇게 모아놓는 방식이었다. 이렇게 하는 이유는 1 + 1 + 2, 1 +.. [프로그래머스LV3] 숫자 게임 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/12987 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr A와 B를 정렬하고 A와 맞으면 둘 다 인덱스 ++ 아니면 B만 ++ 해보는 방식으로 풀면 된다. 문제 유형은 Greedy로 생각된다. #include #include #include using namespace std;int solution(vector A, vector B) { int answer = 0; sort(A.begin(), A.end()); sort(B.begin(), B.end()); for.. [백준] 9017번 크로스 컨트리(C++) https://www.acmicpc.net/problem/9017 처음 봤을 땐 되게 쉬운 문제라고 생각했는데 틀렸습니다가 떠서 질문 게시판을 보니 각 팀의 참가 선수가 여섯보다 작으면 그 팀은 점수 계산에서 제외됨을 주의하라. 이것을 대강 넘어가서 그런 것이었다..!! 그리고 점수가 낮을 수록 순위가 높은 것이었다..!! 문제를 잘 읽고 분석을 철저히 하자. #include#include#includeusing namespace std;int main(){ int T; cin >> T; for(int t = 0; t > N; vector race; map maps; for(int i = 0; i > n; maps[n].. [프로그래머스LV3] 단속카메라(C++) https://school.programmers.co.kr/learn/courses/30/lessons/42884?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 벌써 세번째 푸는데 잘 못푼 나 .. 이런 문제를 풀 때는 케이스를 몇 개 생각해볼 수 있다. 검은색 범위가 원래 있었던 것이고 파란색이 들어온 차의 범위라고 하자. 그리고 빨간색 점이 카메라의 위치라고 하자. 위사진의 케이스들은 모두 새로운 카메라가 필요없다. 첫번째, 두번째 케이스는 원래 있었던 카메라의 위치 = 차가 나가는 지점을 바꿀 필요가 없다. 이미 커버하고 있기 때문이다. 그러나 세번째 케이스의 경우는 기.. 이전 1 2 3 4 5 6 7 ··· 51 다음
