동학 개발 운동

문제 출처 : www.acmicpc.net/problem/17940 17940번: 지하철 대학원생인 형욱이는 연구실에 출근할 때 주로 지하철을 이용한다. 지하철은 A와 B, 두 개의 회사에서 운영하고 있다. 두 회사는 경쟁사 관계로 사람들이 상대 회사의 지하철을 이용하는 것을 매 www.acmicpc.net 문제 해석 : 최소의 환승과 시간을 기준으로 목적지까지 갈 때 환승 횟수와 시간을 구하는 문제이다. 문제 풀이 : 환승에는 높은 가중치를 두고 다익스트라 알고리즘으로 풀이하면 된다. 3개의 변수를 가지고 다익스트라를 실행할 경우에는 메모리 초과가 워셜 플루이드 알고리즘으로 풀이시 시간 초과가 발생한다. 풀이 코드 import sys, heapq input = sys.stdin.readline def ..

문제 출처 : leetcode.com/problems/reverse-linked-list-ii/ Reverse Linked List II - 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 문제 해석 : 시작점과 끝점이 주어졌을 때 그 구간을 뒤집어서 반화하는 문제이다. 문제 풀이 : 시작점과 끝점 앞과 뒤를 저장해 놓고 그 사이를 뒤집어서 반환하면 된다. ( 이 문제의 풀이는 Python Algorithm Interview 책을 참고 했습니다. ) 풀이 코드 c..

문제 출처 : leetcode.com/problems/reverse-linked-list/ Reverse Linked List - 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 문제 해석 : 주어진 링크드 리스트를 뒤집어서 반환하는 문제이다. 문제 풀이 : 주어진 링크드 리스트를 하나씩 탐색하면서 새로운 링크드리스트에 연결시켜주어 반환하면 된다. 풀이 코드 class ListNode: val = 0 next = None def __init__(self, val ..

문제 출처 : www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 문제 해석 : 여러 종류의 카메라를 90도씩 회전하면서 각자 다른 방향을 동시에 감시할 수 있다. 이때 사각지대가 최소가 되도록 하면 사각지대의 갯수를 구하는 문제이다. 문제 풀이 : 문제에서 요구하는 방법을 차근차근 따르면서 재귀, 스택 형식으로 코드를 작성하면 풀수 있다. 풀이 코드 dx = [-1,0,1,0] dy = [0,1,0,-1] def see(arr, i, j, dir_l..

문제 출처 : leetcode.com/problems/best-time-to-buy-and-sell-stock/ Best Time to Buy and Sell Stock - 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 문제 해석 : 시간에 흐름에 따라 생성된 배열은 각 시간에 흐름에 따른 주식의 가격을 의미한다. 이때 최대의 이득을 구하여라 문제 풀이 : 모든 경우의 수를 검사할 때는 시간 복잡도가 O(N^2)이기 때문에 문제를 풀이할 수 없다. 따라서 O(N..

문제 출처 : leetcode.com/problems/product-of-array-except-self/ Product of Array Except Self - 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 문제 해석 : 배열에서 자기 자신을 제외한 모든 수들의 곱을 구하는 문제이다. 다만 나누기 연산을 활용하지 않아야 하면 시간 복잡도 O(n)에 풀 수 있도록 해야한다. 문제 풀이 : 배열 두개를 활용해서 앞에서부터의 곱 뒤에서 부터의 곱을 미리 계산해 놓은..

문제 출처 : leetcode.com/problems/array-partition-i/ Array Partition I - 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개씩 짝을 지을때 그 최솟값의 합이 가장 큰 경우를 구하는 문제이다. 문제 풀이 : 정렬을 통해서 간단하게 풀이할 수 있다. 정렬되었을 때 가장 큰 값을 최솟값으로 하는 방법은 0번째 2번째 4번째 .... 2n번쨰 수를 선택해서 이를 더해 주는 것이다. 가능한 ..

문제 출처 : leetcode.com/problems/group-anagrams/ Group Anagrams - 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 문제 해석 : 문자열 배열을 입력으로 받고 애너그램 단위로 이를 묶어서 반환하는 문제이다. 문제 풀이 : sort를 함으로 갯수와 문자구성이 동일한지 알 수 있다. 이를 딕셔너리로 정리하여 한 배열에 담아서 반환하면 된다. 풀이 코드 from typing import List class Solution: ..

문제 출처 : leetcode.com/problems/reverse-string/ Reverse String - 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 문제 해석 : 문자 배열을 뒤집어라 문제 풀이 : 다양한 방법으로 풀 수 있지만 가장 간단하게 built-in 함수를 이용했다. 가능한 다른 풀이 : index를 이용해서 직접 변경해 줄 수 있다. 풀이 코드 class Solution: def reverseString(self, s) -> None: s...

문제 출처 : www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 해석 : 두 팀으로 나누어서 능력치 차이를 최소로 하게 팀을 구성하는 문제이다. 문제 풀이 : 처음에는 itertools의 permutations를 이용해서 풀려고 했지만 메모리초과가 나와서 직접 팀을 구성하고 이를 계산해서 풀었다. 풀이에 필요한 기능은 1. 팀을 구성하는 함수 2. 팀의 능력치 차이를 계산하는 함수 가 있으며 이를 활용해서 바로 풀어 낼 수 있다. 풀이 코드 def cal_diff(team1,..