알고리즘
-
[백준] 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..
-
[백준] 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",..
-
[백준] 단어정렬 (1181번 파이썬)Coding Test/Algorithm 2021. 7. 15. 06:02
https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 이번 문제는 생각을 좀 하게 만든 문제였다. 하지만 여전히 가볍게 풀었다 음하하하 입력 조건을 보면 문자열의 길이가 최대 50개라고 한다. 나는 어렵게 정렬하기보다는 다른 문제를 풀때 방문한 좌표를 저장하는 스킬을 응용해서 풀었다. 길이가 50인 배열을 만들고 입력받은 문자열의 길이에 해당하는 인덱스에 해당 문자열을 넣었다. word = sys.stdin.readline().rstrip..
-
[백준] 체스판 다시 칠하기 (1018번 파이썬)Coding Test/Algorithm 2021. 6. 12. 02:28
요즘 1일 1문제 푸는 재미 들린 필자. 오늘은 체스판 다시 칠하기를 풀었다. https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 알고리즘 분류는 부르트포스이다. (내 맘대로 풀라는 문제) 사실 이런 문제를 좋아한다. 왜냐하면 특정 알고리즘을 이용해야만 풀리는 문제는 좀.. 창의력을 막는 기분이다. 이런 문제 특징이 굉장히 다양한 방법으로 풀 수 있기 때문에 다양한 측면을 생각하여 푸는 능력을 기를 수 있다는 것이다. 이 문제는 두가지가 중..
-
[자료구조] 큐(Queue)에 대해서 알아보자Knowledge/Algorithm 2020. 5. 22. 03:56
주요 특징 1. FIFO(First-in, First-out) 더운 여름날 아마X빈에서 버블티를 사서 먹는 상상을 해보자. 빨대로 빨려 들어오는 타피오카 펄을 먹으며 우리는 큐를 생각해 낼 수 있다. 그것은 바로 선입선출의 과정을 진행하는 큐이다. 선입선출이란 우리가 빨대로 먹는 펄처럼 먼저 빨대에 들어온 녀석이 먼저 내 입에 들어온다는 법칙이다. 이 법칙은 판매업을 하는 가게에서 철칙으로 사용될 정도로 널리 사용되고 있으며 장점은 명확하다. 바로 제품의 신선도. 즉, 경우에 따라서 순환이 이루어 지지 못하는 스택과는 다르게 큐는 선착순으로 이루어진 공평한 순환을 겪게 된다. 또 다른 예시를 보면 은행을 예로 들 수 있다. 은행은 들어온 순서대로 번호표를 뽑고 기다리다가 번호 순서대로 작업을 처리하게 된..