import sys from itertools import combinations input = sys.stdin.readline n = int(input()) checkpoints = [] for _ in range(n): x, y = map(int, input().split()) checkpoints.append([x, y]) answer = int(1e9) for comb in combinations(checkpoints[1:-1], n-3): temp = [] temp.append(checkpoints[0]) temp += list(comb) temp.append(checkpoints[-1]) distance = 0 for i in range(n-2): x1, y1 = temp[i] x2, y2 ..
Algorithm (PS)
https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Greedy 문제이다 !! 핵심은 가장 가벼운 사람 + 가장 무거운 사람
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 자존감을 올려주는 단순구현문제..ㅎㅎ 문제에서 시키는대로 구현했다 1. 0이아닌 칸 찾기 2. 찾은 칸의 상하좌우에 0 개수 세기 3. 빙하가 녹을 좌표들을 모았다가 한번에 처리하기 4. 1 ~ 3 반복하면서 현재 빙산 덩어리가 몇개인지 세어주기 --> count_iceberg() 함수에서 bfs로 빙산 덩어리를 카운트 함 5. 4번 과정에서 빙하가 모두 녹아버리는 경우를 확인하기 위해 ch..
https://school.programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr greedy 라길래 처음엔 단순하게 작은 숫자들 차례대로 구해서 전체 숫자에서 지워주는 방식으로 갔다 그런데 이 방식은 test case 3에서 걸린다.. "4177252841" 의 경우 가장 작은 숫자들 k 개 고르면 1, 1, 2, 2 인데 이걸 linear 하게 지우면 얻는 값이 477584 가 나오게 된다. but 실제로는 775841이 만들 수 있는 가장 큰 수라는 반례가 생긴다. (Gr..
https://www.acmicpc.net/problem/17394 17394번: 핑거 스냅 [어벤져스] 시리즈를 보지 않은 사람이라도 ‘인피니티 건틀렛’이 무엇인지는 다들 알 것이다. 그래도 모르는 사람들을 위해 설명을 하자면, 인피니티 스톤이 모두 모인 인피니티 건틀렛을 끼 www.acmicpc.net 이문제는 BFS + 소수판별 알고리즘 이 핵심이었다. 오랜만에 에라토스테네스의 체를 정리해보았다. https://sinclairstudio.tistory.com/492 에라토스테네스의 체 (소수판별 알고리즘) Python 에라토스테네스의 체 소수를 구하는 알고리즘 문제에서 주로 사용되는 풀이 방식이다. 1. 2 ~ N 까지의 자연수들 중에서, 아직 지워지지 않은 수들 중에서 가장 작은 수를 찾는다. 이..
에라토스테네스의 체 소수를 구하는 알고리즘 문제에서 주로 사용되는 풀이 방식이다. 1. 2 ~ N 까지의 자연수들 중에서, 아직 지워지지 않은 수들 중에서 가장 작은 수를 찾는다. 이를 p 라고 한다. 2. p는 소수이므로 지우지 않고 남겨준다. 3. p 의 배수들을 하나씩 지워나간다. 1 ~ 3 의 과정들을 반복하면 결국 소수들만 남게 된다. ex) 2는 소수이므로 지우지 않고 , 4, 6, 8 ... 은 지워나가기 위의 그림을 참고하면 이해가 빠르다 N = 1000000 primes = [True] * (N+1) # 소수 primes[0] = False # 0 은 자연수 아님 primes[1] = False # 1은 소수 될 수 없음 for i in range(2, N+1): if primes[i]:..
https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 느리긴하지만 통과했다 ㅎㅎ.. 문제를 처음에 제대로 안읽어서 두가지 원인으로 삽질을 했다. 1. 동전 1개만!!!!!!! 떨어뜨려야 한다 2개 떨어뜨리는건 안되고 꼭 1개만이다 .... 2. 벽을 만났을 때 ('#') 이동하지 않는다. 주의할 점은 벽을 만나서 이동하지 않다가 그다음 버튼누를때 다른 방향으로 이동을 시도하는 것이 가능하다는 것이다. 따라서 벽을 만났다고 해서 그 동전을 떨어뜨린 ..
https://www.acmicpc.net/problem/9997 9997번: 폰트 첫째 줄에 단어의 개수 N (1 ≤ N ≤ 25)가 주어진다. 다음 N개 줄에는 사전에 포함되어있는 단어가 주어진다. 단어의 길이는 100을 넘지 않으며, 중복되는 단어는 주어지지 않는다. www.acmicpc.net * 비트마스킹을 사용할 수 있는 이유 : 알파벳 26자리 방문 표시를 0 or 1 로 할 수 있음 ex) 1
