똥그래미 코딩공장

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 문제를 보자마자 "아 이거 완탐인데?" 하고 알고리즘 분류를 보니까 완탐이 맞았다. 여담인데 문제를 보고 어떤 유형의 알고리즘을 써야하는지 파악하는거도 코테 볼때 매우 중요한 부분이라고 생각한다. 문제 자체는 완탐이라 접근 방법은 알았지만 코드 구현이 빡셀거 같았다. 역시나 '시간초과'가 떠버렸다. 이후 오랜 고민을 해봤지만 더 이상이 시간을 끌면 안될 거 같아 정답코드를 봤다. 내가 생각하지 못한건 행이 아닌 열을 검사할때 기존에 있던 for문으로 가면 됐지만 그러지 못하고 새로 for문을 또 만들어 삼중for문..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 한동안 너무 바빠 블로그에 글을 쓸 시간이 없었다..(변명이지만..) 코딩테스트 준비, 개인 프로젝트, 학교 공부 등 할게 너무 많았다. 알고리즘 문제는 가끔씩 계속 풀었지만 블로그에 글을 쓰진 못했다. 할게 너무 많아서 생각 조차 안났다.. 그래서 오랜만에 글을 쓰게 되었다. 앞으로도 전과 비해선 글을 쓰는 빈도가 많을 거 같진 않다. 하지만 일주일에 2번이라..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 이 문제는 저번에 풀어 보았던 "숨바꼭질" 문제와 거의 동일하다고 볼 수 있다. 아니? 그냥 똑같다. 설명은 주석에 첨부해 놓았다. 아래는 코드이다. from collections import deque import sys input = sys.stdin.readline f,s,g,u,d = map(int,input().split()) count=[0]*(f+1) # 계단 visited = [False]*(f..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 음... 골3문제라기엔 좀 쉬운 문제였다. 기본적으로 다익스트라 알고리즘에 간단한 조건만 들어갔기 때문에 다익스트라 알고리즘을 알고 있는 사람들은 충분히 쉽게 풀 수 있는 문제였다라고 개인적으로 생각한다. 아래는 풀이와 코드이다. (참고로 필자의 풀이는 다익스트라 알고리즘을 알고있다는 가정하에 풀이한것이므로 다익스트라 알고리즘에 대한 설명은 생략하였다.) import..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 해석부터 애먹은 문제이다. 기존에 풀던 이분탐색 문제들과 조금 다른 느낌을 받았다. 어떻게 접근해야 할지를 모르겠어서 풀지를 못하고 있었다. 확실히 골드문제인 이유가 있는거 같다. 다른 사람들의 풀이를 봐도 문제가 이해가 가지 않아 이해하는 꽤 많은 시간을 투자 했다. 집 간 거리를 기준으로 문제를 풀어야 했다. 아래는 풀이 코드이다. n,..

https://www.acmicpc.net/problem/2563 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 이번 문제는 구현 문제이다. 저번주에 소마 1차 코테를 보았는데 구현이 포함된 문제가 거의 대부분이였다. 문제를 이해하고 필요한 알고리즘을 찾는 과정이 굉장히 어려웠다. 나는 구현문제를 많이 풀지 않아서 코테때 애먹었다. 그래서 앞으로는 구현 문제 풀이 비중을 좀 늘려야겠다고 생각을 했다. 아래는 문제 풀이이다. n = int(input()) total = 0 graph = [[0]*101 for _..

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가지의 다른 경우가 있기 때문에 둘을 따로 처리해 주었다. 물론 이 문제는 나 혼자의 힘으로 풀진 못하였다. 하지만 이젠 힌트만 보아도 맞출 수 있게 되었다. 예전에는 힌트를 봐도 몰랐지만 힌트를 보면 맞출수 있는 수준이니 전보다..