똥그래미 코딩공장

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 이번 문제는 너무너무너무너무 어려웠다;; 기존에 풀던 다익스트라 방식에서 조건만 조금 추가해서 구해주면 되나 싶었는데 역시나 쉽지 않았다. 골드 문제는 괜히 골드가 아닌거 같다;; 뭔가 dp의 특징도 살짝 들어간 문제인거 같다. 아래는 코드와 설명이다. import sys import heapq input = sys.stdin.readline n,e =..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 전에 풀었던 숨바꼭질 문제의 업그레이드 버전이다. 이 문제에선 앞뒤로 이동했을때면 1초를 더해주고 2배위치로 이동한것은 0초로 친다. 2가지의 다른 경우가 있기 때문에 둘을 따로 처리해 주었다. 물론 이 문제는 나 혼자의 힘으로 풀진 못하였다. 하지만 이젠 힌트만 보아도 맞출 수 있게 되었다. 예전에는 힌트를 봐도 몰랐지만 힌트를 보면 맞출수 있는 수준이니 전보다..

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..