Problem Solving (67) 썸네일형 리스트형 백준 4256 트리 https://www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 글을 2~3일에 하나씩 올리고 싶은데, 그것도 보통 힘든게 아닌 것 같다. 사실 다른 내용도 많이 담아야 하는데, 그동안 미뤄둔 백준 문제가 너무나 많기에 계속 이렇게 조금씩 올리고 있다. 트리를 다루면 전위 순회, 중위 순회, 후위 순회에 대한 것을 금방 맞닥뜨리게 된다. 너무나도 전형적인 문제이기 때문이다. 이 문제가 바로 그것이다. 재귀함수에 대한 이해를 하기도 좋고, 트리구조에 .. 코드와 선형 구조에 대한 생각 코드를 보면 줄바꿈과 인덴트가 있다. 줄바꿈은 무엇일까? 명령과 명령 간의 분리를 뜻하기도 하고, 줄 번호에 따라서 실행 순서를 뜻하기도 한다. (비동기 처리는 일단은 논외로 한다.) 아마도 마지막에 line break가 있는지를 보고 줄바꿈을 파악할 것이다. 하지만 이렇게만 쓴다면 '갈래' 또는 '영역'을 표현할 수 없다. 순차적으로 실행되는 명령 리스트만 적을 수 있을 것이다. 왼쪽의 그림을 보자. 저런 식으로 조건에 따른 갈래가 생긴다면 코드상에서 v>1? v=5 v=0 이런식으로 쓸 수 없다. 이제 이를 표현하기 위해 뭔가 새로운 표현법이 필요해진 것이다. 하지만 코드를 쓰는 공간에서는 그림을 그리는 것이 아니고 텍스트기에 뭔가 아이디어가 필요하다. 그것을 해결해주는 것이 바로 인덴트인 것이다. .. LeetCode 756 Pyramid Transition Matrix - with Trie (트라이) https://leetcode.com/problems/pyramid-transition-matrix/ Pyramid Transition Matrix - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 필자는 재귀 안에 또 다른 재귀가 돌아가야하는 구조로 생각하였다. 근데 그렇게 하여도 시간초과가 나서 트라이 구조까지 끼얹었다. 가장 바닥에 있는 문자열(문제에서는 bottom으로 표현)이 주어졌을 때, 일단 다음 bottom을 만들어야 한다. 필자는 풀이에서 bot.. LeetCode 1367 Linked List in Binary Tree https://leetcode.com/problems/linked-list-in-binary-tree/ Linked List in Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제에서 이진트리에서 사용될 노드와 링크드리스트의 각 노드 구현 방식이 주어진다. 이제 문제해결을 위해 각 케이스들에 대해 생각해 봐야한다. 그리고 필연적으로 재귀함수를 사용하게 될테니, 기저조건(종료조건, 탈출조건)에 대해 먼저 생각해 본다. 문제의 Constr.. LeetCode 알고리즘 PS에 대한 생각 릿코드(리트코드, LeetCode)에도 많은 문제들이 있고, 특히 해외에서는 상당히 보편적으로 사용하는 플랫폼으로 알고 있다. 릿코드의 시스템에도 장단점이 있는데 몇가지만 짚어보면, 문제를 틀렸을 경우, 어떤 테케에서 틀렸는지 공개된다. 이 점은 시간단축의 효과(장점)가 있다. 어디서 잘못했는지 금방 알 수 있다. 때때로 정말 작은 실수때문에 며칠이 걸리기도 한다. 그런 실수, 그런 코너케이스까지 생각해내야 하는 것도 맞지만 그것으로 너무 많은 시간을 뺏기는 것도 문제가 있다. 실제로 개발자들이 코드리뷰, 페어 프로그래밍 등의 방식을 고안하고 적용하는 것도 이러한 문제를 해결하기 위함이 아닌가? 하지만 동시에 이것은 단점도 된다. 스스로 생각해내는 기회를 앗아가기 때문이다. 필자도 (요새 이 '필자'라는.. 백준 1967 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 트리의 기본 성질 중 하나를 알고 있으면 풀이를 도출하는 게 보다 수월하다. '트리는 어떤 정점을 루트(기준)로 삼아도 트리의 형태로 만들 수 있다.' 이 말이 무엇인지 이해하기 위해 아래 그림을 보자. 위의 그림은 문제에 나온 트리이다. 정점 1이 루트에 있다. 앞서 말한 '어떤 정점을 루트로 삼아도 트리의 형태가 된다'를 확인해보자. 위의 그림과 같이 같은 트리를 6번 정점.. 백준 1918 후위 표기식 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 전형적인 스택 활용 문제이다. 스택을 사용할 수 있는 문제/경우들에는 항상 어떠한 순서나 우선순위와 같은 개념이 묻어있다. 스택이 비어있다면 스택에 값을 담고, 값이 있다면 우선순위를 체크하여 어떤 걸 처리할지 정한다. 이 문제처럼 괄호없이도 연산 순서를 표현하는 후위 표기식 표현이나 증가/감소 수열 구하기 등등 반드시 경험해야할 문제중의 하나라고 생각한다. 스택을 활용하게 되면 보통 O.. 백준 9658 돌 게임 4 https://www.acmicpc.net/problem/9658 9658번: 돌 게임 4 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 이 문제에 앞서 반드시 이전 포스팅(돌 게임 3)을 참조 부탁드린다. 이전 문제(돌 게임 3)에서처럼 이번에도 같은 로직을 적용할 수 있다. 이전 포스팅에서 SK, CY으로 그림 상의 테이블을 채웠는데, 이번엔 전자와 후자로 표현하겠다. 그게 더 올바른 의미이기 때문이다. 길이 1000+1의 DP배열을 먼저 만들어둘 수 있다. 이제 그 배열을 0과 1로 채울텐데 편의상 0이면 전자 승(상근이가 먼저 두므로 상근이의 승리) 1이면 후자 승(창영이의 승리)이 되겠다. 그리고 이전 포스팅에서도 거듭 강조했듯이 이 배열을.. 이전 1 2 3 4 5 ··· 9 다음
