오뚝이개발자

문제 https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. www.acmicpc.net 생각의 흐름 그리 길지않기 때문에 코드로 설명을 대신한다. 코드 # 백준 11722 N = int(input()) arr = list(map(int, input().split())) dp = [1]*N for i in range(N): for j in range(i): if arr[i]

문제 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 생각의 흐름 이전에 포스팅한 카드 구매하기 2와 반대로 생각하면 된다. 좀 더 쉽게 말해 그 때 min을 찾았던 것을 max로 수정해주면 된다. 코드 # 백준 11052 N = int(input()) card = [0] card += list(map(int, input().split())) # dp[i]의 값은 i개의 카드를 구매하는데 필요한 최대비용 dp = [0] * (N+1) dp[1] = c..

문제 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 생각의 흐름 단순한 동적프로그래밍 문제이다. dp[i]에 담긴 값이 카드 i개를 고르기 위해 필요한 최소비용이라 하고 계산을 점진적으로 해나아간 뒤 마지막 dp[N]을 출력하면 된다. 깨달은 점 가끔씩 list의 인덱스가 0부터 시작하여 값과의 매칭이 어려운 경우가 있다. 예컨대, 이 문제의 경우 card[0]에는 카드 1개를 고를 때의 값이 담겨 있다. 이런 경우 인덱스를 고려하여 계산하기가 ..

문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net 생각의 흐름 정말 너무 미운 문제다...ㅜㅜ 이거때문에 코딩 그만둘까 생각함... 진짜 꿈에서도 이 문제 푸는 꿈 꾼 듯...정답률이 ..

1월부터 일을 시작하였으니 엄연한 실무를 담당하는 개발자로 일을 한지도 대략 3개월 정도가 되었다. 그닥 긴 기간은 아니지만 느낀 점이 많다. 무엇보다도 학교에서 배우던 이론과 비교하여 실무는 정말 다르다는 것을 새삼 깨달았다. 일을 하게 되면서 생각하던 부분은 과연 좋은 개발자란 무엇일까에 대한 본질적인 고민이었다. 그간 느낀 점들을 정리하면서 그러한 태도들을 가슴에 새기도록 노력을 하고자 이 같은 글을 적는다. 인내심을 기르자 실무에서 코딩을 하면서 느낀점은 코드를 짜는 것은 정말 일부에 불과하다는 것이었다. 정말 이후에 수많은 에러와 싸워야하는데 더 많은 시간들을 보내야 한다. 비즈니스적으로 실무에서 만들어진 프로그램의 규모는 단순히 백준의 프로그래밍 문제와는 다르다. 매우 큰 규모의 코드를 작성한..

문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 생각의 흐름 전형적인 DFS 문제이다. 문제의 요점은 A-B, B-C, C-D, D-E인 친구관계가 존재하는지를 조사하는 것이다. adjacent list를 이용하여 연결관계에 대한 정보를 저장하고 시작점을 vertex 0부터 n-1까지 돌아가면서 dfs를 사용하여 depth가 4이상이 되는 subgraph가 존재하는지를 판별하면 된다. 코드 n, m = map(int, input().split()) adj_lst = [[] for i in range(n)] for i in range(m): a,..

문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마 www.acmicpc.net 생각의 흐름 일반적인 BFS 문제이다. 처음에 행렬을 하나씩 돌면서 1인 곳의 위치 (x,y)를 q에 넣어주고, 여기서 하나씩 빼서 ..

파이썬에서 input을 처리할 때 가령 110 001 010 과 같은 배열이 input으로 들어올 때가 있다. 이를 2차원 list에 넣고자 할 때는 다음과 같이 하면 된다. two_dimen_list = [list(input()) for i in range(3)] 위 실행의 결과값은 [['1','1','0'],['0','0','1'],['0','1','0']]이 된다. 이 외에도 특정한 값으로 2차원 리스트를 초기화하고 싶을 때가 있다. 이 땐 다음과 같이 해주면 된다. two_dimen_list = [[-1]*3 for i in range(3)] 위 실행의 결과값은 [[-1,-1,-1],[-1,-1,-1],[-1,-1,-1]]이 된다.