알고리즘 (368) 썸네일형 리스트형 [Python] 1551번 수열의 변화 1551번: 수열의 변화 (acmicpc.net) 1551번: 수열의 변화 첫째 줄에 수열의 크기 N과 K가 주어진다. N은 20보다 작거나 같은 자연수이고, K는 0보다 크거나 같고, N-1보다 작거나 같은 정수이다. 둘째 줄에는 수열이 ‘,’로 구분되어 주어진다. 수열을 이루 www.acmicpc.net 22/09/03 마찬가지로 그룹 연습에서 풀었던 문제이다. 문제 자체는 매우 쉬운 편으로, 문제에서 주어진 상황을 반복문으로 그대로 구현하면 된다. 문제 접근 방식: 그대로 구현했다. 개인적으로 글을 쓸 필요도 없을 정도로, 딱히 작성할 내용이 없다. 왜 브론즈 1인지 이해가 되지 않는다. 아래는 내가 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다. 더보기 # 1551번 수열의 변화 N, .. [Python] 21313번 문어 21313번: 문어 (acmicpc.net) 21313번: 문어 문어에게 여덟개의 팔이 있다는 사실은 잘 알려져 있다. 하지만 문어들이 자신의 팔들을 1번, 2번, 3번, ..., 8번이라고 부른다는 말은 오늘 처음 들었을 것이다! 단, 시계방향으로 오름차순이라던 www.acmicpc.net 22/09/03 그룹에서 연습문제로 같이 풀었던 문제 중 하나이다. 간단한 그리디 문제로 쉽게 풀 수 있었다. 문제 접근 방식: 예제 입력을 보고 짝수일 때의 경우를 쉽게 유추할 수 있었다. 붙어있는 배열의 두 원소가 서로 다르고, 그 배열들 중에서 제일 사전 순으로 앞서는 것을 출력하면 되므로, 그리디적인 방법으로 보았을 때, 1과 2가 반복되는 문자열을 출력만 하면 된다. 홀수일 때의 경우는 짝수일 때의 경우에서.. [Python] 2022번 사다리 2022번: 사다리 (acmicpc.net) 2022번: 사다리 첫째 줄에 차례대로 x, y, c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있으며, 3,000,000,000보다 작거나 같다. www.acmicpc.net 22/09/02 은근히 어려웠던 문제이다. 요즘 태그를 보지 않고 문제를 푸는데, 이분 탐색을 활용하는 문제가 아니라 온전히 답안이 나오는 문제인 줄 알고 식 정리에만 시간을 온전히 쏟았다. 알고 보니 명확한 식으로 나오지 않는 문제임을 알고서 이분 탐색을 활용하여 문제를 풀었다. 식 정리가 제일 어려운 문제이다. 문제 접근 방식: 그냥 식 정리를 한 뒤에 이분 탐색으로 문제를 풀면 된다. 이 식 정리가 좀 어렵긴 하지만, 사진으로 나와있으니 참고하.. [Python] 9663번 N-Queen (추후 보강 예정) 9663번: N-Queen (acmicpc.net) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 22/09/01 클래스 3 문제 중에서 안 풀었던 문제가 있기에 풀어보았다. 백트래킹 문제 중에서 가장 유명하고 잘 알려진 문제인 N-Queen 문제이기에, 나는 당연히 이 문제를 솔루션을 보지 않고는 풀기 힘들 것이라고 생각되어서 이 문제를 유튜브 강의를 참고하여 해결하였다. 참고한 유튜브 강의는 아래 링크에 있다. 유튜브 강의에서 설명을 굉장히 잘 해놓았기 때문에 보고 글을 읽으면 더욱 이해가 잘 될 것이다. 파이썬으로 배.. [Python] 1069번 집으로 1069번: 집으로 (acmicpc.net) 1069번: 집으로 은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다. 첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법 www.acmicpc.net 22/09/01 이 문제는 참 창의적인 문제이다. 문제 풀면서 참 감탄한 문제이다. 발상이 굉장히 독특하긴 한데, 수많은 예제들을 보고 이를 쉽게 유추해낼 수 있어서 참 다행이었다. 만약 이 문제가 이렇게까지 예제 입력이 많이 주어지지 않았더라면 지금보다 난이도가 더 높게 매겨지지 않았을까 싶다. 문제 접근 방식: 처음에 살짝 그리디적인 방법으로 접근했다. 이후 이 방법을 뼈대로 하여 고쳐가며 문제를 해결.. [Python] 1270번 전쟁 - 땅따먹기 1270번: 전쟁 - 땅따먹기 (acmicpc.net) 1270번: 전쟁 - 땅따먹기 첫째 줄에는 땅의 개수 n(n 보이어-무어 다수결 투표 알고리즘(Boyer-Moore Majority Vote Algorithm) 최근에 배우게 된 보이어-무어 다수결 투표 알고리즘에 대해 글을 써보고자 한다. 보이어-무어 다수결 투표 알고리즘이란? K명의 후보들이 N명에게 투표받을 때, 과반수 이상인 후보가 나오는지, 나온다면 그 후보가 어떤 후보인지 알아내는 알고리즘.과반수 후보를 가려내는 방법 중 브루트 포스를 이용한 방법과 맵을 이용한 방법(파이썬에서는 딕셔너리 자료형)보다 시간복잡도, 공간 복잡도 면에서 우월함.O(N)의 시간 복잡도로 판단 가능함. 반면, 브루트 포스를 이용한 방법은 O(N^2) 임. 맵을 이용한 방법은 같은 시간 복잡도를 차지하나, 메모리를 더 많이 차지함.스트리밍 알고리즘의 대표적인 예시임.(공간복잡도가 O(1) 임) 이 알고리즘은 두 부분으로 이루어져 있다. 첫 부분은 과반수 원소가 될 수 있는 후보.. [Python] 1024번 수열의 합 1024번: 수열의 합 (acmicpc.net) 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 22/08/31 예전에 북마크 해두었던 문제인데 풀은 문제이다. 실버 2 치고는 수학적 발상이 조금 필요한 것 같아 실버 1로 기여했다. 문제 접근 방법: N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 것이 문제에서 주어진 정보이다. 찾을 수 없다면 -1을 출력하면 된다. 정말 간단하고 짧다. 먼저 나는 길이가 적어도 L이 된다고 했기 때문에, 길이가 L보다 클 수도 있다는 사실에 주목했다. .. 이전 1 ··· 41 42 43 44 45 46 다음
