본문 바로가기
반응형

전체 글308

[프로그래머스/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.
[프로그래머스/Python] 미로 탈출 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] 최소 횟수를 구해야 하므로 BFS로 Start지점에서 Lebber까지의 최소 횟수를 구하고, Lebber에서 Exit까지 다시 BFS로 최소 횟수를 구하면 되는 문제다. 즉, BFS를 두 번 써서 해결하면 된다. ​ [요약] 1. Start지점을 찾고 Lebber 까지 걸리는 이동 횟수를 계산한다. 2. Lebber까지 이동이 가능하다면 Lebber부터 Exit까지 이동횟수를 계산한다. 3. 두 이동횟수를 더한 값을 리턴한다. HTML 삽입 미리보기할 수 없는 소스 dx = [0,0,1,-1] dy = [1,-1,0,0] defaultMap=[] defaultMap2=[] lenX=0 lenY=0 lebberX=-1 .. 2024. 1. 6.
[프로그래머스/Python] 연속 펄스 부분 수열의 합 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 문제를 보면서 연속된 펄스 수열의 합 중 최대를 구하는 문제이므로 부분 합으로 풀 수 있겠다는 생각이 들었다. 주어진 sequence의 길이만큼의 펄스 수열을 곱한 뒤, 첫번째 원소 부터 마지막 원소까지 순차적으로 더해서 리스트에 저장했다. 그 후 리스트에 저장된 값 중 최솟값과 최대값을 구해서 maxValue - minValue를 계산했다. maxValue-minValue가 정답인 이유는 쉽게 생각할 수 있다. (이때 maxValue는 양수, minValue는 음수라 가정) 예를 들어 0 < a < b 일 때, [0, a] 구간의 합이 최소이고 [0,b] 구간의 합이 최대라면 [0, b] 구간 합의 입장에서는 구간 합이 음수.. 2024. 1. 6.
[프로그래머스/C++] 사라지는 발판 HTML 삽입 미리보기할 수 없는 소스 [문제 설명] ​ 밟고 지나가면 사라지는 발판이 있다. A 플레이어와 B 플레이어가 번갈아 가면서 게임을 하고, 각자 최선의 플레이를 한다. 만약 A가 무조건 이기게 된다면 B는 최대한 발판을 오래 밟아야 하고, A 는 최대한 게임을 빨리 끝내도록 플레이 한다. B가 무조건 이기게 되는 경우도 마찬가지로 B는 최대한 빨리 게임을 끝내고 A는 최대한 발판을 오래 밟으면 된다. 이 때, 게임이 진행되는 횟수를 구하면 되는 문제다. HTML 삽입 미리보기할 수 없는 소스 [풀이] 이 문제는 제한사항이 작기 때문에, 시간을 크게 고려하지 않아도 되는 문제다. 중요한 점은 항상 두 플레이어가 최선의 수를 둔다는 점인데, 어떤 플레이어가 이길지 모르기 때문에 조건을 잘 설정하.. 2024. 1. 6.
[프로그래머스/Python] 요격 시스템 HTML 삽입 미리보기할 수 없는 소스 [문제 설명] ​ A나라가 B나라를 침공했다. 요격 시스템이 있지만 비용이 있어서 요격 횟수를 최소로 해야하기 때문에 미사일의 요격을 최소로 하는 횟수를 구하는 문제다. 이때 상대방의 미사일이 날아오는 구간을 알 수 있기 때문에 요격 시스템으로 상대방의 미사일의 구간사이에 요격을 하면 요격에 성공한 것으로 간주한다. HTML 삽입 미리보기할 수 없는 소스 [풀이] 먼저 미사일들의 s 값을 기준으로 정렬을 했다. (이전에 요격에 성공한 미사일의 구간과 이번에 요격할 미사일의 구간이 겹치는지를 확인하기 위해서) ​ s를 기준으로 정렬을 했기 때문에 현재 구간의 s부분이 이전 구간의 e보다 크거나 같은지 비교한다. 크거나 같을 경우 요격할 수 있는 구간을 벗어났기 때문에.. 2024. 1. 5.
[프로그래머스/Python] 상담원 인원 HTML 삽입 미리보기할 수 없는 소스 [문제 설명] 멘토 n명이 있으며, 상담 유형은 k개가 있다. 이때 상담 유형 당 최소 한명의 멘토가 배치되어야 하며, 상담이 진행되는 동안에는 다른 인원은 상담을 받을 수 없다. 이때, 모든 인원의 상담 대기시간의 합의 최소를 구하는 문제다. ​ - 만약 참가자의 상담 유형을 담당하는 멘토가 모두 상담 중이라면, 자신의 차례가 올 때까지 기다린다. 참가자가 기다린 시간은 참가자가 상담 요청했을 때부터 멘토와 상담을 시작할 때까지의 시간이다. HTML 삽입 미리보기할 수 없는 소스 제한사항을 보면 reqs의 길이가 300개 밖에 되지 않는다. 게다가 상담원의 최대 인원은 20명, 상담 유형은 5개이므로 완전 탐색으로 문제를 풀어도 시간안에 계산이 되겠다는 생각이 들.. 2024. 1. 5.
[프로그래머스/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.
[프로그래머스/Python] 정수 삼각형 HTML 삽입 미리보기할 수 없는 소스 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾는 문제다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능하다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 숫자의 합의 가장 큰 경우를 return하는 문제다. HTML 삽입 미리보기할 수 없는 소스 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. HTML 삽입 미리보기할 수 없는 소스 triangle result [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 HTML 삽입 미리보기할 수 없는 소스 .. 2024. 1. 5.
[SWEA/Python] 17643번 - 로봇 HTML 삽입 미리보기할 수 없는 소스 [문제] 2차원 평면의 원점에서 로봇이 움직이기 시작하는데 특정 좌표(x,y)에 있을 가능성이 있는지 구하는 문제다. 특징은 로봇은 상하좌우 4방향으로 이동할 수 있고 t초마다 3^t 만큼 고른 방향으로 이동한다. ​ HTML 삽입 미리보기할 수 없는 소스 처음에는 DFS처럼 완전 탐색을 해서 풀려고 했지만 시간 초과가 떴다. 그래서 어떻게 다른 방법으로 풀 수 있을까 생각해봤다. $$\frac{3^t}{2}>\sum_{n=0}^{t-1} 3n\quad (t\neq 0)$$​ 그러던 중 위의 식이 항상 성립하는 것을 찾았는데, 쉽게 생각하면 a라는 수에 1/3을 계속 곱한 등비수열은 a/2에 수렴한다는게 떠올랐다. 그렇기 때문에 t=n일 때, t=(0 ~ n-1)까.. 2024. 1. 5.
[SWEA/C++] 2112. [모의 SW 역량테스트] 보호 필름Box에 담기 문제 풀기 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] 셀들은 특성 A와 B를 가지고 있으며 보호 필름의 성능은 셀들의 특성이 어떻게 배치되느냐에 따라 달라진다 셀의 특성이 같은 막이 한 열에 연속으로 K개 존재해야 보호 필름의 성능테스트를 통과하며 모든 열이 성능테스트를 통과해야 한다. 약품은 막 별로 투입할 수 있으며(행), 투입하는 막의 모든 셀들은 하나의 특성으로 변경된다. 성능테스트를 통과하기 위해 최소 약품 투입횟수는 몇인지 구하는 문제다. HTML 삽입 미리보기할 수 없는 소스 [풀이] 각 행마다 약품을 주입 하지 않기, A약품을 주입, B약품을 주입 3가지 경우로 경우의 수를 나눴다. 그리고 모든 행의 경우가 정해지면 성능테스트를 통해 보호 성능검사를 통과 여부를 확인하고 통과한다면 약품 주.. 2024. 1. 5.
[SWEA/Python] 16606 - 동전 색 찾기 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] n종류의 동전이 있을 때, 동전의 모양은 완전 똑같고 색이 달라서 n종류의 동전을 구분하기 위해 얼마를 요청해야 하는지 구하는 문제다. HTML 삽입 미리보기할 수 없는 소스 [풀이] 서로 다른 동전은 서로 배수관계를 갖고 있다. 만약 V_i와 V_(i+1)이 2배 차이라면 V_i원의 동전의 2배가 되는 돈을 요청 하게 되면 은행은 V_(i+1)원 동전 하나를 주게 된다. 그러므로 V_i원의 동전의 색을 확인하려면 요구하는 돈 X는 V_i HTML 삽입 미리보기할 수 없는 소스 def fx(dic): # n=배수 a=0 ans=[] # 각 배수마다 몇 회차가 필요한지 저장할 리스트 for i in dic.keys(): # dic의 key는 i배수 관계.. 2024. 1. 5.
[SWEA/Python] 5250 - 최소비용 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] 출발지에서 도착지까지의 높이가 2차원으로 주어진다. 상하좌우로만 이동 할 수 있으며, 이동시 비용은 1, 만약 이동한 곳이 더 높은 지역이라면 높이의 차이 만큼 비용이 증가한다. HTML 삽입 미리보기할 수 없는 소스 입력으로 받은 값에서 가중치를 2차원 리스트에 저장했고, 가중치를 저장할 2차원 리스트를 큰 값으로 초기화했다. 그리고 for 문을 돌려서 N*N의 좌표 중 방문하지 않은 지점 중 가중치가 가장 작은 지점을 탐색하면 시간초과가 났기 때문에, 방문하지 않은 지점이면서 가중치는 초기값이 아닌 좌표를 now_lst에 저장해 탐색했다. 그리고 그중에서 가중치의 값이 가장 작은 지점이 선택되면 now_lst에서 제거하고 방문 표시를 한 다음 그 .. 2024. 1. 5.
반응형

티스토리툴바