문제 설명https://www.acmicpc.net/problem/1876 지름이 20cm 인 볼링공을 너비 105cm 인 레인 위에서 굴린다.볼링공이 구르기 시작한 첫 위치는 레인의 정 가운데 위치이고, 해당 위치에서 x도 각도로 굴린다.굴러간 공은 레인 벽과 부딪히면 입사각과 동일한 각도로 반사되어 튕긴다.볼링공이 구르기 시작한 첫 위치로부터 T 미터 떨어진 곳에 지름 12cm 인 볼링 핀이 있다. 처음 굴리기 시작한 각도 x 와 볼링공과 볼링핀 사이 거리 T 가 주어질 때, 이 볼링공이 볼링핀을 맞히는지 여부를 출력하라. 접근 방법우선 각도에 따라서 공이 여러번 튕길 수 있고, 매번 튕기는 것을 다 시뮬레이션으로 구현하는 것은 너무 복잡해보였다.그래서 수학적으로 문제를 풀 수 있을 것 같아서 태블..
https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 백준에도 똑같은 문제가 있다.전에 프로그래머스 레벨 테스트에서 이 문제를 만났다가 구현에서 막혀서 못 풀었던 기억이 났다.(백준에서도 힘들게 풀었었는데..) 이번에 다시 풀어볼 때는 한번에 잘 풀려서 기분이 좋았다. (옛날 풀이는 기억이 나지 않고 완전히 새로운 느낌으로 풀었다.)이 문제의 핵심은 최소힙과 최대힙을 만들고, 이 둘 사이에 데이터 동기화를 잘 시켜주는 것이다. 먼저 데이터를 추가할 때는 두 힙에 모두 데이터를 추가한다.최솟값을 삭..
https://school.programmers.co.kr/learn/courses/30/lessons/81305# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이진트리를 k개 그룹으로 분할할 때, 각 그룹에 있는 노드가 가진 가중치의 합의 최댓값이 최소가 되도록 하는 문제최댓값이 최소가 되어야 한다는 점에서 이분탐색 (매개변수 탐색) 까지는 어렵지 않게 떠올릴 수 있었으나, 이진트리를 k개로 분할하는 구현에서 막혀서 어려웠다. 처음에는 각 트리에 대해서 누적합을 구하고, 누적합 정보를 기반으로 쪼개는 풀이를 떠올렸다.하지만 이 풀이가 27점 맞고 틀려서 디버깅하다가 반례를 못찾아서 클로드에 물어봤더..
https://school.programmers.co.kr/learn/courses/30/lessons/42892 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr x좌표의 상대적인 위치를 이용하여 이진트리의 구성을 파악하고 전위/후위순위 결과를 출력하는 문제처음에는 직접 간선을 연결하고 그래프 순회를 해야하나 생각했는데, '이진트리' 라는 특성상 계속해서 좌/우 구분이 나눠지는 관계를 이용해서 현재 루트 노드가 커버하는 범위를 계속 좁혀나가면서 특정 x좌표의 노드가 현재 노드의 왼쪽/오른쪽 자식인지 판단하도록 하였다.현재 노드의 자식노드인지 판별하는 것은 현재 노드가 커버하는 범위 안에 포함되어 있는지 ..
https://www.acmicpc.net/problem/1248어떤 수열의 연속하는 모든 부분수열 ai ~ aj 에 대한 합의 부호값 (+, 0, -) 를 알고 있을 때, -10 ~ 10 사이의 숫자를 사용하여 만들 수 있는 수열을 찾는 문제 처음에는 어떻게 해야할 지 감이 안왔는데, 보통 이렇게 알고리즘이 감이 안오는 문제는 입력 크기를 줄이고 완전탐색으로 풀도록 유도하는 경우가 많다. 이 문제도 수열의 길이가 최대 10으로 -10 ~ 10 까지 숫자 10개를 모두 시도해보면서 풀 수 있다.그렇다고 정말 나이브하게 완탐으로가면 21^10 이라는 경우의 수를 체크해야 한다.하지만 모든 부분수열의 ai ~ aj 부호값을 모두 만족해야 하는점에서 경우의 수를 치다보면 체크할 경우의 수가 확 줄어든다는 것을..
https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 생각보다 재미있게 푼 그래프 문제백준 티어로 치면, 골드5 정도 될 것 같다. 막대 그래프 = 1자로 연결된 트리도넛 그래프 = 사이클 1개인 그래프8자 그래프 = 사이클이 2개인 그래프 이때 각각의 그래프를 식별할 수 있는 특징을 잡아내면 된다. 막대 그래프는 사이클이 없다.도넛 그래프는 사이클이 존재하며, 모든 정점의 out degree 가 1개이다.8자 그래프는 사이클이 존재하며, 1개 정점의 out degree = 2, 나머지 정점의 ..
https://www.acmicpc.net/problem/1166 이분탐색 심화 개념을 사용해야 하는 문제.. (나도 알고 싶지 않았다)문제 자체는 간단하다.어떤 정육면체 N개를 W*H*L 직육면체 안에 넣고자 할 때, 이 정육면체의 한변의 길이를 최대한 늘리는 것이 문제 풀이이다.단순히 직육면체와 같은 부피를 갖는 N개 정육면체에 대한 한변 길이 구하기로는 풀 수 없다. 극단적으로 얇은데 큰 직육면체를 생각하면 된다. (1 x 10억 x 10억) 내가 맨 처음 생각한 풀이는 (알고보니 정해였지만) 이분탐색이다.주어진 직육면체의 세 변 중 가장 짧은 변의 길이를 반씩 나누면서 그 변의 길이를 정육면체의 변의 길이로 할 때 N개 이상의 상자를 담을 수 있는지 계산하는 것이다. s = 0, e = min(W..
https://www.acmicpc.net/problem/4315 재미있는 트리 연습 문제아이디어 + 구현 모두 깐깐한 문제였다.각 노드가 갖고 있는 구슬 개수가 모두 1개가 되도록 할 때 구슬을 옮기는 최소 횟수를 구하는 문제이다. 내가 생각한 풀이 흐름은 다음과 같다. 1. 전체 트리를 DFS 돌면서 현재 자신을 root 로 하는 서브트리에 대해 이 서브 트리가 가지고 있는 모든 구슬의 개수, 필요한 구슬의 개수를 구한다. 만약 가지고 있는 구슬이 필요한 구슬보다 많다면, 그 차이를 return 하여 부모 노드로 여분 구슬을 넘긴다. DFS 실행이 끝나면 모든 노드는 자신을 루트로 하는 서브트리 모두를 채울 수 있도록 딱 맞게 구슬을 갖고 있거나, 모자라거나 둘 중 하나의 상태가 된다. 2. 두번째로..
https://www.acmicpc.net/problem/4436 가볍게 브론즈 문제를 하나 풀어봤다. (솔브드 마라톤 시스템 추천 문제)모든 k 값을 1부터 다 시도해보면서 브루트포스로 구현하면 되는 문제다. 근데 푸는데 생각보다 시간이 오래 걸렸다.. 그 이유는 set 연산자를 착각해서 그렇다.나는 s.union() 메서드가 기존 집합에 자동적으로 더해주는 줄 알았는데, 기존 집합이 변하지 않고, 새로운 합집합을 반환한다는 점을 프린트로 찍으면서 디버깅하느라 10분정도 걸려서 푼 것 같다.. 이 문제 덕분에 파이썬 집합 연산은 새로운 집합을 반환하므로 기존 집합을 덮어써야 한다는 것을 깨달을 수 있었다. import sysinput = sys.stdin.readlinewhile True: try..
https://www.acmicpc.net/problem/11437 워냑 유명한 유형이다보니 (나도 풀어보지는 않았지만 이 유형에 대해서 들어봤었다.) 정형화된 알고리즘이 있을 것 같은데, 우선 스스로의 고민으로 먼저 풀어보기로 했다. 어떤 트리가 주어질 때, 임의의 두 노드에 대해 그 두 노드의 최소 공통 조상 노드를 찾는 것이 문제의 요구사항이다.이때 트리의 루트는 1번 노드이다.(나는 이 조건을 못 보고 어떤 루트로 잡든 성립하는 문제인가보다~ 하고 1번 노드를 루트로 잡고 풀었는데, 생각해보면 두 노드 중에 한 노드를 매번 루트로 잡으면 그 노드가 최소 공통 조상이 되어버리니 루트는 정해져있어야 의미있는 문제였다.) 처음에는 특정 노드에서부터 루트를 향해 올라가면서 공통 조상 노드를 찾는 방법을 ..
