본문 바로가기
반응형

C++245

[프로그래머스/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 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 두 용액의 합이 0에 가까운 경우를 구하는 문제다.만약 0에 가장 가까운 경우가 여러개라면 아무 경우나 출력하면 된다. 단순히 2중 for문으로 문제를 풀면 O(n^2)의 시간복잡도가 걸린다. 하지만 이 문제는 정렬을 하면 O(nLogn)의 시간복잡도로 문제를 풀 수 있게 된다. 오름차순으로 정렬을 한 다음 양쪽 끝에서 탐색을 시작한다. 이후 양쪽의 용액의 합이 0보다 작다면 왼쪽에 있는 용액을 오른쪽으로 이동시키면 된다. 정렬 돼 있기 때문에 왼쪽의 용액과 오른쪽 끝에 있는 용액을 더한 값이 0보다 작다면,.. 2024. 4. 30.
[프로그래머스/C++] 택배 배달과 수거하기 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 가장 짧은 이동거리를 구하는 문제다. 여기서 중요한 점은 어차피 배달을 하거나 수거를 할 때 가장 먼 집을 들리게 된다는 점이다. 이때, 최소한의 거리를 이동하기 위해서는 가장 먼 거리에 있는 택배와 수거해야하는 택배를 먼저 수거해야 다시 먼 거리를 이동하지 않는다는 점이다. 아래 그림을 참고하면 이해가 쉽다. 어차피 먼 거리에 있는 택배를 가져오기 위해서 들려야 하므로 이동했을 때 먼 거리에 있는 택배를 먼저 가져오는게 무조건 최소 거리를 이동하는 방법이 된다. 그리고 이동할 때 가장 먼 거리에 있는 택배부.. 2024. 4. 29.
[프로그래머스/C++] 카카오프렌즈 컬러링북 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 DFS나 BFS로 연결된 영역을 탐색하고, 그 크기를 계산하면 쉽게 풀 수 있는 문제다. 문제에서 구해야하는 값이 영역의 개수, 그리고 영역 중 가장 크기가 큰 영역이다. 그렇기 때문에 영역을 만나면 그 영역의 수를 세고 방문했다는 표시를 한다.(다시 탐색을 하지 않도록 표시를 해야한다) 연결된 부분 즉, 모든 영역을 탐색했다면 영역의 개수를 1 추가하고 최대영역의 크기와 비교한다. 만약 이번에 탐색한 영역의 크기가 이전에 저장된 가장 큰 영역의 크기보다 크다면 값을 갱신하면 된다. 마지막으로 구한 영역의 수.. 2024. 4. 28.
[프로그래머스/C++] 가짜 해밀토니안 (월간 코드 챌린지 시즌1) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 가짜 해밀토니안 경로를 만들 때, 어떻게 경로가 형성되는지 잘 파악해야 풀 수 있는 문제다. 문제에서 알려주는 가짜 해밀토니안 경로를 한번 분석해보자위 그림에서 같은 그래프지만 2번 노드에서 어디로 가는지에 따라 만들 수 있는 가짜 해밀토니안 경로가 달라진다. 4번으로 가게 되면, 더 이상 2번 경로로는 돌아오지 못한다.대신 2번 분기점에서 다른 곳으로 빠지지 않고 다시 1번까지 돌아가면 4번 5번을 거쳐 해밀토니안 경로를 만들 수 있다. 만들어진 해밀토니안 경로를 보면 특정 노드와 연결된 노드는 최대 3개가.. 2024. 4. 24.
[백준/C++] 운동 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 도시에서 시작해 다시 돌아오는 사이클이 있는지 확인하고 있다면, 그 중 가장 비용이 적은 사이클을 출력하는 문제다. 사이클을 찾기 위해서는 결국 st 에서 st로 돌아오는 최소비용을 구해야 한다. 문제는 시작점이 하나만 주어진게 아니라 모든 도시가 시작점이 될 수 있다는 점이다. 그러므로 결국 모든 도시에 대해서 시작점으로 돌아오는지 탐색을 해야한다. 처음에는 priority queue를 사용한 다익스트라 알고리즘으로 풀려고 했으나, N개의 점에 대해 다익스트라 연산을 하면 시간복잡도가 O(V*Elog(V))가 된다. [(E < V*2) 이므로 log(V)로 표현 가능] 그러면 O(V^3log(V.. 2024. 4. 23.
[백준/C++] 플로이드 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 정점에서 다른 정점으로 갈 수 있는 최단거리를 구하는 문제다. 모든 정점의 경우를 구해야하기 때문에 플로이드 워셜 알고리즘으로 문제를 풀면 O(N^3)의 시간복잡도로 문제를 해결할 수 있다. 문제를 풀기전에 플로이드 워셜 알고리즘을 간단하게 정리하면, 정점 i에서 j로 가는 비용과 정점 i -> k -> j로 가는 비용을 비교해 최단 거리를 갱신하는 과정이다. 위의 과정을 3중 for문을 이용하면 모든 정점에서 다른 정점으로 가는 최소비용을 구할 수 있다. 여기서 중요한 점은 경유지 k가 for문의 가장 상위에 있어야 한다. 왜 가장 상위에 있어야 하는지 설명하기 전에, 지나갈 수 있는 경유지의 .. 2024. 4. 21.
[백준/C++] 램프 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 열의 램프들을 반전 시키는 방법을 K번 실시했을 때, 모든 행의 램프가 켜진 경우가 가장 많은 수를 구해야 한다. 이 문제에서는 램프가 가장 많이 켜진 경우를 찾기 위해 모든 경우를 탐색해봐야 하는데 이때, 모든 경우를 찾기 위한 기준을 잘 정해야 한다. 특정 열의 램프들을 끄거나 키는 것을 기준으로 잡게 되면 2^n의 시간복잡도가 나타나고 중복이 발생하게 된다. 잘 생각해보면 반대로 특정 행의 램프들을 전부 키도록 한 다음 그때, 몇 행의 램프가 켜져있는지 비교하는 방법으로 쉽게 문제를 풀 수 있다. (왜냐하면 같은 열에 있는 램프들은 전부 불이 반전되는 것에 연결되어 있다. 그렇기 때문에 한 .. 2024. 4. 21.
[프로그래머스/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++] Pho Restaurant HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 두 가지 요리만 하는 식당에 n개의 테이블이 있고, n개의 테이블당 i명의 사람이 요리를 시킨다. 이때, 같은 테이블은 같은 요리를 주문하도록 만드려면 사람을 몇 번 이동해야하는지 계산하는 문제다. 문제 자체는 크게 어렵지 않다. 테이블 당 1번 메뉴와 2번 메뉴를 주문한 사람의 수를 파악하고, 그 중에서 메뉴의 수가 더 적은 사람을 다른 테이블로 이동시키면 된다. 여기서 하나의 예외 상황이 발생하는데, 만약 모든 테이블이 1번 메뉴를 많이 시키고 2번 메뉴를 적게 시키는 경우다. (또는 모든 테이블이 2번 메뉴를 많이 시키고 1번 메뉴를 적게 시키는 경우) 이 경우 최소값인 수만 다른 테이블로 이동하.. 2024. 4. 19.
[백준/C++] 타임머신 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 음의 간선이 있기 때문에, Dijikstra알고리즘으로 문제를 풀 수 없다. 음의 사이클이 존재하는지 찾는 알고리즘에는 벨만 포드 알고리즘이 있기 때문에 벨만 포드 알고리즘을 이용해 문제를 풀었다. 벨만 포드 알고리즘에서 음의 사이클이 존재하는지 판단하는 방법은 다음과 같다. N개의 정점이 있을 때, 임의의 정점 A에 도달하기 위해 거쳐야되는 정점의 개수는 총 N-1개다. 그렇기 때문에 음의 사이클이 없다면 임의의 정점에서 다른 정점으로 도달하는 최소비용을 구하는 과정을 N-1번 하면 출발 정점에서 모든 정점에 도달하는 최단경로가 계산이 된다. 이 때, 음의 사이클이 있다면 한번 더 최단경로를 계산했을.. 2024. 4. 18.
[프로그래머스/C++] 두 큐 합 같게 만들기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 여러 방법으로 풀 수 있는 문제다. 누적합을 이용해 푸는 방법, 문제 그대로 Queue를 이용해 푸는 방법, index를 이용해 Queue가 pop되는 것 처럼 푸는 방법 등 다양한 방법이 존재한다. 이 중에서 나는 Index를 이용해 풀었다. 먼저 이 문제에서 중요한 점은 Queue에서 뺀 원소는 다른 Queue에 들어간다는 것이다. 즉, 그림으로 생각하면 아래와 같이 Queue를 표현할 수 있다. 여기서 Queue2의 원소가 Queue1으로 삽입된다면, 위 그림과 같이 파란 색 부분의 합이 Queue1에 들어가게 된다. 이렇게 연속적인 수들의 합이 되기 때문에 누적합이나, 단순히 Index를 이용해.. 2024. 4. 18.
[백준/C++] 미확인 도착지 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 시작점 st에서 도착점 ed로 가는 최단 경로에 임의의 두 점 (m, n)을 잇는 경로가 포함되어 있는지 계산하는 문제다. 문제를 해결하는 방법은 여러 방법이 있다. 1. Dijikstra 알고리즘으로 두 점 m, n을 잇는 경로를 포함하는지 체크한다. 2. Dijikstra 알고리즘으로 최단경로와 [st -> m -> n -> ed, st -> n -> m -> ed]의 최단 경로의 길이가 같은지 비교하는 방법이 있다. 이 중에서 1번 방법으로 코드를 구현해 문제를 풀었다. Dijikstra 알고리즘과 동일하게 코드를 구현하지만 m, n을 잇는 경로를 포함하는지 체크할 배열을 하나 만든다. 이후.. 2024. 4. 17.
반응형

티스토리툴바