DFS

[LeetCode] 124. Binary Tree Maximum Path Sum

124. Binary Tree Maximum Path Sum Hard A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum p..

[LeetCode] 22. Generate Parentheses

22. Generate Parentheses Medium Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Example 1: Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"] Example 2: Input: n = 1 Output: ["()"] Constraints: 1 cnt2: dfs(cnt1, cnt2 + 1, temp + ')') dfs(0, 0, '') return res

[BOJ] 백준 문제풀이 15649 N과M(1)

알고리즘 스터디 :DFS와 BFS 기초를 다지기 위해서 쉬운 문제 부터 하나하나 차근차근 접근 해보려고 합니다. 종만북은 문제 풀이로 병행을 하려하고, 나머지는 이제 하나하나 볼 것입니다. 우선, DFS 문제를 푸려고 하는데, 제 코딩 스타일이 알고리즘에 최적화 되있지 않다고 조언을 들었습니다. 시간 단축과 알고리즘 구현 단순화를 위해서STL을 같이 공부할거에요. 암튼 ... 아래 문제를 풀었습니다. N과 M (1) 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초512 MB129480457265.148%문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열입력첫째 줄에 자연수 N과 M이..

[알고리즘 문제 해결 전략] Part 1. 6장 무식하게 풀기

알고리즘 문제해결 전략 1 권, 흔히 불리는 이름은 종만북 ! 그럼 이제,,, 시작.. ( 내 글이랑 문제 글 색이랑 같아서 색을 수정 했다... ) 6장 무식하게 풀기, 완전 탐색? 으로 모든 경우의 수를 찾아서 답을 찾아내는 방식 1. 예제 : 보글 게임 (문제 : ID : BOGGLE, 난이도 : 하)https://algospot.com/judge/problem/read/BOGGLE 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다시 지나..

1799 백준 비숍 백트래킹

초등부가 왜 이렇게 어렵나...혼자서 dfs 하려다가 말아먹고 , 결국 다른분 코드 참고해서 만들었다.문제는 아래와 같다. 원래 비숍이 놓일때마다 4방향의 대각선을 다 검색하는 방법을 사용하려고 했는데 , 시간초과가 나는 사람이 있다고도 하고무식한것 같아서 방법을 찾다가, 체스판의 대각선을 2부분으로 나눠 푸는 것을 발견했다. * 체스판을 N * N의 격자가 아니라, 2N 개의 대각선으로 바라보는 방법입니다.대각선으로 체스판을 보게 되면 다음 두가지 이점이 있습니다.1. 현재 대각선에서 비숍을 하나만 놓고 다음 대각선으로 이동하면 됩니다. 2. 현재 대각선의 어떤 위치에 비숍을 놓을 수 있는가의 검사는 반대 방향의 대각선에 비숍이 놓여졌는지를 확인하는것으로 O(1)에 수행할 수 있습니다. 이렇게 푸는 방..