개발자가 되고 싶은 준개발자

문제 트리를 level 순으로 순회하여 각 레벨 별 노드의 값을 리턴한다. 풀이 이 문제는 트리를 level 순으로 순회하는 문제이기 때문에 BFS(너비 우선 탐색)가 적합하다. 트리의 루트부터 leaf까지 순회를 하면서 한 레벨 씩 리스트에 담는다. 한 레벨 씩 리스트에 담기 위해서는 이전 레벨의 노드들의 리스트를 받아 해당 노들들의 left, right을 리스트에 넣으면 된다. 코드 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class So..

문제 이진 트리가 주어질때, 중심을 기준으로 대칭인지를 결과로 리턴하라. 풀이 이 문제를 푸는 방법은 재귀(recursively)와 반복(iteratively) 2가지 방법이 있다. 우선 재귀로 푸는 방법을 살펴보자. 보통 Tree 문제를 재귀로 풀때에는 root를 확인하고, 왼쪽 서브트리와 오른쪽 서브트리를 확인하는 방식으로 구현한다. 이 문제도 똑같은 방법으로 해결 가능하다. 단, 주의할 점은 대칭임을 확인하기 위해서는 왼쪽 서브트리와 오른쪽 서브트리를 반대로 비교해야 한다. 즉 두 서브트리의 root가 같은지 확인하고, 왼쪽 서브트리의 left가 오른쪽 서브트리의 right가 같은지, 왼쪽 서브트리의 right이 오른쪽 서브트리의 leftt가 같은지 확인하면 된다. 같은 풀이를 iterative하게..

