본문 바로가기

Algorithm/프로그래머스131

[프로그래머스/C++] [PCCP 기출문제] 3번 / 충돌위험 찾기 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 생각보다 구현이 까다로웠던 문제다.특정 위치에서 로봇들이 서로 충돌하는지 파악하고 그 지점의 수를 더하면 되는 문제다. 다양한 방법이 있겠지만, 기본적으로 로봇이 움직이는 규칙이 있기 때문에 row 위치가 다르면 row방향으로 움직이고 그다음에 column방향이 다르면 column방향으로 이동하는 움직임을 한다. 그러므로 이를 이용해 특정시간에 로봇들의 위치를 파악하면 어느 위치에서 겹치는지 파악할 수 있다. 처음에는 각 r * c * 시간 으로 3차원 vector를 만들어 저장하려고 했다. 하지만, 이렇게 .. 2024. 10. 4.

[프로그래머스/C++] [PCCP 기출문제] 4번 / 수식 복원하기 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 크게 어렵지 않지만, 구현이 생각보다 빡센 문제였다. 주어진 수식들 중에 수식의 결과를 알고 있다면, 그 수식을 이용해 N진법이 가능한지 판단하고, 만약 결과를 모른다면 후보군에 두면 된다. N진법이 가능한지 판단하는 방법은 간단하다. 먼저 2~9진법의 수로만 수식이 이루어지므로, A + B = C라는 수식에서 A, B, C를 각각 N진법의 수가 가능한지 판단한다.만약 A, B, C 수가 전부 N진법이 가능하다면, A + B라는 값이 C라는 식과 일치하는지 판단한다. 이렇게 비교해서 만약 A+B=C라면 이 .. 2024. 9. 11.

[프로그래머스/C++] 의상 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 먼저 옷의 종류를 map을 이용해 분류를 했다는 가정하에 풀이를 소개하겠다.(이름이 같은 옷은 없으므로, 특정 의상의 수만 파악하면 문제를 풀 수 있기 때문이다.) 약 3가지 방법을 소개하는데, 가장 효율이 좋은 방법은 마지막 방법이다.그러므로 효율적인 풀이가 필요하다면 마지막 풀이를 보는 것을 추천한다. 1. 단순 재귀 처음 문제를 봤을 때, 풀이가 생각이 날듯 말듯 했다. 뭔가 경우의 수를 잘 빼면 해결 될 것 같았는데, 다른 방법이 빠르게 생각이 나지 않아서 먼저 재귀로 문제를 해결했다. 하지만, 재귀로 문제를 풀.. 2024. 6. 7.

[프로그래머스/Python] 주식가격 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 주식의 가격이 떨어지면 몇 초 뒤에 가격이 떨어졌는지를 기록해 return하는 문제다.만약 가격이 떨어지지 않았다면, 끝났을 시간을 고려해 return 하면 된다. 2중 for문으로 비교하면 O(n^2)의 시간복잡도를 갖기 때문에 시간 초과가 걸리게 될 것이다.그러므로 다른 방법으로 풀어야 하는데, stack 구조를 이용하면 쉽게 풀 수 있다. 항상 stack의 맨 위에 어떤 주식 가격이 가장 높은 시간을 둔다.만약 stack의 맨 위에 있는 주식보다 가격이 낮다면, 가격이 떨어지는 순간이므로 시간을 계산해 .. 2024. 5. 19.

[프로그래머스/C++] 올바른 괄호 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 stack을 활용해도 되지만 단순히 개수를 세도 쉽게 풀 수 있는 문제다. '('의 괄호가 나오면 괄호가 시작했다는 count를 1 증가시키고 ')' 괄호가 나오면 괄호가 끝났다는 의미에서 count를 1 감소시킨다.이때, count가 0보다 작은 값이 되면, 이는 올바른 괄호가 아니라는 의미이므로 false를 return 하면 된다. 그리고 모든 string의 탐색이 끝난 후에 count가 0이 아니라면 '('의 괄호가 ')' 괄호의 개수보다 많다는 의미이므로 false를 return 하면 된다. 만약 두 .. 2024. 5. 18.

