본문 바로가기

🧩 Algorithm/구현6

[LeetCode] 2181번: 기존 연결 리스트 수정하기 Hint 1. 어떻게 하면 포인터 2개를 이용해서 기존 리스트를 원하는 결과로 수정할 수 있을까? 2. 포인터 1개는 수정하는 노드 위치에 (a), 다른 하나는 리스트 전체를 확인하는 용도(b)로 이용해보자! 3. 움직이는 포인터b가 그 다음 0에 도달할 때까지 숫자들을 수정하는 포인터a 위치에 더하면 된다. 4. 마지막 노드는 null에 연결되도록 바꿔야한다. LeetCode 2181번: Merge Nodes in Between Zeros (풀어보기) class Solution: def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]: # 포인터 2개 만들기 # now = 덧셈할 포인터 위치 # pointer = 리스트 전체를 확인할 .. 2023. 4. 30.

[LeetCode] 1828번: 원 안의 점 개수 Hint 1. 원과 점들의 최대 개수가 각각 500개이기 때문에 for문 2개를 사용해서 일일이 비교해도 된다 2. Follow up에 O(n)으로 풀어보라고 되어있지만 이건 나중에 도전...^^ LeetCode 1828번: Queries on Number of Points Inside a Circle (풀어보기) class Solution: def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]: # points를 x, y 순서로 작은 숫자부터 큰 숫자까지 정렬한다 points = sorted(points, key=lambda x: (x[0],x[1])) answer = [] for query in que.. 2023. 4. 28.

[LeetCode] 876번: 연결 리스트 Goal 1. 연결 리스트 이해하기 2. 가장 간단한 연결 리스트 알고리즘 문제 풀어보기 연결 리스트(Linked List)란? 연결 리스트란 리스트 안에 있는 항목들이 그 다음 순서로 오는 항목과 연결되어 정해진 순서로 묶여 있는 리스트 구조를 말한다. LeetCode 876번: Middle of the Linked List (풀어보기) Hint 1. head라는 연결 리스트 구조의 정의 : head.val = 현재 위치의 수 head.next= 다음 연결된 리스트 2. 총 개수가 1개일 때는 현재 위치와 중간 지점의 위치가 같다 3. 연결된 리스트의 개수가 하나씩 늘어날 때마다 현재 위치와 중간 지점의 위치가 어떻게 변하는지 생각해보자 4. 총 개수가 홀수일 때와 짝수일 때 현재 위치와 중간 지점의 .. 2023. 3. 11.

[백준] 10808번: 알파벳 개수 Hint 1. 알파벳 개수는 총 26개로 정해져 있다. 2. ord()을 사용하면 알파벳을 아스키 숫자로 변환할 수 있다. 3. ord('a')는 97이다. 백준 10808번: 알파벳 개수 (풀어보기) # 알파벳 개수를 셀 수 있게 미리 0으로 된 리스트를 만들어 준다 alphabet = [0 for i in range(26)] for char in input(): # ord('a')는 97이기 때문에 97을 빼면 alphabet 리스트에서 0번째로 값을 추가할 수 있다 alphabet[ord(char) - 97] += 1 # 리스트는 join을 써서 string 형태로 합칠 수 있다. 이때, 리스트에 들어있는 값들은 string이어야 한다 print(' '.join(map(str, alphabet))) 2023. 3. 6.

[백준] 1929번: 소수 구하기 Hint 1. 1부터 n까지의 숫자가 소수인지 아닌지 확인을 하고, 소수이면 그 숫자의 배수들은 소수일까요? 2. 소수의 배수들은 소수가 아닌게 확실하기 때문에 미리 제거해주면 나중에 소수인지 확인할 필요가 없다! 3. 에라토스테네스의 체 이용하기 (그게 뭐지?) 백준 1929번: 소수 구하기 (풀어보기) import sys M, N = map(int, sys.stdin.readline().split()) # N까지의 숫자의 소수인지 아닌지에 대한 여부를 판단하는 배열 만들기 # 이것이 에레스토스테네스의 체! is_prime = [True] * (N+1) is_prime[0], is_prime[1] = False, False # 2부터 N까지의 숫자의 배수는 모두 소수가 아니라고 False로 바꿔주기 f.. 2023. 2. 18.

에라토스테네스의 체 Goal 1. 소수 정의하기 2. 소수 찾는 알고리즘 - "에라토스테네스의 체" 이해하기 소수란? 소수란 숫자 중 나 자신과 1로만 나눠지는 수다. 즉, 그 2개의 수 이외의 다른 수로 나눠진다면 소수가 아닌 "합성수" 라고 말할 수 있다! 예시) 소수 : 2, 3, 5, 7, 11, 13, 17, 19, ... 그 외 : 4 (2로 나눠지니까), 6 (2와 3으로 나눠지니까), 8 (2로 나눠지니까), 9 (3으로 나눠지니까), ... "에라토스테네스의 체"는 언제 필요한가? N이라는 숫자가 소수인지 아닌지 판단하기 위해서는 2부터 N/2 까지의 숫자로 나눠봐야 알 수 있다 하지만 2부터 100까지의 숫자 중에서 소수를 출력하라고 한다면 이중 for문을 돌려야하고 시간 복잡도는 O(n^2)으로 느리다 .. 2023. 2. 13.

이전 1 다음

티스토리툴바