🌷맹이나라🌻

1. 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 2. 접근 방법 bfs를 사용하면 됩니다. 3. 코드 python from collections import deque def bfs(): global F, S, G, U, D, visited visited = [False] * 1000001 q = deque() visited[S] = True q.append((S, 0)) while q: now, cnt = q.popleft() if now ==..

1. 문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 2. 접근 방법 미로 == bfs 아니겠습니까 근데 이 문제에서 주의할 점이 하나있는데, 입력 받을 때 입력 값이 빈 칸이 기준이 아니라 그냥 숫자 하나씩이어서 input할 때 split()은 사용안해두 됩니당 1. board의 영역을 벗어나는지 확인하는 함수 (is_road) 2. bfs 함수 사실 문제에서 무조건 도착하는 입력 값만 주어진다고 해서, visit 체크하기 귀찮아서 그냥 지나간 자리는 값을 0으로 바꾸..

1. 문제 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 2. 접근 방법 bfs로 풀이를 진행했습니다 dfs로 최소 거리 구하고 싶었는데 결국 4중 for문으로 풀고 말았습니다 1. bfs를 이용해서 섬 나눠주기 이 때, 내륙이 아니라 바다랑 맞닿은 해안가 부분만 따로 리스트에 담아줍니다 2. 4중 for문 이용해서 해안도로 중 가장 짧은 도로 길이 반환 3. 코드 python from collections import deque def is_la..

1. 문제 https://leetcode.com/problems/palindrome-linked-list/ Palindrome 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 2. 접근 방법 deque를 이용해서 풀었습니다. 저번에두 팰린드롬 문제 풀 때 deque를 사용해서 popleft()와 pop()을 비교해서 풀었는데, 동일한 방법으로 풀었습ㄴ다. 하지만 이 문제는 주어진 input값이 연결리스트 형태이기 때문에 value만 데크 ..

1. 문제 https://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 2. 접근 방법 앞에서부터 최저점을 계속 갱신해나가면서, 현재 값과 최저점을 뺐을 때 차이가 가장 컸을 때의 값을 반환한다. 나는 처음에 max값도 min값처럼 계속해서 갱신해나가려고 했는데, 그렇게 되면 max값이 최저점을 만나기 전..

1. 문제 https://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 2. 접근 방법 O(n)으로 하려면 그냥 다 곱해놓고 하나씩 나누면 되게따 했는데, 뒤에 나누기를 사용하지 말라구 되어있다 ^-^ 음 ~! 그래서 또 투포인터같이 ? 왼쪽에서부터 하나씩 다 곱하고, 오른쪽에서부터 하나씩 다 곱하고, 해당 idx까..

1. 문제 https://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. 접근 방법 nums는 2n개의 value가 들어있고, 각각의 요소들을 쌍으로 만들었을 때 해당하는 쌍의 min 값들의 합이 가장 클 때를 구하는 문제입니다 주어진 예시는 [1, 4, 3, 2] 일 때인데, 이 때 답은 4인데요 [1, 2], [3, 4]로 쌍을 나누고, 1+3 했..

1. 문제 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 2. 접근 방법 단순히 for문을 3개 쓰면 O(n3)로 해결할 수 있ㄱㅆ지만 투포인터를 사용하면 O(n2)로 해결할 수 있습니다 !!!!!!!!! 1. 주어진 숫자들을 오름차순 정렬한다. 2. 반복문 하나와 투포인터를 사용해서 각각의 경우의 합을 구하고 만약 해당 idx에서의 value값과 left value, right valu..

1. 문제 https://leetcode.com/problems/two-sum/ Two Sum - 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. 접근 방법 이 문제는 nums의 값 들 중 두 수를 골라 더했을 때 target값이 나오는 두 수의 인덱스를 찾는 문제이다. 사실 for문을 중첩해서 풀이할 수도 있지만 그렇게 될 경우 시간 복잡도가 O(n2)이기 때문에, dict를 사용해서 풀이를 진행했습니다. key에는 숫자 값을 넣고, 해당 value에는 그..

1. 문제 https://leetcode.com/problems/longest-palindromic-substring/ Longest Palindromic Substring - 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. 접근 방법 일단 문제는 주어진 문자열 내에 존재하는 가장 긴 팰린드롬 부분 문자열을 찾으면 됩니다. 팰린드롬은 앞뒤가 같은 문자인데요, 예를 들면 "aba"와 같이 앞에서 봐도, 뒤에서 봐도 같은 문자열을 말합니다 팰린드롬의 종류에는 "..