한 줄 평: 넷플릭스의 성공 비결이 궁금한 사람이라면 한 번쯤 읽어보아도 좋을 책! 넷플릭스의 모토는 이 책의 제목처럼 'No Rules Rules'로 설명할 수 있다. 즉, 규칙이 없는 것이 규칙이라는 말이다. 책을 다 읽어 보니 이 말은 반은 맞고 반은 틀리다고 생각한다. 휴가 일수를 지정하지 않고, 법인 카드로 사용할 수 있는 비용의 한도를 지정하지 않는다는 점에서는 규칙이 없다는 말이 맞다. 그러나 넷플릭스는 혁신적인 기업이라는 평가에 걸맞게 그만큼 새로운 규칙들도 많이 만들었다. ('키퍼 테스트'라는 제도를 만들어 '팀원 중 한 사람이 내일 그만두겠다고 하면, 그를 붙잡을 것인가 아닌가'를 모든 팀원들에게 수시로 적용한다. 키퍼 테스트를 통과하면 그 팀원은 회사에 필요한 인재이지만, 그렇지 않다..

요새 애드센스 광고 승인을 받기가 어려워 져서 '애드고시'라는 말이 불었다고 하는데 의외로 쉽게 승인을 받았다! (이제 정식 블로거의 길로~!!) 애드센스 받기 위한 조건 애드센스 승인을 받고자하는 블로그 초보자들에게 도움이 될까하여 정보를 남기고자 한다. 우선 블로그는 시작한지 1주일 정도 되었고, 총 방문자 수는 14명으로 아주 귀엽고 미미한(^^) 방문자 수를 기록했다. 글은 12개 정도 써는데 코딩 관련하여 7개, 책 관련하여 3개를 썼다. 나도 여러 블로그를 살펴 보면서 애드 센스 승인을 받기 위한 조건들을 살펴 보았는데, 일관된 주제의, 적당한 길이의 글을 쓰는 것이 중요하다고 하는 글들을 많이 보았다. 저조한 방문자 수에도 불구하고 승인을 빨리 받을 수 있었던 것은 일관된 주제의 글을 썼기 ..

풀이 작은 문제의 계산 결과를 재사용하여 큰 문제의 결과를 구할 수 있으므로 동적 프로그래밍을 이용하여 풀 수 있다. 특정 날짜에서 받을 수 있는 비용의 최댓값은 그 이전 날짜 중에서 받을 수 있는 비용의 최댓값에 현재 날짜의 비용을 더한 값이 될 수 있다. 단 주의해야 할 점은 '상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다.'라는 제약사항을 고려해야 한다. 따라서 특정 날짜에서 받을 수 있는 비용의 최댓값을 구하기 위해서는 이전 날짜 중에서 최댓값을 더하되, 이전 날짜의 상담이 특정 날짜에는 종료되어 있어야 한다. 코드 import sys # 입력 읽기 n = int(sys.stdin.readline()) t, p, dp = [0 for _ in range(n)..

문제 문자열이 주어지면 이를 키를 이용하여 해독하는 방법의 수를 리턴하는 문제이다. 해독하기 위한 키는 다음과 같다. 'A' -> 1 'B' -> 2 ... 'Z' -> 26 예) "12"는 "AB"나 "L"로 해독될 수 있다. (2가지 방법) "123"은 "ABC"나 "LC"나 "AW"로 해독될 수 있다. (3가지 방법) 풀이 이번 코드는 길이는 짧으나 직관적이지는 않은 것 같다. (더 좋은 방법이 떠오르면 추후에 수정해야 겠다!) 주어진 문자열을 순회하면서 1) 해당 인덱스(i)의 숫자가 1~9의 숫자인지 확인한다. 맞다면 i까지의 방법 개수는 i-1까지의 방법 개수와 같다. (이 문장이 이해가 가지 않는다면 예로 "89"를 생각해 보자. i가 1인 상황을 가정한다. "9"는 1~9의 숫자이므로 1번..

중고 서점에 책 구경하러 갔다가, 출간된지 1년이 아직 안 된 책 코너에서 이 책을 발견하여 집에 데리고 왔다. (나는 중고서점이 일반 서점보다 좋다. 개인적으로 일반 서점에는 모든 출간된 책들이 모여서 좋은 책을 골라내기가 어렵다고 생각한다. 이에 반해 중고서점에는 한번 선택된 책들이 모여 있어서 그런지 좋은 책을 고르기가 상대적으로 수월한 것 같다. 물론 부담없는 가격도 빠른 선택에 한 몫한다.) 제목에서 알 수 있듯이 이 책의 저자는 삼성에서 일하다가 아마존으로 이직을 했다. 책 전반이 삼성과 아마존에 대한 비교인데, 확실한 점은 저자가 아마존을 훨씬 더 좋아한다는 것이다. 대부분의 내용이 '삼성에서는 ~ 방식으로 일을 진행하는데, 이는 ~하기 때문에 좋지 않다. 아마존에서는 이와는 반대로 ~하게 ..

문제 왼쪽 상단 코너에서 오른쪽 하단 코너까지 각 칸에 적힌 수의 합이 최소인 경로를 구해라. 풀이 이 문제를 푸는 데 중요한 포인트는 특정 칸까지의 최소인 경로는 하나만 구하면 된다는 점이다. 그 경로가 어떤 경로인지는 중요하지 않고, 수의 합이 최소라는 점만 중요하다. 따라서 최소의 합을 내는 경로를 구했다면 그 최소의 합만 저장하고, 경로는 저장할 필요가 없다. 따라서 이 문제는 동적 프로그래밍으로 풀기에 적합하다. 각 칸까지의 경로의 최소 합을 저장하고, 다음 칸의 값을 구할 때 이전 값들을 사용하면 된다. 즉, dp[i][j] = min(dp[i-1][j], dp[i][j-1])+ grid[i][j]. (물론, 예외처리는 해주어야 한다.) 코드 class Solution(object): def ..

문제 이전 글에서 푼 Unique Paths(https://june-coder.tistory.com/5?category=913762)에 약간의 제약사항이 추가된 문제이다. 이전에는 시작점에서 도착점까지 가능한 경로의 개수를 구하면 되었지만, 이번 문제에서는 지도에 방해물이 추가된다. 따라서 방해물을 지나지 않는 경로의 개수를 세어야 한다. 풀이 문제 자체는 평이했다. 이전 문제를 푼 방법대로, 특정 지점의 윗 칸과 왼쪽 칸의 경로의 개수를 합하면 된다. 이 문제에서는 방해물이 있기 때문에 왼쪽이나 위에 방해물이 있으면 해당 경로로는 오지 못하는 것을 의미하기 때문에 그 경로를 제외한 나머지 경로를 구하면 된다. 그러나 약간 어려웠던 부분은 예외 처리이다. 만약 [[1]]와 같은 입력이 들어온다면 답은 무..

문제 m*n의 그리드에서 좌측 위 코너에서 우측 아래 코너까지 가는 각기 다른 경로의 개수를 리턴해라. 풀이 그리드의 크기와 같은 테이블을 그리고 각 칸마다 그 칸으로 가는 경로의 총 개수를 기입하면 된다. 이 문제를 동적 프로그래밍으로 풀수 있는 이유는 작은 문제를 풀면 이를 이용하여 큰 문제를 풀 수 있기 때문이다. 문제에는 아래나 오른쪽으로 밖에 가지 못한다는 제약 사항이 있기 때문에, 특정 칸까지 가는 경로의 수는 위의 칸까지 가는 경로의 수와 왼쪽 칸까지 가능 경로의 수의 합과 같다. (어렸을 때 눈높이 학습지를 많이 풀어서 그런지 이 문제가 너무 익숙하다 ㅋㅋㅋ) 코드 class Solution(object): def uniquePaths(self, m, n): """ :type m: int ..