도비LOG(跳飛錄)

https://school.programmers.co.kr/learn/courses/30/lessons/181187 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 요약반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return※ 각 원 위의 점도 포함하여 센다. 풀이1. 1사분면만 고려하고 계산한 뒤 나중에 4를 곱한다.2. x좌표를 0부터 r2까지 순회하면서,    2.1. 각 x에 대해 r1     2.2. y의 상한과 y의 하한을 구한다.3. x축과 y축 상의 중복 계..

https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 보석이 진열된 배열이 주어졌을 때, 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아라. 풀이 문제의 제한사항에서 gems의 길이가 최대 100,000이라고 하니, 완전탐색을 할 경우 시간초과가 발생할 위험이 있다. 따라서 다른 접근법을 생각해봐야 한다. 리스트 내의 부분리스트를 투포인터로 차례차례 탐색하면서, 만약 모든 보석을 포함하는 부분리스트를 발견할 경우 이를..

https://school.programmers.co.kr/learn/courses/30/lessons/64064 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 응모자 아이디 배열 user_id와, 일부를 *로 가린 불량 사용자 배열 banned_id이 주어졌을 때, 제제 아이디 목록은 몇 가지 경우의 수가 가능한지를 return 풀이 permutation을 활용한다. 먼저, user_id에서 banned_id의 원소 수만큼 가능한 순열을 모두 구한다. 그리고 구해진 각 순열들을 순회하면서, 해당 순열 내의 user_id가 banned_id에 ..

https://www.acmicpc.net/problem/15686 문제 요약 치킨 거리 = 집과 가장 가까운 치킨 거리 = |x1-x2| + |y1-y2| 도시의 치킨 거리 = 모든 집의 치킨 거리의 합 도시의 치킨거리가 가장 작게 되도록 치킨집 M개만 남겼을 때의 도시의 치킨거리를 구하라. 풀이 m개의 치킨 집을 남기는 조합에 대해서, 도시의 치킨 거리가 최소가 되는 조합에서의 도시의 치킨 거리를 리턴한다. # 백준 15686 치킨 배달 골드5 https://www.acmicpc.net/problem/15686 # 치킨거리: 집과 가장 가까운 치킨집까지의 거리 = |x1-x2| + |y1-y2| # 도시의 치킨거리 = 모든 집의 치킨 거리의 합 # 도시의 치킨거리가 가장 작게 되도록 치킨집 M개만 남..

https://school.programmers.co.kr/learn/courses/30/lessons/17679 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 2차원 행렬 모양의 게임판에서 2x2 형태로 4칸이 일치하면 해당 칸들을 삭제하고, 해당 칸들의 위에 있던 칸들이 그대로 내려오는 게임에서, 칸이 삭제되는 수를 리턴한다. 풀이 2x2 형태의 4칸이 모두 일치하는가를 확인한다. 일치한다면 해당 칸들을 제거한다. 칸을 제거하는 것은 '0'이라는 표시를 해주는 것으로 대체한다. 칸을 제거하면서 제거한 만큼 카운트해준다. 삭제할 칸들을 다시 ..

https://www.acmicpc.net/problem/2096 문제 요약 바로 아래 칸 혹은 바로 아래 칸과 인접한 칸으로만 이동이 가능할 때, 얻을 수 있는 최대 점수와 최소 점수를 리턴. 풀이 DP로 풀 수 있는데 메모리 제한이 4MB로 매우 작다. 입력값을 배열에 직접 담고, DP 방식으로 다음행에다가 이전 행의 정보를 계속 누적하는 방식으로 풀면 메모리 초과가 뜬다. DP 방식으로 풀되 매 행을 받을 때마다 결과를 처리함으로써 메모리를 절약해야 한다. # 백준 2096 내려가기 골드5 https://www.acmicpc.net/problem/2096 # 바로 아래 혹은 바로 아래와 인접한 칸으로만 이동 가능 # 최대 점수, 최소 점수를 구하라. n = int(input()) a,b,c = ma..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 요약 출발 지점에서 끝 지점으로 가는 최소 비용 리턴 풀이 기름값이 가장 저렴한 도시에서 기름을 최대한 많이 채우면 된다. 출발 지점부터 끝 지점까지의 가격을 훑어보면서, 최저가 도시를 찾는다면 현재 필요한 비용을 해당 도시의 가격을 기준으로 갱신해준다. # 백준 13305 주유소 https://www.acmicpc.net/problem/13305 # 도시마다 주유소가 있음. ..

https://www.acmicpc.net/problem/1806 문제 요약 연속된 수들의 부분합 중에서 합이 S 이상 되는 것 중 길이가 가장 짧은 것의 길이를 리턴 풀이 투 포인터 방식으로 풀 수 있다. 부분합이 s이상일 경우 최소 길이를 업데이트해주고, 왼쪽 포인터를 오른쪽으로 이동한다. 그리고 부분합이 s 미만일 경우 오른쪽 포인터를 오른쪽으로 이동한다. 즉, 윈도우를 늘여서 부분합을 증가시켜준다. # 투 포인터 # 백준 1806 부분합 n, s = map(int, input().split()) nums = list(map(int, input().split())) left = 0 # 왼쪽포인터 right = 0 # 오른쪽포인터 summation = 0 # 부분합 min_len = 100000001..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 요약 바이러스는 상하좌우 인접 빈칸으로 퍼져나갈 수 있다. 벽 3개를 세워 확산을 최대한 막아야 한다. 0=빈칸, 1=벽, 2=바이러스 벽을 세운 뒤 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 함. 이 안전영역의 최댓값을 구하라. 풀이 먼저 벽을 3개 세우고 나서 바이러스의 위치부터 시작하는 bfs를 수행한다. 이렇게 함으로써 바이러스가 퍼지는 영역을 구해볼 수 있고, 바이러스가 다 퍼지고 난 후의 ..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 요약 트리를 입력 받아서 전위 순회, 중위 순회, 후위 순회 결과를 출력하여라. 풀이 전위 순회, 중위 순회, 후위 순회를 하는 함수를 각각 구현한다. 전위 순회는 root -> left -> right 순서로, 중위 순회는 left -> root -> right 순서로, 후위 순회는 left -> right -> root 순서로 탐색해야 한다. 이를 위해 각 함수를 재귀함수로 구..