코딩관계론

문제 이해하기 부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 계산하는 문제였다. 단 모든 예산을 지원해야 한다.문제 해결 방법 설명하기1. 경우의 수 계산하기  문제를 풀기 위해서 먼저 경우의 수를 계산해야 하는데 부서별 지원여부를 두고 경우의 수를 계산하면 2(해당 부서의 지원 여부 O or x)^100(부서의 개수)가 나오게 되고, 제한시간안에 문제를 해결할 수 없다. 따라서 완전 탐색은 사용할 수 없게 된다. 최대한 많은 부서에 예산을 지원하면 되기 때문에 예산 요청이 작은 순으로 지원하면 된다. 따라서 그리디하게 지원하면 문제를 해결할 수 있다. 코드def solution(d, budget): ..

문제 이해하기 등굣길 경로의 경우의 수를 구하는 문제이다. 좌표 (1,1)인 집에서 부터 (m,n)인 학교까지 가는 경로를 구하는 문제인데 사이에 웅덩이를 피해 가야한다. 경우의 수를 계산해보면 200!/(100! * 100!)이 된다. 매우 큰 수이기 때문에 완전탐색으로는 제한시간안에 답을 찾을 수 없다. https://m.blog.naver.com/parkhc1992/220669287080 [확률과 통계] 최단거리 경우의수 중2때 배운적이 있을거에요. 최단거리 경우의수 구하는 문제 예를 들면 이런 그림 하나주고 점A에서 점B... blog.naver.com 문제 해결 방법 설명하기 1. 최단거리 구하는 수 계산하기 최단 거리를 구하는 경우의 수는 아래의 그림과 같다. 이를 코드로 구현하면 아래와 같다..

문제 이해하기 주어진 피로도(K)를 사용해서 최대한 많은 던전을 탐험하는 문제였다. 던전의 최대 개수가 8개이니 가장 연산이 많은 경우의 수는 65,536이다, 따라서 완전탐색을 사용하면 시간안에 풀 수 있다. 문제 해결 방법 설명하기 1. 모든 경우의 수를 탐색 아래의 코드를 보면 visited 배열을 사용해 던전의 방문 유무를 확인하고, 해당 던전의 피로도 조건을 만족한다면 일단 던전에 입장해서 탐색을 진행한다. 이 방법을 사용하면 모든 경우의 수를 탐색할 수 있다. def search(k, dungeons, visited): ans = 0 for i in range(len(dungeons)): if visited[i] == False and dungeons[i][0]

문제 이해하기 아래의 그림과 같이 게임 보드와 테이블이 주어지는데 테이블의 블럭들을 사용해서 게임보드에 최대한 채워넣어주면 된다. 단 테이블에 있는 블록을 게임보드에 채워 넣을 땐 주위에 빈 칸이 있으면 안된다는 몇 가지의 조건을이 존재합니다. 문제 해결 방법 설명하기 1. 테이블에서 블럭의 모양을 추출한 후 roate 배열을 저장 블럭들의 회전 배열을 만들기 위해선 블럭의 모양을 알아야 합니다. 이를 위해서 저는 BFS를 사용해 블럭들을 상대좌표로 변환했습니다. 코드를 보면 연결된 블록을 찾기 위해서 절대좌표를 사용해 BFS탐색을 진행합니다. 만약 인접한 블록이 발견됐다면 해당 좌표를 상대 좌표로 변환해줍니다. def bfs(x, y, board, visited, choice = 0): queue = ..

문제 이해하기 주어진 지형에서 아이템을 줍기위한 최단 거리를 구해야 한다. 제한사항은 가장 바깥쪽 테투리만을 이용해 캐릭터를 이동시켜야 한다는 점이다. https://school.programmers.co.kr/learn/courses/30/lessons/87694 문제 해결 방법 1. 배열의 크기를 두 배 늘려야합니다. 아래의 사진을 보시면 5, 3에서 6, 3으로 바로 접근을 할 수 없습니다.하지만 배열의 탐색에서는 인접인덱스끼리의 접근이 가능함으로 오답이 나오게 됩니다.따라서 기존 5, 3이 아닌 크기를 두 배를 늘린 배열을 사용해야 합니다. 따라서 해당 좌표는 (10, 6), (12, 6)으로 변경되고, 직접 접근할 수 없게 됩니다. 또한 기본적인 좌표와 배열의 좌표 표현 방식이 달라지면서 그림과..

문제 이해하기 우리가 원하는 것은 바위를 n개를 제거했을 때 최소 거리가 되는 최대 값을 찾는 것이 목적입니다.주어진 문제의 조건은 아래와 같습니다. 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다. 바위는 1개 이상 50,000개 이하가 있습니다. n 은 1 이상 바위의 개수 이하입니다. https://school.programmers.co.kr/learn/courses/30/lessons/43236 문제 해결 방법 설명하기 1. 최소가 되는 최대값 찾기 우리가 원하는 것은 바위를 n개를 제거했을 때 최소 거리가 되는 최대 값을 찾는 것이 목적입니다. 따라서 바위의 숫자가 적다면 완전탐색으로도 해결이 가능하지만, 해당 문제는 바위의 개수가 50,000개이기 때문에 완전..

