본문 바로가기
반응형

Algorithm293

[프로그래머스/C++] 아이템 줍기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] ​ 이 문제는 겹친 사각형으로는 캐릭터가 이동할 수 없다는게 핵심이다. 그래서 겹친 사각형의 경로를 없애주고, 없앤 다음 만들어진 경로를 BFS로 탐색하면 쉽게 풀리는 문제다. BFS로 탐색하는 것은 쉽지만, 어떤 경로를 이동할 수 있는지를 구하는게 생각보다 어려웠다. 처음에는 사각형의 좌표를 기준으로 겹쳐있는지를 보고 겹친 부분을 조건에 따라 삭제하려고 했다. 하지만 코드가 생각보다 길어질 것 같아서, 잘 생각해보니 겹칠 경우는 조건을 잡을 필요없이 겹친 부분을 0으로 없애면 실제로 가능한 경로만 남게 된다는 사실을 알았다. 그래서 하나의 사각형에서 이동이 가능한 경로를 그리고, 그 사각형의 경로 위에 다른 사.. 2024. 1. 11.
[프로그래머스/C++] 섬 연결하기 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] ​ 섬과 섬을 연결하는 다리를 건설해 모든 섬을 이을 때, 최소 비용을 구하는 문제다. 이전에 풀었던 최소 신장 트리 문제와 똑같은 문제다. [SWEA/Python] 5249 - 최소 신장 트리 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] 노드와 간선의 수가 주어지면 이 그래프로 부터 최소 신장트리를 만들고 최소신장트리를 구성하는 간선의 가중치를 모두 더하는 문제다. HTML 삽입 codingjj.tistory.com HTML 삽입 미리보기할 수 없는 소스 [풀이 요약] 섬위 범위가 100이기 때문에, 프림 알고리즘이나 크루스칼 알고리즘에서 사용하는 유니온, 우선순위 큐 등을 사용하지 않고 반복으로도 쉽게 풀릴 것이라 생각했다. [아이디어 정.. 2024. 1. 9.
[프로그래머스/C++] 단속카메라 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] ​ 특정 구간을 지나는 모든 차량이 단속용 카메라를 만다록 하는 문제다. 이전에 풀었던, 요격 시스템이라는 문제와 매우 비슷하다. [프로그래머스/Python] 요격 시스템 HTML 삽입 미리보기할 수 없는 소스 [문제 설명] ​ A나라가 B나라를 침공했다. 요격 시스템이 있지만 비용이 있어서 요격 횟수를 최소로 해야하기 때문에 미사일의 요격을 최소로 하는 횟수를 구 codingjj.tistory.com HTML 삽입 미리보기할 수 없는 소스 이 문제는 greedy 하게 풀 수 있다. 특정 구간을 지나서 무조건 새로 카메라를 달아야 하는 구간이 오면 새로 비교하던 데이터들을 갱신하고, 다시 카메라가 차량들을 단속할 수 있는지 판단하면 된다. 이전에는 시.. 2024. 1. 8.
[프로그래머스/C++] 네트워크 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] ​ 컴퓨터와 컴퓨터가 연결되어 있으면 하나의 네트워크로 본다. 만약 A와 B컴퓨터 B와 C컴퓨터가 연결되어있다면, 하나의 네트워크로 간주한다. 컴퓨터간의 연결이 2차원 vector로 주어지면 컴퓨터들 간의 총 네트워크의 수는 얼마인지 return 하면 되는 문제다. HTML 삽입 미리보기할 수 없는 소스 컴퓨터의 개수가 최대 200개로 크지 않았기 때문에 DFS로 쉽게 풀 수 있다는 생각이 들었다. 그래서 이미 네트워크로 체크했는지 검사하는 isNet이라는 1차원 vector를 이용해 DFS로 문제를 풀었다. 하나의 컴퓨터와 연결된 컴퓨터는 이미 연결된 네트워크인지 체크를 했다고 처리를 하는 것이다. ​ [아이디어 정리] 컴퓨터의 개수만큼 for문을 .. 2024. 1. 7.
[프로그래머스/C++] 자동완성 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] ​ 자동완성 기능을 넣기 위해서 한번이라도 입력된 단어는 자동으로 출력되도록 기능을 구현하기로 했다. 이 때, 앞부분이 같은 단어라면 구분을 위해서 구분이 될 때 까지 단어를 입력해야한다. 만약 goat와 gone이 있다면 구분을 위해 goa와 gon을 입력해 주어야 한다. 그래서 입력해야 할 문자의 수는 6이다. ​ HTML 삽입 미리보기할 수 없는 소스 [풀이] 처음에 보고 trie 알고리즘을 활용하면 쉽게 풀 수 있을 것 같아서 trie 알고리즘을 활용해 풀었다. 그런데 풀고나서 다른 사람들의 풀이를 보니 정렬을 활용해 푼 사람들이 많았다. 게다가 테스트 케이스에서는 더 빨랐다... ㅠㅠ 정렬을 활용한 풀이는 앞이나 뒤에 오는 단어와 비교해서 몇.. 2024. 1. 7.
[프로그래머스/C++] 거스름돈 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 처음에 DP로 풀면 되겠다 생각했다가 단순히 100종류에 100000개면 정렬만 잘 하면 빨리 통과하지 않을까 생각해서 그냥 풀었다. 그랬더니 효율성에서 시간초과가 걸려 다시 DP로 돌아왔다. ​ 2차원 vector를 만들고 n원을 만드는 경우를 재귀로 구하도록 처음에 코드를 짰는데, 효율성 테스트 중 하나를 자꾸 통과하지 못했다. 그래서 1차원 vector로 바꿔서 다시 풀었더니 통과할 수 있었다. ​ 1차원 vector로 푸는 방법은 처음에 동전 하나를 사용해서 만들 수 있는 n보다 작은 모든 거스름 돈의 수를 구한다. 그리고 그 거스름 돈의 자리에 1을 저장한다. 이후 두번째 동전도 사용해 거스름 돈을 주는 수를 구한다... 2024. 1. 7.
[프로그래머스/C++] 셔틀버스 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 특별한 알고리즘 없이 그리디하게 풀 수 있는 문제였다. 먼저 특정 시간에 버스가 오면 그 때, 탈 수 있는지 없는지를 판단한다. ​ 만약 탈 수 있다면 버스가 도착하는 시간에 나와서 타면 된다. ​ 문제는 버스 탑승 인원만큼 서 있을 때가 문제다. 만약 버스 탑승 인원 만큼 서 있다면, 마지막에 버스에 탑승하는 사람보다 1분 빠르게 줄을 서면 된다. (마지막에 줄을 서 있는 인원이 아니라 마지막에 버스에 탑승하는 인원이다.) ​ 요약하면 탑승시간 변수에 버스가 오는 시간을 저장한다. 만약 그 시간에 탑승하는 인원들이 많아 버스의 탑승인원과 같거나 많아지면 마지막에 탑승하는 인원의 탑승시간보다 1분 빨리나오도록 한다. 버스의 운.. 2024. 1. 7.
[프로그래머스/C++] 최적의 행렬 곱셈 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 처음에 행렬이 곱할 수 있는 순서대로 주어지는건지 고민했지만, 순서대로 계산이 가능하도록 주어질 것이라고 보고 문제를 풀었다. 문제를 보면 최악의 경우 200개의 행렬의 모든 순서를 전부 계산해보고 풀기에는 무리가 있어서 DP로 풀기로 했다. ​ A번째에서 C번째 행렬까지의 곱셈연산을 구한다고 하면 (A행렬과 C행렬 사이에 B행렬이 있다고 가정) [A 행렬 ~ B 행렬의 최소 곱셈연산 횟수] + [B 행렬 ~ C 행렬의 최소 곱셈 연산횟수] + [이번 연산 횟수] 값이 최소가 되는 행렬을 찾으면 A 행렬 ~ C 행렬의 최소 곱셈 연산 횟수가 된다. 즉, 이전에 계산한 최소 곱셈연산 횟수가 다음 계산에도 사용되므로 DP로 풀 수.. 2024. 1. 7.
[프로그래머스/C++] 퍼즐 조각 채우기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] 처음에 문제를 보고 빈 공간에 조각을 채워넣어야 하는 줄 알고 어렵다고 생각했는데, 조건에 조각을 넣었을 때, 빈 공간이 생기면 안된다는 조건을 보고 생각보다 쉽겠다고 생각했다. 하지만 막상 해보니 코드가 엄청 길어지고 처음 생각했던 방법과 다르게 풀어서 의외로 오래 걸렸다... 내가 시도한 방법은 조각이 들어갈 수 있는 공간을 탐색하고, 그 공간의 모양을 파악해 90도로 회전해 나올 수 있는 모양들은 전부 같은 모양으로 정했다. 그리고 조각의 모양이 90도로 회전해 나올 수 있는 모양 중 하나라면 채워넣는 식으로 코드를 짰다. 이후 같은 조각인지 비교하는 방법은 다음 그림과 같이 만들었다. 만약 위와 같은 퍼즐의 공.. 2024. 1. 7.
[프로그래머스/C++] 다단계 칫솔 판매 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] 판매한 금액의 10%가 자신을 초대한 사람에게 전달 되므로 초대한 사람이 누구인지 잘 매칭만 되면 해결되는 쉬운 문제다. 등록된 사람이 누구의 추천을 받아서 들어왔는지를 빠르게 찾기 위해 map으로 저장해 시간을 줄이고, 판매한 금액을 정산 할 때마다, 추천을 해준 사람에게 10%씩 금액을 전달하면 된다. [아이디어 요약] 등록되어 있는 사람을 누가 추천했는지 map으로 만든다. 판매한 사람의 금액을 정산하고 10%는 map에 있는 추천인에게 금액을 전달한다. 추천인은 금액을 전달 받으면 다시 자신을 추천한 사람에게 10%의 금액을 정산한다. 10%의 금액이 0이거나, 추천한 사람이 없으면 반복문을 종료하고 다음 금액.. 2024. 1. 7.
[프로그래머스/C++] 불량 사용자 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 이 문제는 중복된 경우의 수를 제거하는게 핵심인 문제다. 먼저 banned_id 와 user_id를 비교해서 ban을 할 수 있는 사용자 목록을 뽑고, ban할 수 있는 경우의 수를 완전 탐색해 풀었다. 이 때, 한번 ban할 수 있는 목록으로 뽑힌 사용자가 다시 뽑힐 수 는 없으므로 이 경우를 제거했고, ban할 수 있는 사용자가 전부 뽑히면 Set에 넣어 중복을 제거 했다. ​ ​ [아이디어 정리] user중 ban할 수 있는 사용자의 목록을 뽑는다.​ ban 할 수 있는 사용자들이 중복되지 않게 뽑고, Set에 넣어 중복을 제거한다.​ 최종적으로 구한 Set의 size를 return 한다. HTML 삽입 미리보기할 수 없.. 2024. 1. 6.
[프로그래머스/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.
반응형

티스토리툴바