감자튀김

https://www.acmicpc.net/problem/24479문제첫째 줄에 정점 개수 N ( 5 ( 1 ( 1 둘째 줄부터 M개의 줄에 간선의 정보 u v ( 1   N, u != v) 가중치 1인 양방향 간선이 주어진다.첫째 줄부터 N개의 줄에 정수를 한 개씩 출력하는데 i번쨰 줄에 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 순서를 1로 시작하며, 시작 정점에서 방문할 수 없는 경우 0을 출력한다.방문 순서는 오름차순으로 방문하도록 한다. 최종 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Co..

https://www.acmicpc.net/problem/2263 문제첫째 줄에 정점 개수 V ( 2 둘째 줄에는 인오더, 셋째 줄에는 포스트오더가 주어지는데 각 줄에는 n개의 숫자를 공백으로 구분하여 입력된다.인오더와 포스트오더를 이용하여 프리오더를 만들어 출력한다. 최종 코드 import java.io.*;import java.util.StringTokenizer;public class Main { public static int[] inorder; public static int[] postorder; public static int[] preorder; public static int index = 0; public static void tree(int il, int i..

https://www.acmicpc.net/problem/1167문제첫째 줄에 트리의 정점 개수 V ( 2 둘째 줄부터 V개의 줄에 간선의 정보가 주어진다.정점 번호는 1부터 V까지 매겨진다.간선의 정보는 정점 정보와 간선 정보의 정수 두 개로 연속하여 입력되고 각 줄의 입력의 마지막에는 -1이 들어온다.임의의 두 점 사이의 거리 중 가장 긴 것의 거리를 답으로 출력한다.트리의 지름 1967번과 다를 게 별로 없는 것 같은 문제이다. 다만 트리의 정점 개수에서 차이가 있다.1967번은 트리의 정점이 최대 10000개이고 1167번은 트리의 정점이 최대 100000개로 10배 차이가 나서 똑같이 푼다면 시간 초과가 난다.시간 초과를 피하기 위하여 노드의 개수를 줄일 어떠한 조건이 더 필요한 문제이다.   ..

먼저 둘 다 어느 때 사용하는 지 구분하자면모든 정점을 방문해서 뭔가를 해야 될 때는 둘 중 어떤 알고리즘을 써도 괜찮다. 경로의 특징을 저장할 때 ( ex. 경로의 가중치를 저장하여 사용 ...) 는 당연히 경로를 연결할 수 있는 DFS를 사용한다.BFS는 노드가 연결된 방향대로 진행하지 않기 때문에 경로가 없어 사용할 수 없다. 최단거리나 최단 경로에는 BFS를 사용한다.DFS를 사용하기엔 DFS는 한 방향으로 나아가 트리의 끝까지 진행하기 때문에 시간이 더 오래 걸리는 듯 하다. 그리고 작은 그래프에는 BFS를 사용하고, 아주 큰 그래프에는 DFS를 사용한다.  공통적으로 두 함수에 필요한 부분은1. 노드의 방문 여부를 나타내는 boolean 배열2. 트리의 정점과 노드를 2차원 연결 리스트로 변환..

https://www.acmicpc.net/problem/4803 문제입력은 여러 테스트 케이스로 이루어져 있다.각 테스트 케이스의 처음에는 정점의 개수 n ( 1 이후 m개의 줄에 간선을 나타내는 두 개의 정수가 주어지며 같은 간선은 여러 번 주어지지 않는다.입력의 마지막 줄에는 0 0 이 주어진다. (프로그램 실행 종료)  일단 내 방법대로 한 최종 코드 (그럴 사람은 없겠지만 혹시나 보더라도 따라하지 마세요 진짜 구립니다.)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer;public..

https://www.acmicpc.net/problem/1967문제입력으로 자연수 N ( 1 둘째 줄부터 N - 1개의 줄에 간선에 대한 정보(부모 노드, 자식 노드, 간선 가중치(1 루트 노드 번호는 항상 1이다. 풀이 과정 1. 트리이기 때문에 dfs와 bfs 중 무엇을 사용할 것인지 정해야 됨. -> 이 문제는 간선의 가중치를 사용하는 문제이고 경로를 이용하는 문제이기 때문에 dfs를 사용해야 된다.2. 트리는 양방향으로 연결된 리스트이기 때문에 입력된 내용을 배열로 옮길 때 부모 노드에서 자식 노드로 가거나 자식 노드에서 부모 노드로 갈 수 있도록 양쪽 모두에 해당 노드들을 등록해야 된다.3. dfs 함수를 만들 때 재귀 함수로 만들 것이기 때문에 간선 가중치의 합을 저장하며 비교할 부분이 필요..

https://www.acmicpc.net/problem/1644문제입력으로 자연수 N ( 1 입력된 자연수 N을 연속된 소수의 합으로 표현할 수 있을 경우 정답으로 출력할 변수를 1 증가시킨다.모든 연속된 소수의 합을 모두 살펴보고 마지막으로 정답 변수를 출력한다. 투 포인터에 중점을 둔 문제 풀이 방법이다.같은 지점에서 출발하여 같은 방향으로 나아가는 두 개의 포인터를 만들어 진행한다. 에라토스테네스의 체를 이용하여 N까지의 소수를 구한 후 ArrayList에 추가하여 1부터 N까지의 소수가 담긴 배열을 만든 뒤 시작한다. 0에서부터 시작해서 같은 방향으로 인덱스를 이동하며 전체를 탐색하며 조건을 비교할 수 있도록 한다.포인트 두 개를 p1과 p2로 지정하고 p1을 먼저 이동시키며 sum 변수에 더하..

https://school.programmers.co.kr/learn/courses/30/lessons/161988문제입력으로 sequence ( 1 sequence.length  500000, -100000  )이 입력으로 들어옴.펄스 수열 [1, -1, 1, -1, ..., -1, 1, -1], [-1, 1 -1, ..., 1, -1, 1] 처럼 1과 -1이 연속적으로 번갈아 나오는 수열.입력으로 들어온 sequence 수열에 펄스 수열을 곱해 부분 수열의 합 중 가장 큰 것을 return. 초기 코드class Solution { public long solution(int[] sequence) { long answer = 0; int[] sum = new..

https://school.programmers.co.kr/learn/courses/30/lessons/49189 문제입력으로 n ( 2  10000 )과 s ( 1  )이 입력으로 들어옴.각 원소의 합이 s가 되는 수의 집합, 이 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합. 을 최고의 집합이라고 함.최고의 집합을 오름차순 정렬된 1차원 배열으로 return 할 것.  초기 코드import java.util.Arrays;class Solution { public int solution(int n, int[][] edge) { int answer = 0; int[] result = new int[n + 1]; for (int i = 0; i..

https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  문제 표현이 가능한지 확인할 숫자가 들은 Long 배열 numbers ( 1 1  )가 입력으로 들어옴.배열에 있는 숫자를 이진수로 바꾸어 이진 트리에 추가하여 해당 수를 판별하는데 이 때 숫자를 하나의 이진트리로 해당 수를 표현할 수 있다면 1을 결과 배열에 추가하고, 표현할 수 없다면 0을 결과 배열에 추가하여 return한다. 배열에 있는 숫자를 이진수로 바꾸어 이진수가 포화 이진트리 (완전 이진트리)가 될 수 있도록 문자열 앞에 0을..