오뚝이개발자

문제 https://leetcode.com/problems/3sum/ 3Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 나의 풀이 리트코드 풀이를 하다가 굉장히 재미있는 문제가 있어 가져와봤다. 문제는 간단하다. 리스트와 타겟이 주어지면 그 리스트의 3개의 원소의 합이 타겟과 같아지는 그룹을 return하는 문제다. 여기서 포인트는 단순히 3중 for문으로 구현하면 시간초과가 난다는 것이다. 다른 방법을 고안해야 하는데 그 풀이가 굉장히 흥미롭다. tw..

문제 https://leetcode.com/problems/integer-to-roman/ Integer to Roman - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 나의 풀이 2가지 방법으로 풀이했다. 첫 번째 방법은 좀 naive한 풀이이고, 두 번째 방법은 변환의 규칙을 파악한 풀이이다. SOL 1) 문제에서 주어진 조건이 num의 범위가 [1,3999]이므로 이 범위 안에서만 변환을 생각하면 된다. 예컨대, 256을 변환하려면 200+50+6으로 분..

문제 https://www.acmicpc.net/problem/10448 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net 나의 풀이 사실 처음엔 itertools 모듈의 중복조합을 사용해 구했다. 물론 답은 맞았지만 조금 더 nice해 보이는 코드가 있어 첨부한다. 이 문제는 브루트 포스 문제로 그냥 가능한 경우를 모두 카운트 해주면 된다. 문제에서 주어진 조건 중 1000이하의 자연수만 입력으로 주어진다고 했기 때문에 1000 이하의 모든 유레카 수를 구해두면 된다. eureka라는 flag 배열을 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 나의 풀이 뭔가 그래프 문제라서 복잡한 알고리즘을 써야할 줄 알았는데 생각보다 간단하게 해결했다. 자식-부모의 pair로 이루어진 dictionary를 활용해 반복적으로 돈을 분배하면 된다. 이 때 반복문의 종료 조건은 center까지 도달해 분배가 끝나거나 혹은 나눌 돈의 10%가 1원 미만(문제에서 주어진 종료조건)이다. 문제의 조건에서 10%를 ..

개념 위상정렬이란 directed graph에서 꼭짓점을 방향성을 거스르지 않도록 정렬하는 방법이다. 실생활에서 대표적인 예시가 바로 선수과목(prerequisite)이다. 알고리즘 구현하는 방법은 아래와 같다. 연결성에 대한 정보를 가지고 인접리스트를 만든다. 이를 기반으로 in-degree(해당 vertex로 들어오는 선의 갯수) 정보를 담은 배열을 만든다. in-degree가 0인 vertex를 stack에 담는다. stack에서 pop하고 해당 vertex와 연결된 점들의 in-degree를 -1 한다. 3과 4를 반복하며 stack에서 pop 해줄 때마다 answer 리스트에 담으면 해당 결과가 위상정렬의 결과가 된다. 아래와 같은 그래프가 있다고 하면, in-degree(진입차수) 리스트는 아..

문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 나의 풀이 위상 정렬을 사용해 푸는 대표적인 문제이다. 위상 정렬의 개념을 모르겠으면 이 글을 참조하기 바란다. 코드 # https://www.acmicpc.net/problem/2252 n, m = list(map(int, input().split())) # adjacent list adj_list = [[] for _ in range(n+1)] ..

문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 나의 풀이 DFS와 DP가 합쳐진 유형의 문제이다. 시작지점이 정해진 것이 아니므로 각 지점을 시작지점으로 했을 때 최장거리를 계산해 이들 중 다시 가장 큰 값을 답으로 출력하는 문제이다. 그냥 단순히 모든 지점을 시작점으로 해서 DFS로 탐색해도 되지만 이미 했던 연산을 중복해서 계산하므로 시간초과가 난다. 따라서 DP를 사용해 해당 지점을 시작점으로 했을 때 갈 수 있는 최장경로..

문제 https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하 programmers.co.kr 나의 풀이 브루트 포스 문제이다. 생각보다 어려웠던 것 같다. 중요하게 고려해야 할 것은 크게 두 가지이다. 1. 외벽은 원형으로 이루어져 있는데 주어진 weak 리스트가 그것을 반영하지 못한다. -> weak 리스트 배열의 길이를 2배로 늘려서 해결. 예컨대, weak = [1,5,6,10], n=12라면 weak_point = [1,5,6,10,13,1..