본문 바로가기
반응형
SMALL

알고리즘

시간 복잡도 느린 정렬 모음 - python N = int(input()) arr = [int(input()) for _ in range(N)] # bubble for i in range(N): for j in range(i + 1, N): if (arr[i] > arr[j]): arr[i], arr[j] = arr[j], arr[i] # selection for i in range(N - 1, -1, -1): idx = i for j in range(i): if (arr[idx] arr[i]): idx = i while (idx >= 1 and arr[idx .. 더보기
18111 - 마인크래프트, python에서의 elif와 else 속도 차이 안녕하세요. 꼬동입니다. 최근 solved.ac를 통해서 문제를 하나씩 부수고 있는데요. 굉장히 좋은 문제를 한 번 들고 와봤습니다. https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 추가 시간이 없기에, C로 푸는게 유리하나, 맥북이라 C를 못 돌려서... 흑흑 문제를 처음 봤을 땐, 굉장히 쉽게 생각했습니다. 왜냐면, 256 * 500 * 500 해도 1억이 안넘으니, 충분히 1초 안에 들어올 수 있다고 생각을 했죠. 근데 이게 뭐람 어떤 .. 더보기
12865 - 평범한 배낭 머리 굴리는데, DP 만한 문제는 없죠 근데 못 품 ㅎ;; 답 봄 ㅎ;; 항상 DP는 푸는 법을 알고나면, 너무나 쉬운거 같아요. 목표 : 가방에 가치가 가장 높게 물건을 넣는 방법 찾기 접근 : 가방에 물건을 넣는 경우의 가치, 가방에 물건을 안 넣는 경우의 가치를 비교하자 접근 방법만 알면 간단합니다. 물건은 총 100 개, 무게는 100,000이며, 시간 복잡도는 10,000,000이며 시간 제한은 2초니 충분하겠네요. 배열을 만들어봅시다. index가 가방의 무게인 배열을요. 그 안에 들어가는 값은 가치입니다. 즉, 물건 순서대로 가방의 무게(index)마다, 최고의 가치를 넣어주면 됩니다. N, K = list(map(int, input().split())) DP = [0 for k in ran.. 더보기
7682 - 틱택토 (구현) https://www.acmicpc.net/problem/7682 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 일 하면서 단계적인 생각을 하는 경우가 많은데, 이럴 때마다 문제를 접근하는 방법이 중요하다고 느낌 몸은 여기 앉아 있는데, 정신은 다른 곳에 가 있으면 문제가 많은 코드를 만들 수 밖에 없는데, 요새 들어 논리적 생각을 할 때, 이런 경우가 몇 번 있어서 훈련을 해야겠더라. 그래서 선택한건 다시 백준 문제 하나씩 푸는 것 쉬운 문제라도 논리적인 생각을 자주 하는 것이 중요하기에 차근차근 다시 .. 더보기
1409. Queries on a Permutation With Key 오랜만에, 문제를 가지고 왔습니다 ! 사실 계속해서 문제를 풀었는데, 포스팅만 안했네요. 이번 문제는 포스팅할 맛이 있는 문제라 가져왔습니다. https://leetcode.com/problems/queries-on-a-permutation-with-key/ Queries on a Permutation With Key - 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 가봅시다 ! 이 문제는 1 ~ m이라는 순열 (순열이란 표현이 맞는가 잘 모르겠는데...?) q.. 더보기
307. Range Sum Query - Mutable 슬 난이도 좀 올려봅시다 ! https://leetcode.com/problems/range-sum-query-mutable/ Range Sum Query - Mutable - 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 본 문제는 구간합 문제입니다. 구간합이라함은 i ~ j 까지 데이터의 합을 말합니다. 이 문제에서는 update라는 메소드가 존재를 하는데 본 메소드를 통해서 값을 변경해나갑니다. 그 변경 값에 대한 구간합도 당연히 초기화가 되겠죠. 이를 염.. 더보기
581. Shortest Unsorted Continuous Subarray 배열이 하나 주어집니다. 이 배열은 정렬이 된 배열일 수도 있고, 안되어 있는 배열일 수도 있습니다. 그렇다면, 이 주어진 배열을 정렬된 배열로 바꾼다면 !? 어느 부분을 바꿔야할까요? 그렇다면 그 바꾸는 부분의 길이는 몇이 될까요 !? 를 물어보는 문제입니다. TestCase 하나를 보시죠. [2, 6, 4, 8, 10, 9, 15] 멀쩡해보이는 이 배열, 안을 들여다보면 뒤죽박죽, 엉망진창입니다. 이 배열을 멀쩡히 정렬된 배열로 만드려고 한다면 1번 ~ 5번 인덱스까지를 정렬하면 됩니다. 즉, 길이는 5가 됩니다. 그렇다면 이 문제 어떻게 풀 수 있을까요? 1. max / min 함수를 활용하자. 저희가 사용하는 언어 Python, 이 Python에는 max, min 함수가 내장되어 있습니다. 배열을.. 더보기
414. Third Maximum Number https://leetcode.com/problems/third-maximum-number/ Third Maximum Number - 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 정말 이 문제가 코딩 면접에서 간단하게 물어볼 수 있는 문제라고 생각합니다. 물론 저는 생각해내지 못했지만, 경이로운 해설을 발견했기에 들고 와봤습니다. 흑 왜 저는 이런 풀이법을 생각해내지 못할까요. 공부를 열심히 합시다. 제가 쓴 풀이법입니다. 정말 어디에 내놓기 창피한 풀이법.... 더보기
반응형
LIST

티스토리툴바