Algorithm115 [프로그래머스][C++] 코딩 테스트 공부 (249) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 사실 맨 처음 문제를 읽고 생각이 난 풀이는, 다익스트라를 활용한 최소거리를 찾는 풀이였다. 다만 다익스트라를 적용시키려면 그레프를 먼저 만들어야 하는데, 이부분이 만만치 않다 생각되었다. 두번째로 든 생각은 DP를.. Algorithm/프로그래머스 2022. 9. 27. [프로그래머스][C++] 등산코스 정하기 (248) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 그레프 문제인건 확실한데, 처음 보면 익숙하면서 조금 어색한 느낌도 들고... 어떠한 방식으로 풀어야할지 한눈에 보이지는 않았다. 이 문제는 생각할점이 3가지나 존재합니다. 1) 알고리즘 2) 편도와 왕복 3) 시간.. Algorithm/프로그래머스 2022. 9. 26. [프로그래머스][C++] 파괴되지 않은 건물 (247) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이 문제를 처음 보자마자 제한 조건 때문에 brute force 방식은 절대 불가능 하다 생각했다. 또한 이전까지의 경험에 의해서 2차원 누적합을 응용해야 될것 같다는 생각까지는 했다... 문제는... 2차원 누적합을.. Algorithm/프로그래머스 2022. 9. 22. [백준][C++] 스타트와 링크 (246) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이번 문제는 백트래킹 알고리즘의 대표적인 문제라 생각되어 정리해본다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 vec1, vec2 각각에 모든 사람의 번호를 집어넣어서 가능한 모든 케이스를 구하되 애당초 불가능 경우 바로 return 하면 됩니다. 이게 무슨 의미일까요? 불.. Algorithm/백준 2022. 9. 22. [프로그래머스][C++] 주차 요금 계산 (245) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://school.programmers.co.kr/learn/courses/30/lessons/92341 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 2개의 Map을 사용하게 된다. unordered_map과 map을 사용하게 되는데, map같은 경우 차량 번호의 오름차순으로 결과를 출력해야하기 때문에 사용하였다. 그 외에 주차 시작시간을 저장하는 경우 정렬을.. Algorithm/프로그래머스 2022. 9. 21. [프로그래머스][C++] 순위 검색 (244) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://school.programmers.co.kr/learn/courses/30/lessons/72412 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아니 이번 문제 이거 level 2 맞아? level 3 느낌인데?..... 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 매번 조건을 검색하기에는 최대 50000 * 100000 = 50억 이기 때문에, 제한시간안에 해결할수가 없다... 따라서 입력값들을 .. Algorithm/프로그래머스 2022. 9. 19. [프로그래머스][C++] 후보키 (243) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://school.programmers.co.kr/learn/courses/30/lessons/42890 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 맨 처음 문제를 보고 든 생각은 조합을 구해야 한다는 점이었다. C++에서는 Python과 같이 조합을 구해주는 라이브러리가 없기 때문에 직접 구현해야 한다. C++에서 조합을 구하는 방식은 크게 2가지이다. 1.. Algorithm/프로그래머스 2022. 9. 15. [백준][C++] 6593번: 상범 빌딩 <242> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 1. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 너무나 단순한 BFS 탐색 문제이다. 우선 우리는 좌표와 몇분이 걸리는지를 저장하기 위해 Position이라는 Class를 다음과 같이 정의하자. class Position { public: int x, y, z; i.. Algorithm/백준 2022. 9. 5. [백준][C++] 7569번: 토마토 <241> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번문제는 Queue를 얼마나 잘 활용하는지가 핵심이다. 보통 BFS문제는 (!Q.size)동안 반복문을 돌게 된다. 문제는 이렇게 한번에 다 BFS탐색을 돌면, 하루안에 모든 과일이 익은것 처럼 코드가 작동한다. 우리는 하루마다 이미 익어있는 토마토에 인접한 토마토만 익도록 만들어야 한다. 따라서 BFS도 하루 단위로 동작해야 한다. 그래야 총 몇일이 소모됬는지 확인할 수 있다. 이를 위해서는 Queue의 사이즈를 이용해야 한다. 문제의 input을 보자. 5 3 1 0 -1 0 0 0 -1 -1 0 1 1 0 0 0.. Algorithm/백준 2022. 9. 1. [백준][C++] 2410번: 2의 멱수의 합 <240> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 동전1 문제와 매우 유사한 문제입니다. 우선 DP[i] : i를 2의 멱수로 표편하는 방식의 수 라고 정의합시다. DP[i]를 구하는 방법은 DP[i-1] + DP[i-2] + DP[i-4] + DP[i-8] + ... + DP[0] 로 구할수 있습니다. 예를 들어 문제의 예시인 7을 구한다 생각해봅시다. 2^0(1) 일때의 모든 DP 배열을 채우면 다음과 같다 1로만 각 수를 만들수 있는 경우는 전부 1가지 이다. i = 1 2 3 4 5 6 7 DP[i] 1 1 1 1 1 1 1 2^1(2) 일때의 모든.. Algorithm/백준 2022. 8. 18. [백준][C++] 2302번: 극장 좌석 <239> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 HTML 삽입 미리보기할 수 없는 소스 1) 일반석 1자리만 있는 경우 당연히 해당 1자리만 앉으면 끝이니 1가지 경우이다. DP[1] = 1 이 된다. 2) 일반석 2자리만 있는 경우 이 경우는 2가지 경우가 가능한데, 다음과 같이 가능하다. [A][B] [B][A].. Algorithm/백준 2022. 8. 16. [백준][C++] 15486번: 퇴사 2 <238> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 N의 범위가 150만 이라서 완전탐색 이런 방식으로는 절대 해결할수 없다 생각하였다. 그리고 문제 자체에서 DP smell이 엄청나게 느껴졌다. 바로 동적계획법을 적용시켜보려 노력하였다... Algorithm/백준 2022. 8. 9. 이전 1 2 3 4 5 6 ··· 10 다음
