코딩관계론

문제 이해하기이동하는 방향이 담긴 배열이 주어질 때, 방의 갯수를 return하는 문제였습니다. 문제 해결 방법 설명하기1. 닫친 방이란?닫친 방을 생각해본다면 이미 방문한 정점에 다시 한번 방문 했을 때 닫친 방이라고 생각할 수 있다.하지만 주의할 점은 다시 방문한 정점은 이전에 사용되지 않은 edge로 부터 진입해야 한다는 점이다. 2. 배열의 확장 배열의 확장은 왜 필요한가.4각형 배열이기 때문에 중간 정점은 생각하지 못하게 된다.따라서 배열의 확장을 통해 중간 정점을 표현할 수 있게 만들어줘야 닫친 방을 모두 찾을 수 있게 된다. 코드from collections import dequedef solution(arrows): answer = 0 visited = {} dir = {}..

문제 이해하기삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 하시오. https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 해결 방법 설명하기1. 최대값을 찾는 방법최대값이 되는 경로를 찾기 위해서는 모든 가능한 경로를 탐색해야 합니다. 그러나 모든 경로를 매번 계산하려고 하면 제한된 시간 내에 문제를 해결할 수 없습니다. 따라서 이전에 저장한 정보를 활용하는 방법이 필요합니다. 제가 선..

문제 이해하기부분 펄스가 있는데 해당 부분 펄스를 적용하고 나서 가장 큰 합을 가지는 부분 수열의 값을 찾는 문제였다. https://school.programmers.co.kr/learn/courses/30/lessons/161988 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 해결 방법 설명하기 1. 가장 큰 부분 수열이 되려면?가장 큰 부분 수열을 찾기 위해서 크게 두 가지 방법이 있다. 하나는 이중 for문을 이용해서 가장 큰 값을 갖는 부분 수열을 찾을 수 있을 것이다. 하지만 sequence 배열의 길이를 보면 해당 방법은 불가능하다. 따라..

문제 이해하기케이크를 잘라서 토핑을 공평하게 나눌 수 있는 가짓수 방법을 찾는 문제였다. 문제 해결 방법 설명하기1. 케이크를 나누기 전 토핑의 가짓수를 계산합니다 for i in topping: if not i in topping_right.keys(): topping_right[i] = 1 else: topping_right[i] += 1 2.토핑을 하나씩 제거하면서 공평하게 나눠지는지를 계산합니다. for i in topping: if len(topping_left.keys()) == len(topping_right.keys()): answer += 1 if ..

문제 이해하기 숫자로 이루어진 문자열 numbers가 주어졌을 때 최소한의 시간으로 타이핑을 하는 경우의 가중치 합을 return 하도록 solution 함수를 완성해주세요문제 해결 방법 설명하기1. 경우의 수 계산하기일단 숫자의 Length가 100,000이기 때문에 완전탐색으 진행한다면 2^100,000이 되니깐 제한시간안에 풀기는 불가능하다.따라서 다른 접근 법이 필요했다. 2. 그리디인가?다른 접근 법 중 처음 생각난 것은 그리디였다. 왜냐하면 왼손과 오른손 중에 다음 칸에 도달할 수 있는 가장 빠른 경로를 구하면 최적의 답이라고 생각했지만 다음과 같은 경우에는 최적의 답을 찾을 수 없게 된다."왼쪽 손이 4번 칸에 위치하고, 오른쪽손이 6번 칸에 위치했을 때 5번 칸으로 이동하려면 어떤 손을 선..

문제 이해하기어떤 왕국에사 새로운 도시를 건설하기 위해선 금과 은이 필요하다.왕은 새로운 도시를 건설하기 위해서 기존 도시에서 금과 은을 가지고 오려고 하고, 이 광물이 새로운 도시에 도착하기 까지 일정 시간이 소요된다.새로운 왕국에 필요한 금과 은이 배달되기 까지의 시간을 구하라. https://school.programmers.co.kr/learn/courses/30/lessons/86053 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 해결 방법 설명하기 1. 경우의 수 계산하기 왕국 내에 존재할 수 있는 도시의 최대..

문제 이해하기 부서별로 신청한 금액이 들어있는 배열 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개이기 때문에 완전..