전체 글333

• 

  백준/2667 단지번호붙이기 단지번호붙이기 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 136659 59302 37452 41.223% 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25.. 자바/알고리즘 문제 풀이 2022. 12. 26.

• 백준/1260 DFS와 BFS DFS와 BFS 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 209861 77758 46193 36.039% 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 .. 자바/알고리즘 문제 풀이 2022. 12. 26.

• 

  백준/2606 바이러스 /dfs,bfs 바이러스 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 118785 57140 38448 46.177% 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다... 자바/알고리즘 문제 풀이 2022. 12. 26.

• 백준/24444 알고리즘 수업 - 너비 우선 탐색 1 / bfs 알고리즘 수업 - 너비 우선 탐색 1 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 5928 2629 2202 46.154% 문제 오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자. 너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다. bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점 for e.. 자바/알고리즘 문제 풀이 2022. 12. 26.

• ★백준/24479 알고리즘 수업 - 깊이 우선 탐색 1 / dfs 알고리즘 수업 - 깊이 우선 탐색 1 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 15267 3595 2718 23.026% 문제 오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자. 깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다. dfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점 visi.. 자바/알고리즘 문제 풀이 2022. 12. 26.

• 

  ★ 백준/17299 오등큰수 / 스택, Map 오등큰수 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 10157 4539 3497 44.328% 문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다. Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다. 예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) =.. 자바/알고리즘 문제 풀이 2022. 12. 26.

• 

  ★백준/17298 오큰수 / 스택 오큰수 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 52983 17765 12790 32.613% 문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ .. 자바/알고리즘 문제 풀이 2022. 12. 26.

• 

  ★백준/9935 문자열 폭발/ 스택,리스트 문자열 폭발 다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 (추가 시간 없음) 128 MB 50912 12488 8741 24.596% 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRU.. 자바/알고리즘 문제 풀이 2022. 12. 26.

• 

  ★백준/1655 가운데를 말해요 / 우선순위큐 가운데를 말해요 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.1 초 (하단 참고) 128 MB 46404 13493 10163 30.553% 문제 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에는 백준이가 외치는 .. 자바/알고리즘 문제 풀이 2022. 12. 24.

• 백준/11286 절댓값 힙 / 우선순위큐, Comparator 절댓값 힙 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 (추가 시간 없음) (하단 참고) 256 MB 31694 17683 14442 56.658% 문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배.. 자바/알고리즘 문제 풀이 2022. 12. 24.

• Integer.Min_Value 를 Math.abs 했을때 System.out.println(Math.abs(Integer.MIN_VALUE)); 이 코드를 실행시 -2147483648의 절대값인 2147483648가 나오지않는 이유는 int 형의 최대범위값이 +2147483647 이기 때문이다. https://stackoverflow.com/questions/5444611/math-abs-returns-wrong-value-for-integer-min-value Math.abs returns wrong value for Integer.Min_VALUE This code: System.out.println(Math.abs(Integer.MIN_VALUE)); Returns -2147483648 Should it not return the absolute valu.. 문제해결 2022. 12. 24.

• 

  [Java] 우선순위 큐 (Priority Queue) 우선순위 큐(Priority Queue)란? 큐는 일반적으로 선입선출의 구조이지만 우선순위큐는 우선순위가 높은 순서대로 나가는 구조입니다. 우선순위큐는 최대힙 또는 최소힙을 이용하여 구현됩니다. 최대힙을 이용하고, 숫자 데이터라면 숫자가 큰 순서대로 데이터가 나가고, 최소힙을 이용하고, 숫자데이터라면 숫자가 작은 순서대로 데이터가 나갈것입니다. Priority Queue(우선순위큐) 선언 import java.util.PriorityQueue; //import //int형 priorityQueue 선언 (우선순위가 낮은 숫자 순) PriorityQueue priorityQueue = new PriorityQueue(); //int형 priorityQueue 선언 (우선순위가 높은 숫자 순) Priorit.. 자바/자료구조 2022. 12. 24.