본문 바로가기
반응형

C++245

[프로그래머스/C++] [3차] n진수 게임 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] n진수로 변환만 잘 하면 되는 문제다. 진수 변환은 특정 숫자를 n으로 계속 나눠가면서 나머지를 구하고 처음 구한 나머지를 첫번째 자리, 두번째로 구한 나머지를 두번째 자리로 해 수를 만들어가면된다. 그리고 내가 부를 숫자를 구하기 위해서는 몇 명이 대답했는지 세면서, 내 차례인지 구분하고 만약 내 차례가 됐다면 그때 해당하는 수를 추가하면된다. ​ ​[아이디어 정리] 1. 숫자를 N진수로 변환한다. 2. N진수로 변환한 숫자를 한 자리씩 세면서, 내가 대답해야하는 숫자인지 구한다. 3. 내가 대답할 횟수만큼 숫자가 채워지면 코드를 종료한다. HTML 삽입 미리보기할 수 없는 소스 #include #include #i.. 2024. 1. 6.
[프로그래머스/C++] 전력망을 둘로 나누기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] 문제를 보면 송전탑의 개수가 최대 100개다. 그러므로 송전탑의 구조가 트리 구조이기 때문에, 연결 부위를 한번 씩 끊어서 완전탐색해도 된다. 하지만, 연결된 a와 b를 끊을 때마다 하위 트리를 계산하는 것은 비효율 적이라 생각해서, 1번 송전탑을 부모 노드로 생각하고, 1번 송전탑과 연결된 노드들을 자식으로 해, 모든 하위 노드의 수를 구하도록 했다. ​ ​ [아이디어 정리] 1. 1번 송전탑을 부모 노드로 정한다. ​ 2. 자식노드의 하위 원소 개수들을 합쳐서 부모노드의 하위 원소 개수들을 구한다. ex) 1의 자식노드가 [2,3] 이라고 가정하면, 1의 하위 원소 개수 = [자기 자신+2의 하위 원소 개수 + 3.. 2024. 1. 6.
[프로그래머스/C++] PCCP 기출문제 4번 HTML 삽입 미리보기할 수 없는 소스 [문제 설명] n * m 의 격자판이 주어지고 빨간 수레와, 파란 수레가 주어진다. 그리고 빨간 수레와 파란수레가 각자 목표로 하는 지점까지 도착하는데 걸리는 최소 턴수를 구하는 문제이다. 이때, 빨간수레는 1, 파란수레는 2, 빨간 수레의 도착점은 3, 파란 수레의 도착점은 4이고, 벽은 5로 주어진다. 이동할 위치에 다른 수레가 있으면 이동할 수 없으며, 서로 위치를 교환 할 수도 없다. 또한 이미 지나왔던 길은 다시 갈 수 없다. HTML 삽입 미리보기할 수 없는 소스 [풀이] 먼저 문제를 읽고 어떻게 풀면 좋을지 고민했는데, 다행히 미로의 크기가 크지 않았기 때문에 완전 탐색을 해도 시간이 충분하겠다는 생각이 들었다. 그래서 완전 탐색으로 코드를 짰다. ​ .. 2024. 1. 6.
[프로그래머스/C++] 사라지는 발판 HTML 삽입 미리보기할 수 없는 소스 [문제 설명] ​ 밟고 지나가면 사라지는 발판이 있다. A 플레이어와 B 플레이어가 번갈아 가면서 게임을 하고, 각자 최선의 플레이를 한다. 만약 A가 무조건 이기게 된다면 B는 최대한 발판을 오래 밟아야 하고, A 는 최대한 게임을 빨리 끝내도록 플레이 한다. B가 무조건 이기게 되는 경우도 마찬가지로 B는 최대한 빨리 게임을 끝내고 A는 최대한 발판을 오래 밟으면 된다. 이 때, 게임이 진행되는 횟수를 구하면 되는 문제다. HTML 삽입 미리보기할 수 없는 소스 [풀이] 이 문제는 제한사항이 작기 때문에, 시간을 크게 고려하지 않아도 되는 문제다. 중요한 점은 항상 두 플레이어가 최선의 수를 둔다는 점인데, 어떤 플레이어가 이길지 모르기 때문에 조건을 잘 설정하.. 2024. 1. 6.
[프로그래머스/C++] 매출 하락 최소화 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스  풀이 ">HTML 삽입미리보기할 수 없는 소스 처음에 문제를 읽고 경우를 생각해 봤다. A, B팀의 매출액 하락이 최소가 되기 위해서는 A팀의 최소, B팀의 최소를 더한 값과 A, B팀 둘 다 속한 인원이 워크숍을 들었을 때의 값 중 최솟값을 비교하면 된다.문제는 팀이 2개가 아니라 여러 개일 경우이다.​팀이 여러개일 경우 경우를 나눠서 생각해봤다.A팀부터 A팀의 하위에 있는 팀들이 전부 워크숍을 듣는 경우를 생각해보자.(A팀의 팀원은 B, C, D 3명이 있다고 가정, 팀원들이 다른 팀의 팀장인지는 모름)​[A팀장이 워크숍을 받는 경우]  A팀의 팀장이 워크숍을 받는 경우는 B, C, D 는 워크숍에 참가해도 되고.. 2024. 1. 5.
[프로그래머스/C++] 프로세스 HTML 삽입 미리보기할 수 없는 소스 [문제 설명] 운영체제의 역할 중 하나는 자원을 효율적으로 관리하는 것이다. 이 문제는 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내는 문제다. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼낸다. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣는다. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행한다. 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다. 예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 된다. HTML 삽입 미리보기할 수.. 2024. 1. 5.
[SWEA/C++] 2112. [모의 SW 역량테스트] 보호 필름Box에 담기 문제 풀기 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] 셀들은 특성 A와 B를 가지고 있으며 보호 필름의 성능은 셀들의 특성이 어떻게 배치되느냐에 따라 달라진다 셀의 특성이 같은 막이 한 열에 연속으로 K개 존재해야 보호 필름의 성능테스트를 통과하며 모든 열이 성능테스트를 통과해야 한다. 약품은 막 별로 투입할 수 있으며(행), 투입하는 막의 모든 셀들은 하나의 특성으로 변경된다. 성능테스트를 통과하기 위해 최소 약품 투입횟수는 몇인지 구하는 문제다. HTML 삽입 미리보기할 수 없는 소스 [풀이] 각 행마다 약품을 주입 하지 않기, A약품을 주입, B약품을 주입 3가지 경우로 경우의 수를 나눴다. 그리고 모든 행의 경우가 정해지면 성능테스트를 통해 보호 성능검사를 통과 여부를 확인하고 통과한다면 약품 주.. 2024. 1. 5.
[프로그래머스/C++] 풍선 터트리기 HTML 삽입 미리보기할 수 없는 소스 n개의 풍선이 일렬로 나열되어 있다고 하자. 이 때, 모든 풍선에는 서로 다른 숫자가 써져 있다.다음 규칙에 따라 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터뜨리려고 한다. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터뜨린다. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생기면, 빈 공간이 없도록 풍선들을 중앙으로 밀착 시킨다 여기서 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터뜨리는 행위는 최대 1번만 할 수 있도록 제한 되어있다.즉, 한번이라도 인접한 두 풍선 중 번호가 더 작은 풍선을 터뜨리면 이후에는 번호가 큰 풍선만 터뜨려야 한다. 이 규칙에 따르면 어떤 풍선은 어떤 방법을 쓰더라도 절대 마지막까지 남길 수 없다. 이때, 최후까지 남.. 2024. 1. 5.
[프로그래머스/C++] 경사로의 개수 (2023 현대모비스 알고리즘 경진대회 예선) HTML 삽입 미리보기할 수 없는 소스 문제 설명 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/214290 위와 같이 맵이 주어지면 방문할 수 있는 경사로를 [1, -2, -1, 0, 2, 1, -2, -1, 0, 2]와 같은 형태로 주고, 얼마나 경사로를 반복할지 횟수 k를 알려준다. 한번에 이동할 수 있는 경사로는 상하좌우로만 이동할 수 있으며 이전에 방문한 경사로도 방문 할 수 있다. 이때 위 조건을 만족하는 경로의 수를 전부 구해 1000000007로 나눈 나머지를 return하면 된다. HTML 삽입 미리보기할 수 없는 소스 3 ≤ grid의 길이 = n ≤ 8 3 ≤ grid[i]의 길이 = m ≤ 8 0 ≤ grid[i][j.. 2024. 1. 5.
[백준/C++] 10830번 - 행렬 제곱 HTML 삽입 미리보기할 수 없는 소스 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000) 둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다. HTML 삽입 미리보기할 수 없는 소스 행렬의 곱을 구하기 위해서는 행렬의 성질을 알아야 한다. 일반적으로 행렬의 곱은.. 2024. 1. 4.
[백준/C++] 11401번 - 이항 계수 3 HTML 삽입 미리보기할 수 없는 소스 자연수 N과 정수 K가 주어졌을 때 이항 계수 (N, K)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N) HTML 삽입 미리보기할 수 없는 소스 (N, K)를 1,000,000,007로 나눈 나머지를 출력한다 HTML 삽입 미리보기할 수 없는 소스 이항계수는 nCk로 쉽게 구할 수 있는데, 곱셈간의 나머지를 구하기는 쉽지만 나눗셈이 포함 될 경우 나머지를 계산하기가 어렵기 때문에 페르마의 소정리를 이용해서 풀었다. HTML 삽입 미리보기할 수 없는 소스 $$a^{p-2} \equiv a^{-1} \pmod{p}$$.. 2024. 1. 4.
[백준/C++] 1629번 - 곱셈 HTML 삽입 미리보기할 수 없는 소스 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. HTML 삽입 미리보기할 수 없는 소스 제곱의 횟수가 매우 많기 때문에 이를 구하기 위해서는 제곱하는 횟수 B를 B/2 로 나눈 뒤, B/2번 제곱했을 경우의 값을 구하고 B/2를 곱하는 방법으로 문제를 풀었다. B/2번 곱하는 것은 재귀로 만들었다. 그리고 .. 2024. 1. 4.
[백준/C++] 25682번 - 체스판 다시 칠하기 2 HTML 삽입 미리보기할 수 없는 소스 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 K×K 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 K×K 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시.. 2024. 1. 4.
[백준/C++] 1780번 - 종이의 개수 HTML 삽입 미리보기할 수 없는 소스 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다. .. 2024. 1. 4.
[백준/C++] 2630번 - 색종이 만들기 HTML 삽입 미리보기할 수 없는 소스 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 .. 2024. 1. 4.
반응형

티스토리툴바