똥그래미 코딩공장

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 요즘 구현, 백트래킹, 브루트포스에 관한 문제를 풀어보고 있는중이다. 해당 유형의 코딩테스트 문제가 많이 나오고 있는 추세인거 같다. 그래서 최대한 많은 유형의 문제를 풀어보려고 하는 중이다. 아무래도 완탐,다이나믹 프로그래밍 등 언급한 분야들에 약하다 보니 약점을 커버 하기 위해 문제를 풀어보는 중이다. 이 문제도 그래서 풀어 보았다. 아래는 풀이 코드이다. import sys input = sys.stdin..

https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 이 문제는 처음에 쉽게 생각했다. 지금까지 풀었던 문제들과 크게 다를게 없구나 하고 막힘없이 풀어 갔다. 그리고 예제들을 돌렸을때 잘 나오길래 오 됐다!! 하고 제출을 했는데... "시간초과" 가 떠버렸다... 그래서 pypy3로 돌려봤는데 여기선 정답이 떴다. 하지만 python3로 정답이 떠야 하기 때문에 다시 풀어보려다 실패하고 결국 다른 사람의 풀이를 참고하게 되었다. 아래는 풀이 코드이..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 이 문제를 보고 "어?! 다익스트라로 풀면 되겠네" 하고 바로 다익스트라로 풀었는데 시간초과가 나와버렸다. 즉, 알고리즘 선택이 잘못된 것이였다. 그래서 dfs겠는데 하고 풀어보려 했지만 결국 풀 수가 없었다. 그래서 결국 구글링을 해보던 도중에 접근 방법을 알게됐다. 우선, 그래프의 특징을 알아야 한다. 트리의 노드중 아무거나 하나 선택한다. 그리고 그 노드로부터 가장 먼 거..

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번이라..