본문 바로가기

전체 글

 (268)
[백준 java] 1068 - 트리 BFS를 사용하여 Leaf를 구하도록 구현하였다 주의할점은 1. 트리의 시작점은 여러개일 가능성도 있다 (여러개 트리) 2. 트리의 시작점은 꼭 0번째에 위치하지 않는다 둘째줄 0~N-1노드를 입력받을 때 입력값이 -1 이면 바로 큐에 담아주고 방문처리를 한다. 셋째줄 삭제할 노드를 입력받고 해당 노드를 가리키는 자식노드들을 재귀함수를 통해 모두 삭제처리를 해주었다. (직접 삭제가 아닌 삭제 노드에는 -2의 값을 주었다) searchLeaf에서는 삭제된 노드 -2를 만나면 건너뛰고 방문하지 않은 자식노드를 찾으면 큐에 넣어준다. (해당 노드는 자식노드가 있으니 isLeaf는 false) 자식노드를 찾지못하면 Leaf 수를 ++ 해줘서 리프노드의 수를 구하였다 여러가지 반례 //ex1 4 -1 0 1 2 ..
[백준 java] 10845 - 큐 바로 전 문제 스택과 거의 같은 문제이다. 스택에서는 그냥 스택을 사용하여 풀었는데 이번에는 직접 큐 처럼 동작하는 배열을 만들어서 구현했다. 큐는 선입선출이므로 먼저 들어온 값을 삭제한다. 여기서는 직접 삭제하지 않고 보여줄 부분을 변경 우선 배열의 보여줄 부분 시작점 start , 끝점 last 으로 두고 push 시 배열의 last 인덱스에 추가후 last를 ++ pop 에는 직접 삭제를 하지말고 큐의 last인덱스를 보여주고 보여줄 start를 ++한다. size 해당 큐의 크기는 last- start 이다 (배열을 직접 삭제하지않고 보여주는 부분만 바꿨기때문) empty start back 은 사이즈에 따라, 즉 last-start 이 0인지 아닌지에 출력을 바꿔준다. import java.io..
자료구조 알고리즘 -1주차 백준 자료구조 알고리즘 15문제 풀어보기 문제집: 자료구조 (sotjs12) www.acmicpc.net 1주차
[백준 java] 10828 - 스택 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 블로그 - 전체 글 여러가지 언어와 입력 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다. 방법: 첫째 줄에 정수의 개수 N (= 10,000,000), 둘째 줄부터 N개의 줄에 한 개의 자연수(10,000 이하)가 적힌 파일 www.acmicpc.net 위 블로그에서 입력속도 비교글을 한눈에 볼 수 있다. BufferReader로 입력을받고 "push 정수" 를 스페이스바로 구분하기위해 StringTokenizer를 사용하였다 출력은 ..
[백준 java] 9935 - 문자열 폭발 진짜 폭발시키고 싶은 문제 String replace를 사용하면 O(N^2) 번의 시간복잡도가 발생하므로 Stack을 사용하는 방법으로 풀어야한다. (문자열 탐색후 지우고 다시 처음부터 탐색하기 때문) 폭발 문자열 = B 1. 입력값을 char[]로 받은 후 스택에 처음부터 하나씩 넣는다 2. 만약 스택 사이즈가 B보다 크다면 3. 스택에 넣은 값에 B의 길이만큼 뺀 값과 B를 한글자씩 for문으로 비교한다 4. 만약 explosion = true 라면 B의 길이만큼 스택에서 버린다. (선입선출) 계산 후 for문을 사용하여 값을 출력했는데 여기서 또 시간초과가 발생했다 for문을 사용하여 출력할때도 O(N^2) 번의 시간복잡도가 발생해서 그렇다 시간 복잡도, 입출력 시간복잡도, 입출력 velog.io ..
시간 복잡도 관련 참고할 글 여러가지 알고리즘 문제를 풀면서 해당 문제를 제한시간 안에 끝낼 수 있을지? 알고 모르고가 굉장히 중요하단걸 체감하고있다. https://coding-factory.tistory.com/608 [Algorithm] 알고리즘 시간복잡도에 대하여 시간복잡도란? 시간 복잡도란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다. 같은 결과를 가져오는 프로그래밍 소스도 어떻게 작성하느냐에 따라 걸리는 시간이 달라질 coding-factory.tistory.com https://noahlogs.tistory.com/27 빅오 표기법 (big-O notation) 이란 컴퓨터 과학(Computer Science) 에서 알고리즘은 어떠한 문제를 해결하기 위한 방법이고, 어떠한 문제를 해결 하기 위한 방법..
[백준 java] 1717 - 집합의 표현 (Union-find) 집합의 수는 0을 포함한 N+1 개의 집합을 가진다. Union-find 알고리즘을 사용하여 문제를 해결했다. 합집합 찾기라는 의미를 가진 알고리즘으로, 두 개의 노드를 집어 두 노드가 같은 그래프에 속하는지 판별한다. Find 는 입력한 수가 어떤 집합에 포함되어있는지 부모를 찾아준다 (재귀함수를 사용하여 부모를 찾을때까지 타고 올라간다) Union 은 두 수 a와 b가 포함되어 있는 집합을 합쳐준다. 두 값을 비교하여 더 작은 값의 부모노드로 합쳐준다 부모가 p[1] = 1 과 p[2] = 2인 노드를 합치면 p[2] = 1로 연결되며 더 작은 1번노드를 가리키게 된다 for문으로 M개의 입력(m,a,b)을 받으며 첫번째 숫자의 m이 0이면 a,b를 union 첫번째 숫자m이 1이면 a,b를 각각 f..
1717-집합의 표현 (오답) 1. M(연산의 수)이 10만개이므로 2중 for문을 사용하여 리스트를 합쳐주는것은 O(N^2)시간이 걸린다. 2. 집합의 수가 1~100만개지 집합 수의 범위가 1~100만이 아니기때문에 0도 포함되어야한다 (0을 포함안시키고 수행) 시간복잡도를 다시한번 생각해보고 다른 방법을 찾아봐야겠다 import java.util.*; public class B1717 { static int N,M,p,a,b; static ArrayList Board; public static void main(String[] args) { Scanner sc= new Scanner(System.in); N = sc.nextInt(); M = sc.nextInt(); Board = new ArrayList(); for(int i..

티스토리툴바