[프로그래머스/C++] 숫자 블록 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 규칙에 따라 블록을 채우면 되는 문제다. 규칙을 잘 보면 k번째 블록이 임의의 수 n으로 나누어지는지 판단하면 되는 문제기 때문에 k번째 블록의 약수를 구하는 문제로 볼 수 있다. 여기서 k번째 블록의 약수를 구하기 위해서 1~k까지 계산할 필요가 없다. 왜냐하면 k번째 블록의 약수를 k = a * b로 표현할 수 있는데, 이 때 a 그러므로 임의의 두 수를 곱해서 k를 만드는 약수를 구하기 위해서는 1~sqrt(k)까지만 계산하면 된다.(sqrt(k)~k사이에 있는 약수는 1~sqrt(k)와 곱해서 k를 만.. 2024. 5. 6.

[프로그래머스/C++] 교점에 별 만들기 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 정수로 이루어진 교점에 별을 찍는 문제다. 먼저 교점을 찾는 방법은 쉽다.연립 방정식을 풀듯이 x의 계수를 일치시켜 y값을 구하고, y의 계수를 일치시켜 x값을 구하면 된다. 여기서 두 계수를 일치시키는 방법은 곱셈으로 해결했다.(곱셈을 사용하므로 변수형을 long long 으로 해주어야 한다.) 1번 함수의 x계수를 2번 함수의 x, y계수와 d값에 곱한다.2번 함수의 x계수를 1번 함수의 x, y계수와 d값에 곱한다. 이후 두 식을 빼주면 x항은 사라지고 y계수와 d값만 남게 된다. 여기서 y항이나 x항.. 2024. 5. 4.

[프로그래머스/C++] 양궁대회 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때 어떤 것을 기준으로 탐색을 해야할지 고민을 했다. 만약 특정 점수에 a개의 화살을 맞추는 경우의 수를 구했다면 a!과 같은 형태의 시간복잡도가 나오게 된다. 하지만 반대로 각 점수판에서 특정 캐릭터가 이기는 경우의 수로 계산을 하면 [이긴다, 진다] 두 경우로 나오기 때문에 2^n의 시간 복잡도로 빠르게 문제를 해결 할 수 있게 된다. 그러므로 10개의 점수에 대해 라이언이 이기는 경우를 모두 탐색하고, 만약에 라이언이 이 경우대로 이기는게 가능하다면, 점수 차이를 비교했다. + 여기서 라이언이.. 2024. 5. 3.

[프로그래머스/C++] 순위 검색 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 문자열을 잘 나눌줄 알아야 풀 수 있는 문제다. 처음에 문제를 보고 단순히 query가 들어올 때 마다 계산을 할 경우 시간초과가 나게 되어있어서 어떻게 풀까 고민을 많이 했다. 그러다가 한 사람이 점수를 제외하면 가질 수 있는 경우의 수가 3*2*2*2로 24개 이며, 점수가 100000으로 모든 경우의 수를 구해도 2,400,000이 된다는 것에 착안해 문제를 해결했다. 이때 24개의 경우의 수를 표현하기 위해 cpp, java, python 은 각각 0, 8, 16 backend, frontend 는 4.. 2024. 5. 2.

[프로그래머스/C++] 택배 배달과 수거하기 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 가장 짧은 이동거리를 구하는 문제다. 여기서 중요한 점은 어차피 배달을 하거나 수거를 할 때 가장 먼 집을 들리게 된다는 점이다. 이때, 최소한의 거리를 이동하기 위해서는 가장 먼 거리에 있는 택배와 수거해야하는 택배를 먼저 수거해야 다시 먼 거리를 이동하지 않는다는 점이다. 아래 그림을 참고하면 이해가 쉽다. 어차피 먼 거리에 있는 택배를 가져오기 위해서 들려야 하므로 이동했을 때 먼 거리에 있는 택배를 먼저 가져오는게 무조건 최소 거리를 이동하는 방법이 된다. 그리고 이동할 때 가장 먼 거리에 있는 택배부.. 2024. 4. 29.

[프로그래머스/C++] 카카오프렌즈 컬러링북 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 DFS나 BFS로 연결된 영역을 탐색하고, 그 크기를 계산하면 쉽게 풀 수 있는 문제다. 문제에서 구해야하는 값이 영역의 개수, 그리고 영역 중 가장 크기가 큰 영역이다. 그렇기 때문에 영역을 만나면 그 영역의 수를 세고 방문했다는 표시를 한다.(다시 탐색을 하지 않도록 표시를 해야한다) 연결된 부분 즉, 모든 영역을 탐색했다면 영역의 개수를 1 추가하고 최대영역의 크기와 비교한다. 만약 이번에 탐색한 영역의 크기가 이전에 저장된 가장 큰 영역의 크기보다 크다면 값을 갱신하면 된다. 마지막으로 구한 영역의 수.. 2024. 4. 28.

[프로그래머스/C++] 단체사진 찍기 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 풀기 위해서는 시간복잡도를 빨리 눈치채는게 중요했다.처음에 문제를 보고 어떻게 규칙을 찾아서 빠르게 계산을 할 수 있을까? 고민을 했다. 예를 들어 서로 연관된 규칙이 있는 경우에는 하나의 집합으로 포함시켜서 Combination을 계산하면 빠르게 조건을 탐색할 수 있지 않을까 생각했다. 하지만 아무리 생각해도 그 과정을 구현하기에는 힘들 것 같아서 다른 방법을 생각했다. 그러던 와중 8명을 배치하는 경우의 수가 8! 이고, 조건이 100개라는 걸 보고 둘을 곱하면 약 4,000,000 이므로 모든 경우를 직.. 2024. 4. 25.

[프로그래머스/C++] 가짜 해밀토니안 (월간 코드 챌린지 시즌1) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 가짜 해밀토니안 경로를 만들 때, 어떻게 경로가 형성되는지 잘 파악해야 풀 수 있는 문제다. 문제에서 알려주는 가짜 해밀토니안 경로를 한번 분석해보자위 그림에서 같은 그래프지만 2번 노드에서 어디로 가는지에 따라 만들 수 있는 가짜 해밀토니안 경로가 달라진다. 4번으로 가게 되면, 더 이상 2번 경로로는 돌아오지 못한다.대신 2번 분기점에서 다른 곳으로 빠지지 않고 다시 1번까지 돌아가면 4번 5번을 거쳐 해밀토니안 경로를 만들 수 있다. 만들어진 해밀토니안 경로를 보면 특정 노드와 연결된 노드는 최대 3개가.. 2024. 4. 24.

[프로그래머스/C++] 유사 칸토어 비트열 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제에서 나오는 수열은 프랙탈 구조처럼 일정한 규칙을 갖고있는 수열이다. 만약 이 문제에서 1의 개수를 직접 count한다면 최대 개수가 5^20 이기 때문에 시간복잡도에서 문제가 생길 수 있다. 그러므로 규칙을 이용해 1의 개수를 직접 세지 않고, 범위를 이용해 빠르게 풀었다. 일단 l ~ r까지 1의 개수를 구하기 위해 생각해 볼 것은 n = i 인 경우의 모든 1의 개수와 n = i -1 인 경우의 모든 1의 개수는 총 4배 차이가 난다. 왜냐하면 이전 배열의 1이 11011로 바뀌고 0은 00000으로 바뀐다. 그러므로 1의 개수는 이전의 1의 개수에만 영향을 받아 4배씩 증가하는 것이다. 그리고 [l.. 2024. 4. 20.

[프로그래머스/C++] 두 큐 합 같게 만들기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 여러 방법으로 풀 수 있는 문제다. 누적합을 이용해 푸는 방법, 문제 그대로 Queue를 이용해 푸는 방법, index를 이용해 Queue가 pop되는 것 처럼 푸는 방법 등 다양한 방법이 존재한다. 이 중에서 나는 Index를 이용해 풀었다. 먼저 이 문제에서 중요한 점은 Queue에서 뺀 원소는 다른 Queue에 들어간다는 것이다. 즉, 그림으로 생각하면 아래와 같이 Queue를 표현할 수 있다. 여기서 Queue2의 원소가 Queue1으로 삽입된다면, 위 그림과 같이 파란 색 부분의 합이 Queue1에 들어가게 된다. 이렇게 연속적인 수들의 합이 되기 때문에 누적합이나, 단순히 Index를 이용해.. 2024. 4. 18.

이전 1 2 3 4 ··· 9 다음

티스토리툴바