알고리즘
[프로그래머스] 징검다리
https://school.programmers.co.kr/learn/courses/30/lessons/43236 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이분탐색 문제인걸 알고 풀어도 어려운 문제였다. 알고리즘을 어떻게 적용해야 할지 아이디어가 떠오르지 않아서 힌트를 찾아봤는데 힌트를 보고도 다른 부분에서 막혀서 3시간 정도를 고민하다가 정답을 참고했다. 내가 생각한 풀이 n개의 돌을 제거할때 어떤 돌을 제거하냐에 따라 거리의 최소값이 달라지므로 n개의 돌을 제거하는 모든 경우의 수를 구하는 방법을 생각했지만 제거 가능한 돌의 개수가 너무 많아서 ..
[프로그래머스] 도둑질
https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결 아이디어를 떠올리기 어려웠던 DP 문제이다. 다른 사람의 풀이를 참고 했는데 경우의 수를 나눠서 복잡한 문제를 단순히 만드는게 풀이의 핵심이었다. N개의 집이 있는 한 마을을 도둑이 털 계획을 하고 있다. 단, 각 집은 원형으로 이어져 있으며 집을 털때 서로 인접해 있는 두 개의 집을 털 수 없다. 각 집마다 털 수 있는 돈이 배열로 주어졌을때 도둑이 이 마을에서 털 수 있는 금액의 최대값을..
[프로그래머스] 단속카메라
https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 어려워보이지만 조금만 쉽게 생각해보면 간단히 풀리는 문제였다. 문제를 요약하자면 N대의 자동차가 어느 도로 위를 주행한다. 각 차마다 그 도로에 진입하는 지점과 도로에서 나가는 지점이 주어진다. 이 도로에 진입하여 주행하는 차들은 적어도 한 번은 단속카메라를 거쳐야 하는데 단속카메라를 최소한의 개수로 설치하여 모든 차가 단속카메라를 거치게 하고 싶다. 이때 필요한 카메라의 개수를 구하는 문제이다. 상식적으로 생각했을때 도로 위에 자동차가 가장 많는 지점에 카메라를 ..
[프로그래머스] 큰 수 만들기
https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 문제를 접하고보니 백준에서 똑같은 문제를 풀었던 기억이 났다. 그때는 고민을 하다가 힌트를 보고 풀었었는데, 지금 다시 풀려고 하니 기억이 잘 나지 않았다. 이 문제를 풀면서 복습의 중요성을 깨닫게 됐다. 자리 수가 최대 100만인 어떤 수가 주어지고, 그 수에서 k개 만큼의 숫자를 빼서 얻을 수 있는 가장 큰 수를 구하는 문제이다. 단순하게 생각했을때 주어진 수 number에서 k개 만큼 뺐을때 얻는 수의 자리 수는 len(number)-k이다. 가장 왼쪽 자리의 수(값이 큰 자리 수)부터 만든다고 가정할때 number안에 존재하는 가장..
백준 22942번 : 데이터 체커
https://www.acmicpc.net/problem/22942 22942번: 데이터 체커 데이터가 조건에 맞는다면 YES, 조건에 만족하지 않는다면 NO를 출력한다. www.acmicpc.net 스택 자료구조를 활용해서 푸는 문제이다. x좌표상에 N개의 원이 존재하고, 각 원의 중심(x좌표)와 반지름이 주어진다. 이 N개의 원들 중에서 임의의 원 2개를 선택했을때 교점이 존재하는지 판단하는 문제이다. 즉, N개의 원 중 어느 것이라도 다른 원과 교점이 있으면 안된다. 데이터의 개수(N)이 최대 200,000이므로 N개 중에 2개를 선택하는 모든 경우의 수를 구하는 방법은 시간 초과 판정을 받기 때문에 다른 방법으로 문제를 해결해야 한다. A (중심: a, 반지름: r1), B (중심: b, 반지름:..
백준 2473번 : 세 용액
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 전형적인 투 포인터 알고리즘 문제를 조금 복잡하게 꼬아낸 문제이다. 서로 다른 값을 가진 N개 (3 0: e -= 1 elif v == 0: print(d[i], d[s], d[e]) exit() else: s += 1 print(*r, sep=' ')
백준 20440번 : 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1
https://www.acmicpc.net/problem/20440 20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 첫째 줄에 지동이의 방에 출입한 모기의 마릿수 N(1 ≤ N ≤ 1,000,000)가 주어진다. 다음 N개의 줄에 모기의 입장 시각 TE과 퇴장 시각 TX이 주어진다. (0 ≤ TE m: m = cnt tem = i flag = True elif cnt < m and cnt - d[i] == m and flag: txm = i flag = False print(m) print(tem, txm)
백준 1967번 : 트리의 지름
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 전형적이진 않지만 조금만 생각하면 풀 수 있는 그래프 탐색 문제이다. N개의 노드로 구성된 트리가 주어지고 간선으로 연결된 두 노드의 번호와 간선의 길이(비용)가 주어진다. 간선의 개수는 N-1개로 일정하다. 이 때 이 트리를 이루는 임의의 두 노드 사이의 거리의 최댓값을 구하는 문제다. 각 노드에 대하여 다른 노드로 가는 비용을 모두 더하여 값을 저장하고 그 값들 중에 최댓인..
백준 2800번 : 괄호 제거
https://www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 구현하기도 까다롭고 예외처리도 해줘야해서 개인적으로 어려웠던 문제다. 괄호가 포함된 수식이 입력으로 주어진다. 이 수식에서 괄호를 제거해서 만들 수 있는 모든 서로 다른 수식을 구하려고한다. 단, 괄호는 반드시 한 쌍 이상을 제거해야하며 자신과 맞는 짝이 아닌 괄호끼리는 제거할 수 없다. 문제를 이해하는데는 큰 어려움이 없었고 처음 생각한 해결 아이디어는 이렇다. ..
백준 2812번 : 크게 만들기
https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 아이디어 접근은 쉬우나 구현이 까다로웠던 그리디 문제다. 입력으로 주어지는 N자리 숫자에서 K개 만큼의 수를 제거하여 만들 수 있는 가장 큰 (N-K)자리 수를 구하는 문제다. 처음 생각한 해결 아이디어는 이렇다. N자리 수를 구성하는 숫자들 중 가장 큰 숫자가 만들어야 하는 수의 첫째 자리로 오는 것이 수를 가장 크게 만들 수 있다. 예를들어 주어진 예시 3번에서 10자리 숫자 중 가장 큰 수는 8이지만, 8을 첫째 자리로 만들기 위해선 8 앞의 7개의 숫자를 모두 지워야..