Coding Test/Algorithm
-
[백준] 1644번 소수의 연속합 (파이썬, 두 포인터)Coding Test/Algorithm 2021. 11. 3. 01:43
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 오랜만에 아무것도 안찾아보고 푼 문제다. 하지만 풀고나서 사람들의 풀이를 보니 아직 나는 두 포인터를 활용하는 부분이 부족했던 것 같다. 코드를 보면서 더 설명하겠다. import sys def prime_list(n): sieve = [True] * n m = int(n ** 0.5) for i in range(2, m + 1): if sieve[i] == True: for j in range(i+i, n, i): sieve[j] = False return [i for i in range(2, n) if sieve..
-
[백준] 17404번 RGB거리2 (파이썬, DP) feet. 인간적인 코딩Coding Test/Algorithm 2021. 11. 1. 21:32
https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 개인적으로는 dp 문제가 제일 어렵다. 다른 사람의 코드를 봐도 점화식을 이해하는게 버겁기 때문이다. 참고로 rgb거리2의 점화식을 이해하기 위해서는 우선 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하..
-
[백준] 4386번 별자리 만들기(파이썬, MST)Coding Test/Algorithm 2021. 10. 31. 19:06
https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 이번 문제는 최소 스패닝 트리 문제였다. kuruskal mst 알고리즘을 사용했다. 핵심은 간선간의 비용은 좌표 간의 거리이며 2차 평면에서 두 좌표의 거리는 직각삼각형을 그려서 빗변의 길이를 구하면 두 좌표간의 거리가 된다. x1, y1 과 x2, y2 두 좌표가 있다면 |x1 - x2|^2 + |y1 - y2|^2 의 루트 값이 바로 두 좌표간의 거리가 된다. import sys import ..
-
[백준] 2473번 세 용액 (파이썬, 두 포인터)Coding Test/Algorithm 2021. 10. 29. 11:43
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 이 문제는 이전 용액 문제를 풀고 푸는 것을 추천한다. 2021.08.08 - [Coding Test/Algorithm] - [백준] 2467번 용액 (파이썬) [백준] 2467번 용액 (파이썬) https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 ..
-
[백준] 2239번 스도쿠 (파이썬, DFS)Coding Test/Algorithm 2021. 10. 27. 12:16
https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 익숙한 기법을 좋아하다보니 이번에도 DFS로 구현했다. 사실 BFS로 하기에는 뭔가 이상한 것 같아서 그런 것도 있다. 원래 스도쿠 푸는 걸 좋아했는데 무지성으로 다 때려 박아서 풀지만 나보다 빨리 푸는 코드를 보면서 씁슬한 마음이 들었다. 문제 접근은 간단하다. 규칙에 맞는 숫자가 없다면 백트래킹 하도록 구현하면 그만이다. def dfs(i): if i == len(arr): ppp() s..
-
[2021 KAKAO BLIND RECRUITMENT] 메뉴 리뉴얼 (파이썬)Coding Test/Algorithm 2021. 9. 11. 04:55
오늘 있는 코딩 테스트를 대비해서 열심히 문제를 풀고 있다.. https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 해당 문제를 부분집합이라는 개념에 접근하여 풀어보았다. https://www.welcomekakao.com/learn/courses/30/lessons/42890 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300",..
-
[백준] 2467번 용액 (파이썬)Coding Test/Algorithm 2021. 8. 8. 00:32
https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 이번에는 이진탐색 문제를 풀었다. 2019.06.17 - [Knowledge/Algorithm] - 알고리즘 - 이진탐색 알고리즘 개념 알고리즘 - 이진탐색 알고리즘 개념 안녕하세요. 오늘은 이진탐색 알고리즘 개념에 대해서 정리하려 합니다. 이진탐색이란 이진법, 이분법에서 파생된 말로 아메바를 예로 들 수가 있겠네요. 아메바는 번식을 할 때 자신의 몸을 반 shineild-security.t..
-
[백준] 2166번 다각형의 면적(파이썬)Coding Test/Algorithm 2021. 8. 6. 21:29
https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 처음에 다각형 면적을 도대체 어떻게 구해야하는지 어리둥절했었는데 공식을 알고나서 매우 쉽다는 것을 알았다. https://ko.wikihow.com/%EB%8B%A4%EA%B0%81%ED%98%95-%EB%84%93%EC%9D%B4-%EA%B5%AC%ED%95%98%EA%B8%B0 다각형 넓이 구하기 다각형의 넓이를 계산하는 일은 정삼각형 넓이를 구하는 것처럼 간단하기도 하지만 각 변의 길이가 다른 11각형의 넓이를 구하는..