똥그래미 코딩공장

https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 이번 문제는 '투 포인터'라는 알고리즘 개념을 이용해 풀어야 한다. 이분탐색 알고리즘에 있길래 항상 풀던 방식으로 접근해 보았다가 결국 풀지못하고 구글링해서 확인해 보았는데 투 포인터 라는 알고리즘 개념을 이용해 풀고 있었다. 그래서 유투브에 투 포인터 알고리즘을 검색해 강의 좀 들었다. 이번에도 새로운 알고리즘에 대해 배워간다. import sys input = sys.std..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 이 문제는 DP 문제이다. 점화식만 구하면 쉽게 풀 수 있는 문제이다. 그러나... 점화식 구하는게 쉽지가 않다... 점화식을 못구하겠어서 결국 챗 GPT한테 물어봤는데 친절하게 설명해줬다;; DP는 진짜 점화식 구하는게 관건이다. n = int(input()) price = list(map(int,input().split())) dp = [0]*(n+1) for i in range(1,n+1): tmp..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 이 문제는 분명 백트리킹 알고리즘도 사용했고 예제 출력도 잘 나오는데 25%에서 시간초과 탈락을 했다;; 아무리 찾아도 이유를 모르겠어서 사이트에 질문을 남겼는데 다행이 자고 일어나니 어떤 고수분께서 답을 알려주셨다. 아래는 틀렸던 답안이다. import sys input = sys.stdin.readline def dfs(): if len(ans) == 6 and ans == sort..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 다른 유형만 풀다가 오랜만에 그래프 탐색 문제를 풀어보았다. 오랜만에 하니까 가물가물했다. 역시 까먹지않게 자주자주 해주는게 좋은거 같다. 아래는 코드와 설명이다. import sys input = sys.stdin.readline sys.setrecursionlimit(10**9) # 재귀제한을 늘려주는건데 이문제에선 필요없다. n = int(input()) graph = [] for i in range(n): graph.append(l..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 하... 진짜 너무 어렵게 생각을 했다. 모든 알고리즘 문제가 그렇겠지만 어떻게 푸는지 이해는 갔지만 코드로 표현한다는게 진짜 실력인거 같다. 이 문제에서 팍 느꼈다. 문제를 풀때에는 고정관념에서 벗어나야한다. 어떠한 문제를 보고 이런 문제는 이렇게 풀면되지라는 공식처럼 외우고 있다간 조금만 변형된 문제 맞닥뜨리면 그 문제를 풀 수 없게된다. 심지어 그 문제가 더 쉬운 문제라..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 오랜만에 dp문제를 풀어보았다. dp 문제는 점화식 설정이 매우 중요하다. 문제를 보고 경우의 수를 그려가며 어떤 차례에서 경우의 수가 반복 된다면 그때부터 점화식의 설정해서 풀면 된다. 그러면 까다로운 조건이 있지 않는 한 금방 풀릴것이다. 아래는 코드와 주석으로 달아놓은 풀이이다. 점화식만 설정하면 풀리는 문제들이라 설명이 크게 길지가 않다. 꼭 본인이 경우의 수를 그려가며 풀어보길 권한다. i..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 이번 문제는 새로 배운게 많았다. 1. int(1e9)가 10억을 뜻한다는거 2. if, elif가 아닌 if 로만 만들면 전부 다 실행된다는거 문제가 생각했던 풀이와 달라 모범답안을 참고하는 수 밖에 없었다. 풀이를 보니 계속 고민을 했어도 못풀었을거 같긴하다 ㅋㅋ;;; 하지만 이렇게 또 새로운 풀이에 대해 배웠으니 뿌듯하긴 하다. impo..

https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 음... 지금까지 풀었던 BS문제들과 비슷한 문제다. 조금만 생각하면 쉽게 풀 수 있는 문제다. 금방 풀어서 별 코멘트가 없다. 아래는 코드와 설명이다. import sys input = sys.stdin.readline n = int(input()) region = list(map(int,input().split())) m = int(input()) ans = [] def bs(array,..