오뚝이개발자

문제 https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 나의 풀이 preorder와 postorder로 트리를 순회하는 것은 쉽다.(모르면 검색을 해보면 금방 나올 것이다.) 이 문제의 핵심은 주어진 정보로 트리를 얼마나 잘 구현하는가이다. nodeinfo를 y좌표에 대해 내림차순, x좌표에 대해 오름차순으로 정렬한다. 정렬된 nodeinfo를 순회하며 각 노드의 자리를 찾아 삽입한다. 문제에서 주어진 조건 중 ..

트리를 순회하는 방법은 preorder, inorder, postorder로 크게 3가지가 있다. 여기서 소개하려고 하는 내용은 이러한 순회를 "어떻게" 구현하는지에 관한 것이다. 가장 보편적인 것은 물론 재귀를 이용하는 것이나, 반복문을 통해서도 얼마든지 구현 가능하다. 참고로 트리노드의 정의는 아래와 같다고 하자. # Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right 편의상 inorder를 구현하는 것으로 한다. 재귀(Recursive)를 통한 구현 class Solution: # ..

문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 www.acmicpc.net 생각의 흐름 인접한 곳들을 탐색하여 그룹을 짓는 문제이다. 특이한 점은 일반적인 상하좌우 이외에도 대각선 4곳까지도 인접한 영역으로 ..

문제 https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수는 N-1보다 많을 수도 있다. 모든 수의 사이에는 연산자를 한 개 끼워넣어야 하며, 주어진 연산자를 모두 사용하지 않고 모든 수의 사이에 연산자를 끼워넣을 수도 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 www.acmicpc.net 생각의 흐름 이전에 포스팅한 연산자 끼워넣기와의 차이점은 연산자의 갯수가 많아졌다는 점이다. 동일한 방법으로 짜도..