오구의코딩모험

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 문제 3줄 요약 1. 수백년 전, 골드바흐는 추측했다. 2. "4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다." 3. 백만 이하의 모든 짝수에 대해 검증해봐라 8은 3 + 5 로 나타낼 수 있다. 42는 나타낼 수 있는 경우가 많은데, 만들 수 있는 방법이 여러 가지인 경우는 두 수의 차가 가장 큰 것을 출력한다. 또한 소수의 합으로 나타낼 수 없다면, 문자..

https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 문제 3줄 요약 1. 가로수가 임의의 간격을 두며 직선으로 배치 되어있다. 2. 가로수를 더 심어 모든 가로수들의 간격을 같게 한다. 3. 가로수를 최소로 심어 간격을 같게 할 경우, 몇 개 심어야 할까? 그림판을 키고, 그림으로 문제의 이해를 돕도록 하겠다. 가로수들의 위치가 한 줄에 하나씩 좌표로 주어진다. Ex) 1, 3, 7, 13 일 경우 위의 그림처럼 표현할 수 있고, 간격이 2..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 3줄 요약 1. 짝수인 N명의 사람이 팀을 짜 축구를 한다. 2. 팀원들 간의 시너지가 존재한다. ex) 팀(1번 팀원 + 2번 팀원)의 능력치 = S12+ S21이다. 3. 팀 간 능력치의 차이가 최소가 되도록 팀을 짜봐라. 사람의 수인 N이 최대 20까지 이므로 브루트포스 알고리즘을 이용하였다. 최대 10 vs 10인 축구 경기가 될 것이다. Step 1) 또한 경우의 수를 구하기 위해 조합 라이브러리인 co..

https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 문제 3줄 요약 1. 숫자 1, 2, 3 으로만 이루어져 있는 수열이 있다. 2. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 나쁜 수열. 아니라면 좋은 수열 3. N자리의 좋은 수열 중에서도 가장 작은 좋은 수열을 구하여라. 문제만 읽어봤는데도 정신이 혼미해졌다. 단순히 연속되는 숫자가 아닌 연속되고 인접한 '수열'을 걸러내야 하면서 N의 자리 수열 중 가장 작아야한다. 일단 통과한 코드..

문제 3줄 요약 1. N개의 정수로 이루어진 수열과 주어진 정수 S가 있다. 2. 수열의 원소들을 더하여 S를 만들고자 한다. 3. 주어진 수열의 원소들을 이용하여 S를 만들 수 있는 경우의 수를 구하여라. 처음 문제에 접근 하였을 땐, 투포인터를 이용하여 좌, 우 원소의 합이 S보다 클 때, 작을 때를 나누어 원소들을 더해주는 방식으로 접근하였다. 하지만 투포인터로는 모든 경우의 수를 탐색하긴 어렵다는 글을 확인한 후 브루트포스 알고리즘을 이용하였다. 모든 조합의 경우의 수를 더해보며 타겟인 S와 같은 경우를 카운트 해주었다. from sys import stdin # 조합 라이브러리 from itertools import combinations if __name__ == "__main__": N, S..

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제 3줄 요약 1. 편집기에 위와 같은 4가지 기능이 있다. 2. 초기 문자열에서 입력한 명령어를 차례대로 실행한다. 3. 남은 문자열을 출력해라! L은 커서를 왼쪽으로 한 칸, R은 커서를 오른쪽으로 한 칸, B는 커서 왼쪽 문자 삭제, P $는 $라는 문자를 커서 왼쪽에 추가. (여기서 커서는 문자열 오른쪽 끝에서 시작!!) 쉽게 말해, 왼쪽 이동, 오른쪽 이동, 문자 삭제, 문자 추가가 되겠..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 3줄 요약 1. 1 부터 n까지의 수를 스택에 넣었다가 뽑는다. 2. 뽑은 수들로 수열을 만들 것이다. 3. 만들고자 하는 수열이 주어지는데 만들기 가능하다면, push와 pop 연산 순서대로 출력. 불가능이면 "NO" 출력 예제를 보고 처음엔 주어진 수열이 어딨는거지? 찾고 있었다 ㅋㅎ... 위의 예제 첫 번..

수 정렬하기 1, 2를 이어 3을 풀어보도록 하겠다! 문제 3줄 요약은 아래 링크와 동일하다. https://59travel.tistory.com/65 [Python] 수 정렬하기, 수 정렬하기 2 문제 3줄 요약 1. N개의 수를 오름차순으로 출력한다. 2. 수는 중복되지 않는다. 3. 왼쪽 문제는 N이 1000이하, 오른쪽 문제는 N이 100만 이하이다. 같은 기능을 하는 문제지만, Input으로 들어올 수 있 59travel.tistory.com 기존의 1,2 와 문제는 같지만 3 또한 N의 범위가 다르고, 중복되는 숫자가 존재한다. 때문에 이전에 사용했던 from sys import stdin import heapq if __name__ == "__main__": N = int(stdin.read..

문제 3줄 요약 1. N개의 수를 오름차순으로 출력한다. 2. 수는 중복되지 않는다. 3. 왼쪽 문제는 N이 1000이하, 오른쪽 문제는 N이 100만 이하이다. 같은 기능을 하는 문제지만, Input으로 들어올 수 있는 사이즈가 다른 문제였다. 두 문제 모두 python 리스트의 sort로 푼 코드들이 있는 것 같다. python sort 함수 Timsort라는 정렬 알고리즘을 사용하는데 Quicksort와 같이 평균 시간 복잡도가 O(NlogN) 이지만, 최악의 경우는 더 빠른 O(NlogN) 이라고 합니다. https://realpython.com/sorting-algorithms-python/#the-timsort-algorithm-in-python Sorting Algorithms in Pyth..

문제 3줄 요약 1. 색깔 별 영역을 나눈다. 2. 적록색약은 빨강과 초록을 같은 색으로 인지하여 구역을 나눈다. 3. 일반인이 보는 색깔 별 영역과 적록색약이 보는 색깔 별 영역을 구해라 BFS로 기준으로 잡은 색과 다른 색이 나오면, 다시 돌아가는 방식으로 코드를 작성하였다. 조금 차이점이 있다면, 적록색약일 경우엔 빨강과 초록을 같게 인지하는 조건문을 추가해주었다. 문제가 어렵진 않았지만, 문제를 해결하고 난 후 다른 사람과 코드를 비교해보았을 때, 상하좌우 비교와 구조체 생성을 리스트 하나로 해결하는 코드를 주로 작성하는게 보였다. 지금 나의 코드는 직관적이라고 생각하지만, 코드의 길이가 길고 복잡한 기능이 필요한 BFS, DFS 일 경우 잦은 오류가 발생하는 것 같다. 이후의 DFS, BFS 문..