똥그래미 코딩공장

https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 뭔가 bfs의 고정관념을 깬 문제다. 아 이렇게 풀 수도 있구나 라고 생각이든 문제다. 이정도는 풀어야지 나 좀 치네 라는 말이 나오는데 아직은 먼거 같다. 더 잘하고 싶다. 설명은 아래 주석에 담겨있다. import sys from collections import deque input = sys.stdin.readline n,m = map(int,input().split()) graph = [] dx = [1,-..

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 전에 풀었던 N과M(1)문제에 오름차순으로 만 된 정답을 출력하라는 조건만 추가됐다. 1번을 푼 사람들은 2번문제는 무리없이 풀었을거라 생각한다. 추가적인 설명은 생략하겠다. import sys input = sys.stdin.readline n,m = map(int,input().split()) ans = [] visited = [False]*(n+1) def dfs(): if len(ans)..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 전형적인 이분탐색 문제였다. 전날에 살짝 봤지만 컨디션 난조로 오래걸릴거 같아 냅두고 다음날 풀었는데 금방 풀렸다.(너무 졸렸음ㅋㅋ;;) 아래는 풀이 코드이다. import sys input = sys.stdin.readline k,n = map(int,input().split()) line = [] # 전선을 입력 받을 리스트 ans = [] # 11개가 맞아 떨어지..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 백트래킹 문제이다. 백트래킹은 dfs에서 주로 응용되는 알고리즘이다. 방문 후에 다시 미방문 처리를 해주는 알고리즘 이다. 난이도 꽤 있는 알고리즘이라고 말 할 수 있다. 코딩테스트에도 자주 나오는 유형이니 꼭 짚고 넘어가야한다. 아래 코드에 주석을 달아 설명해 놓았다. import sys input = sys.stdin.readline n,m = map(int,input().spli..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이 문제는 파이썬의 dict 함수(hasp map)를 모른다면 풀 수 없는 문제다. 나 또한 딕셔너리를 생각해내지 못해 막혀서 다른 사람들의 코드를 참고하여 dict 쓰는것을 발견해 풀어 낼 수 있었다. 딕셔너리(hash map) 이란 "key 값": "value 값"의 형태로 키값을 입력하면 밸류 값이 출력되는 형태이다. 해시의 특성상 검색, 삽입,수정이 빠르기..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이번 문제는 기본적인 bfs 문제로 풀 수 있다. 하지만 다른 문제와 차이점은 입력예제에 조건이 있다는 것이다. 보통 몇번 반복할지 입력을 받고 입력을 실시하는데 이 문제는 몇번 반복할지 묻지 않고 0,0 이라는 숫자가 나올때까지 프로그램을 계속 실행해야 하는것이다. 처음에 문제를 보고 음.. 살짝 까다롭겠는데 생각을 했지만 bfs에 나오는 큐를 사용한 반복을 적용해서 입력예제를 똑같이 구현..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이 문제는 이분탐색의 "응용" 문제이다. 저번에 풀었던 [수 찾기] 문제 보단 어려웠지만 다 풀고나니 할만 했던거 같다. 이 문제는 가장 긴나무를 end로 하고 그 중간값을 mid로 하여 각각의 나무의 mid부터 end까지의 길이의 합을 더하여 m보다 크거나 같을 경우 mid는 조건에 부합하는 절단선의 높이이기 때문에 answer 리스트에 넣어준다 그 다음 ..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 오늘은 BST 문제를 풀어보았다. BST문제도 코딩테스트에 간간히 나오기도 하고 학교 수업때 이론으로 배운거라 실제로 문제로도 풀어보고 싶었다. 뭔가 처음에 이론을 볼때 퀵정렬 설명이랑 비슷해서 오... 하면서 보았다. 실4 문제를 풀어서 그런지 그렇게 어렵진 않았다. 하지만 난이도 있는 문제를 풀땐 어려울 거 같다. N = int(input()) ..