문제 이해하기 H-index를 찾는 문제로, h-index는 n번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용됐다면 h의 최댓값이 이 과학자의 H-index입니다 예를들면[3 0 1 6 1 5]가 있다면 3이 h-index가 됨 주의할 점은 배열에 있는 값만 h-index가 되는게 아니기 때문에 최대 값을 기준으로 h-index(0 1, 2, 3, 4, 5, 6)를 탐색해야 합니다. 문제 해결 방법 설명하기 1. 정렬 h번 이상 인용된 논문이 h개 이상이라는 것을 찾기 위해서 정렬을 수행했습니다. 이는 특정 인덱스를 기준으로 이후에 나오는 값은 모두 특정 인덱스의 값보다 크기 때문에 h번 이상이라는 것을 찾기가 쉽습니다. citations.sort() #정렬한 후 max_referen..

문제 이해하기 인천 앞바다에는 등대와 등대 사이를 오가는 뱃길이 총 n-1개 있는 등대가 n개 있습니다. 윤성이는 전력을 아끼기 위해 일부 등대만 켜둘 계획입니다. 그러나 모든 뱃길이 안전하게 운항하기 위해서는 각 뱃길의 양쪽 끝에 적어도 하나의 등대가 켜져 있어야 합니다. 문제 해결 아디어 1. leaf 노드를 불을 꺼야 함으로 먼저 leaf노드를 찾습니다. 다음과 같이 더이상 dfs로 진입할 곳이 없다면 해당 노드는 leaf노드가 됩니다. def dfs(graph, node, visited, lighthouses): for next_node in graph[node]: if not visited[next_node]: dfs(graph, next_node, visited, lighthouses) 2. ..

문제 이해하기 N개의 주사위가 주어지고, 해당 주사위에는 6개의 면에 랜덤한 숫자들이 적혀있음 이 N개의 주사위 중 N/2를 A가 가져가고, 나머지를 B가 가져가고 이렇게 가져간 주사위 중 승률이 가장 높은 주사위를 반환해야함 문제 해결 방법 1. 주사위 선택을 어떻게 하냐에 따라서 결과 값이 달라지기 완전탐색을 진행해야 합니다. 파이썬에서는 combinations 함수를 통해서 주사위 조합을 구할 수 있습니다. combi = list(combinations(range(0, len(dice)), n)) 2. 내가 선택한 주사위에서 나올 수 있는 면들의 조합, 상대 방이 선택한 주사위에서 나올 수 있는 면들의 조합을 구해야 합니다. for my_dice in combi: enemy_dice = list(s..

문제 이해하기 주어진 그래프에서 임의로 삽입된 노드를 찾고, 막대 그래프가 몇 개인지, 도넛 그래프, 8자 그래프가 몇 개인지 찾는 문제였다.여기서 중요한 점은 그래프를 순회해서 모양을 판별하는 것이 아니라, 노드와 간선의 개수를 가지고 어떤 그래프인지 판별하는 것이다. 문제 해결 방법 설명하기 1. 먼저 어떤 정점이 임의로 삽입된 정점은 진출차선만 있는 노드라고 생각했다. 2. 당연히 원래 있던 그래프에서 임의로 정접을 삽입했다고 했으니 해당 정점은 강제로 이어진 것 따라서 진출차선만 있어야 함 3. 그 다음 dfs를 사용해서 그룹을 나눴고, 해당 그룹에는 몇 개의 노드와 엣지가 있는지 계산했다. 4. 모든 노드를 순회했다면, 그룹의 노드와 엣지 정보를 토대로 어떤 그래프가 있는지 판별했다. 코드 im..

문제 이해하기 시추관을 세로로 뚫었을 때 최대 몇 개의 오일을 뽑을 수 있을까를 묻는 문제였다. 아래 그림과 같이 7번으로 뚫었을 때는 총 9개의 오일을 뽑을 수 있는 것을 볼 수 있다 문제 해결 방법 설명하기 1. DFS알고리즘을 이용해 그룹을 나누기로 결정했다. 처음에는 최대 석유 개수를 기록하려고 했는데 아래 오른쪽 그림과 같은 상황에서는 원하는 답을 찾을 수 없기 때문에 그룹으로 나누었다.예를들면 6번 라인에서 굴착을 하면 [2, 1, 1, 12]만큼 오일을 얻을 수 있다는 것을 알기가 어려울 것 같았다. 2. 굴착을 했을 때 어떤 그룹들이 있는지를 저장했다. 아래 그림과 같은 경우에는 초록색 그룹이 3개나 발견됐는데 중복을 제거하는 코드가 필요하다. 3. 그 후 시추 1, 2, ~ 8까지 반복문..

문제 이해하기 숫자 0이 적힌 블록들에 다른 숫자가 적힌 블록들을 설치하려고 한다. 블록을 설치하는 규칙은 다음과 같습니다 블록에 적힌 번호가 n 일 때 가장 첫 블록은 n * 2번 째 도로의 위치에 설치, 그 다음은 n * 3, 4 ...도로의 위치에 설치합니다. 이 때 기존에 설치된 블럭이 존재한다면 해당 블록을 빼고 새로운 블록을 설치합니다. 각 블록은 오름차순으로 주어집니다. 또한 블럭의 숫자는 1 ~ 10,000,000까지의 숫자만 존재합니다. 문제 해결 방법 1. 도로의 입장에서 생각해보면 도로에 설치될 수 있는 블럭은 도로의 위치의 약수입니다. 예를 들면 10번 도로의 위치에는 1, 2, 5의 블록이 설치될 수 있다. 10의 블록이 설치될 수 없는 이유는 10(도로)은 10(블럭) * 1이기..