devlog

출처 : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 방법 dp로 풀어야 하는 문제이다. dp를 설정할 때 문제를 잘 나누어야 한다. dp를 나눌 때 이전 상황에 영향을 받지 않고 앞으로의 상황에만 영향을 받도록 문제를 나누었다. dp[y][x]를 y, x에서 최대로 이동할 수 있는지로 설정했다. dfs함수 안에서 이동 가능한 부분으로 이동할 때 ret의 값과 1 + dfs(ny, nx) 값 중 더 큰 값을 ret에 업데이트..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150368?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 처음으로 할일율을 조절하는 그리디 방법을 생각했으나 할인율이 너무 높아도 안되고 너무 낮아도 안된다고 생각해서 dp 방식을 생각해 봤다. 하지만 dp방식도 이모티콘 개수에 따라, dp 배열이 너무 달려져 완전탐색 방식으로 풀어야겠다고 생각했다. 먼저 완전 탐색 방법의 시간 복잡도를 계산해 봤는데 할인이 4가지 경우 밖에 없고 이모티콘도 최대 7개 까지..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 단순 string을 잘 처리할 수 있느냐의 문제이다. terms를 빠르게 처리해 주기 위해 파이썬의 딕셔너리를 사용해서 각 term에 따른 개월수를 저장했다. 그 후 cal함수를 통해 term을 더해 주었다 여기서 term의 범위는 100 이하 이므로 month가 12 이하가 될 때까지 year을 더해주는 작업이 필요하다. 그 후 보관기간이 지났는지를 판단하기 위해 strin..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이 방법풀지 못하여 다른 분들의 풀이를 참고했다.다익스트라를 변형한 문제였다.이 문제의 핵심은 편도만 경로만 구하면 되는 것이다.또 다익스트라를 적용하여 값들을 업데이트할 때 max(이전 노드의 값, 이전 노드와 현재 노드의 가중치)를 사용해야 한다. import heapqdef solution(n, paths, gates, summits): graph = [[] for _ in ra..

출처 : https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.www.acmicpc.net풀이 방법투 포인터 문제를 연습할 겸 문제를 풀어 보았다. 이중 for문으로 풀면 시간초과가 난다.투 포인터란 배열을 순회하는 하나의 방법으로 포인터를 2개를 사용해서 순회하는 방법이다.왼쪽 포인터와 오른쪽 포인터를 두고 풀어보자왼쪽 포인터부터 오른쪽 포인터까지 합을 리턴하는 함수를 작성한다. 이때 배열의 합에 따라 케이스를 분리하자배열의 합이 M보다 ..

출처: https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A B구하는 거 보단 B->A로 구해야겠다고 생각했다. 하지만 예제 정답 부분만 보고 짝수이면 나누기 2 홀수이면 -1 후 나누기 10을 했다. 예시 부분은 다 정답처리가 되었지만 1 25같은 수가 입력된다면 제대로 해결하지 못할 것이다. 그래서 10으로 나누었을 때 나머지가 1인 경우, 2로 나누었을 때 나머지가 1인 경우 다른 경우는 실패 이렇게 3가지 경우로 나누게 되었다. A, ..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/169199 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 기존 bfs 문제와 다른 점은 board를 벗어나거나 벽에 부딪힐 때까지 한 방향으로 쭉 이동하는 것을 한 번 이동했다고 카운트하는 점이다. 하지만 기존의 bfs를 조금 변형해서 풀 수 있었다. 현재 위치에서 move 함수를 이용해서 다음 위치점을 찾아야 했다. move 함수의 인자로 현재 위치, 이동 방향을 나타내는 인덱스 i를 넘겨주었다. 그 후 while 루프를 통해 벽..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 처음엔 문제를 x축으로 나누어서 진행했다. 같은 x축일 때 까진 visited 배열을 초기화하지 않고 진행했고 x축이 증가할 때마다 visited 방문 배열을 초기화해주었다. 이렇게 하니 효율성 문제가 발생했다. 그래서 다른 분들의 풀이 방법을 참고하니 정사영이라는 알고리즘을 사용하는 것을 볼 수 있었다. 먼저 x축에 따른 추출 가능한 석유량을 count하는 배열 result..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/250137 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 단순 구현문제이다 현재 시간에서 다음 공격 시간으로 바로 이동했다. 그런 후 공격 데이미를 입기 전에 얻는 회복량을 계산하고 데이미를 주었다. 그런 다음 현재 시간을 최근에 받은 공격 시간으로 이동했다. def solution(bandage, health, attacks): max_health = health health_time = 0 now_t = 0 last_time =..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/118668# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 처음에는 그리디 하게 풀 수 있는 방법이 있나 생각해 봤는데 복잡할 거 같아서 dp로 풀어야겠다고 생각했다. dp로 풀기 위해 중복되는 계산이 뭔지 생각해 봐야 한다. 이차원 배열로 dp[알고력][코딩력] = cost 알고력과 코딩력을 가지는데 필요한 최소 시간으로 설정했다. dp배열을 모든 문제를 푸는데 필요한 최대 알고력과 코딩력의 크기로 int max값으로 초기화했다...