본문 바로가기

프로그래머스128

[프로그래머스/C++] 최고의 집합 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 처음에 보고 쉽다고 생각했지만, 푸는 방법에 대한 이유를 찾다보니 라그랑주 승수법을 알고 있어야 하는 문제였다. 라그랑주 승수법이란 조건부 함수의 최대화 또는 최소화 문제에 대한 해석수법의 일종인데, 이것을 지금 다루기는 어려우니 생략하려고 한다. 쉽게 말하면 두 식(제약조건, 목적함수)의 gradiant 방향이 같은 곳이 정답이 되는 부분인데, 쉽게 말하면 접하는 부분을 의미한다. 이 때, 방향은 같지만 크기가 다를 수 있기 때문에 라그랑주 승수를 이용해 크기를 같게 해준다. [라그랑주 승수법 참고] https://blog.naver.com/waterforall/222730998200 [최적화(optimization).. 2024. 1. 6.

[프로그래머스/C++] 4단 고음 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] 처음에 1부터 시작해 최종 음높이 n이 되는지 탐색하도록 코드를 짰는데, 경우의 수가 너무 많아 시간 초과가 걸렸다. 그래서 역으로 n부터 시작해 역으로 1까지 돌아오도록 코드를 짰다. 이 경우 코드의 패턴은 n을 3으로 나눌 수 있는 경우와 없는 경우로 나뉘는데 n을 3으로 나눌 수 있는 경우 n/3 의 경우를 재귀로 탐색하면서 *의 개수를 1 늘려준다. n에서 1을 뺀 다음 +의 개수를 1 늘려준다. 위와 같이 탐색해 나가면 된다. [주의] +의 개수가 늘어난 만큼 *의 개수가 늘어나는데 [사용한 +의 개수/2 - 사용한 *의 개수] 가 앞으로 추가되어야 할 *의 개수다. 그러므로 추가해야할 *의 개수 .. 2024. 1. 6.

[프로그래머스/C++] 양과 늑대 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] 처음에 모든 경우를 구하면 시간이 많이 오래 걸릴 것 같아서 어떻게 해야할까 생각했는데 제한사항에 info의 길이가 17밖에 되지 않는 것을 보고 충분히 완전탐색해도 되겠다는 생각이 들었다. 첫 노드부터 시작해 갈 수 있는 노드를 구해서 그 노드를 방문하도록 재귀적으로 코드를 짰다. 만약 특정 노드를 방문했는데, 양의 수와 늑대의 수가 같아지면 그 때는 더 이상 재귀를 하지 않도록 했다. [아이디어 정리] 방문할 수 있는 노드들을 vector로 정리해둔다. 새 노드를 방문 할 때마다 다음에 갈 수 있는 노드들을 새로 갱신한다. 만약 새 노드를 방문했을 때, 늑대의 수가 양의 수와 같아지면 그 루트에서는 양이 .. 2024. 1. 6.

[프로그래머스/C++] 가장 먼 노드 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] 노드간에 길이 연결 되어 있는지 vector로 표현하고, BFS로 탐색해 나가면 되는 문제다. BFS로 탐색을 하므로 처음 방문했을 때가 최단 거리인 사실을 생각하면, 단순히 BFS로 탐색하면서 이전 노드를 방문할 때 걸린 거리 + 1 을 노드에 저장하면 되는 문제다. [아이디어 정리] Vector를 이용해 노드간에 연결이 되어있는지 표현한다. 1번 노드부터 BFS로 방문하며 새로 방문한 노드에는 이전 노드를 방문하는데 걸린 거리 +1을 저장한다. 모든 노드를 탐색한 후에는 가장 먼 노드의 거리가 얼마인지 구한 다음 가장 먼 노드의 개수를 return한다. HTML 삽입 미리보기할 수 없는 소스 #include .. 2024. 1. 6.

[프로그래머스/C++] 이중우선순위큐 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 테스트 케이스의 예시가 적어서 그런지 vector에 숫자를 삽입 할 때, 이분 탐색으로 들어갈 위치만 잘 정해주니 쉽게 풀리는 문제였다. [아이디어 정리] 1. vector 에 숫자를 삽입 할 때, 이분 탐색으로 삽입 될 위치를 계산한다. 2. 삭제 명령이 뜰 경우 최대 최소에 따라 vector의 맨 앞 숫자를 삭제하거나 맨 뒤의 숫자를 삭제한다. HTML 삽입 미리보기할 수 없는 소스 #include #include using namespace std; vector answer; void InsertNum(string num) { int st, ed,mid; int reNum=stoi(num); st = 0; ed =.. 2024. 1. 6.

[프로그래머스/C++] 길 찾기 게임 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] 문제를 보면 전위 순회와 후위 순회를 나타내는 것은 어렵지 않다. 하지만, 노드의 정보를 바탕으로 그래프를 그리는게 약간 힘들다. 조건을 보면 모든 노드는 다른 x값을 갖는다. 이를 이용해 x값의 좌표에 몇번 째 노드인지 값을 저장하는 array를 하나 만들어 결과 값을 출력 할 때 사용한다. 또한 트리는 이진트리의 형태이며, 같은 레벨에 있는 좌표는 전부 같은 y 값을 갖는다. 그러므로 y값을 기준으로 노드들을 정리한 다음 레벨을 점차 낮추며 그래프를 그리면 쉽게 이진트리를 그릴 수 있다는 사실을 알 수 있다. [아이디어 정리] 1. 이진트리의 자식 관계를 그리기 위해 y축을 기준으로 Map을 만들어 노드.. 2024. 1. 6.

[프로그래머스/C++] 뒤에 있는 큰 수 찾기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 숫자를 스택에 쌓으면서 비교하면 되는 문제다. 내 숫자보다 큰 숫자가 뒤에 오는지를 구하면 되기 때문에 스택의 맨 위에 있는 수보다 작은 숫자가 오면 스택의 위에 쌓고 큰 수가 오면 스택의 맨 위에 있는 숫자가 뒷 큰 수를 찾았기 때문에 뒷 큰수를 기록하고 스택에서 제거한다. 그리고 새로 맨 위에 오는 숫자가 현재 숫자 보다 큰 지 비교하는 과정을 반복한다. [아이디어 정리] 1. 스택의 맨 위에 숫자가 현재 숫자보다 큰 지 비교하고, 작으면 스택의 맨 위에 쌓는다. 2. 만약 클 경우 스택의 맨 위의 숫자를 제거하고 뒷 큰수를 기록한 다음 다시 스택의 맨 위 숫자와 비교한다. 3. 위 과정을 반복한다. HTML 삽입 미리.. 2024. 1. 6.

[프로그래머스/C++] 연속된 부분 수열의 합 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] 처음에는 길이가 1000인 줄 알고 for 문을 두번 돌려서 빠르게 풀려고 했다. 근데 알고보니 길이가 1,000,000이여서 투포인터를 이용해 문제를 풀었다. 먼저 주어진 수열 대신 0번 idx에는 0, 1번 idx에는 기존 수열의 0~0 idx까지의 합 2번 idx에는 기존 수열의 0~1 idx까지의 합을 저장하는 새로운 수열 newSeq를 만들었다. 이후 ed를 1, st를 0으로 시작해 newSeq[ed]-newSeq[st]의 값이 k보다 작으면 ed의 값을 1 늘리고, newSeq[ed]-newSeq[st]의 값이 k보다 크면 st의 값을 1늘렸다. 만약 newSeq[ed]-newSeq[st]의 값이 k와.. 2024. 1. 6.

[프로그래머스/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.

이전 1 ··· 5 6 7 8 9 다음

티스토리툴바