문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/87694 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문제 풀이- 격자형 그래프 문제 (BFS)- rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태로 주어진다- 직사각형 외곽 테두리를 통해 시작 (x, y) 에서 도착 (x,y) 까지 최단 거리를 구한다  문제 예시1에서 (3,5) -> (4,5)로 가야하는데 (3,6)으로 가버려서 15(오답)이 나와 시간 소비를 많이 했다..

문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이 요약 1. game_board의 빈 영역(0)과 table의 블록 영역(1)을 구한다2. 빈 영역에 블록이 끼워지는지 회전하며 최대 4번 비교한다3. 블록이 빈 영역에 끼워질 경우 결과값에 블록 크기를 누적하고, 사용처리한다 (2-3 반복)  ① game_board 의 빈 영역(0), table 에 블록 영역(1)을 BFS 로 구한다List> emptySpace = new Arra..

문제링크 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제풀이 "빙산이 2 그룹이상 나눠지지 않고 모두 다 녹았을 때는 0을 출력한다" 조건을 이해하지 못해서 시간 소비 (반성) 절차 1) DFS 로 빙산 그룹을 카운팅한다. - 이때 빙상 그룹을 2그룹 이상 나누지 못하고 0이 된 경우 경우(모두 다 녹은 경우) 0을 출력하고 종료 - 빙상을 녹여 그룹 분할 하기 위해 while문 실행 2) BFS 사용하여 초기화시 빙산 위치를 넣어주..

문제 링크 풀이 - 앞서 풀었던 치즈(2638)에서 조건에 맞게 수정하여 풀었으나 마지막 98%에서 '실패했습니다' 확인 https://dev-ljw1126.tistory.com/243 [BOJ 2638] 치즈 (Java, BFS) 문제 링크 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있 dev-ljw1126.tistory.com - 마찬가지로 공기(0)인 부분에 대해 탐색을 진행하는데, 공기와 접촉한 치즈의 경우 임의 값(2)로 갱신 후 치즈 개수를 카운팅 수행 - while 반복문 시작 하기전 녹아 없어질..

문제 링크 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 - 주어진 조건에 맞게 BFS, 시뮬레이터 구현 하는 문제 - Queue를 활용하여 뱀의 위치 정보를 관리하고, 맵 데이터를 갱신 시켜 줌 게임 조건 게임은 N * N 보드 위에서 진행되고, 게임이 시작할 때 뱀은 맨위 맨 좌측에 위치하고 뱀의 길이는 1이다. 뱀은 맨 처음 오른쪽으로 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. - 먼저 뱀은 몸길이를 늘려 머리를 ..

문제 링크 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 - 격자형 그래프 탐색 문제 - BFS 풀이 - N이 최대 50이므로 O(N^2)으로 풀이 가능 예제 입력 4 3 5 10 10 15 20 20 30 25 40 22 10 예제 출력 4 2 1회차 int[][] WORLD 10 15 20 20 30 25 40 22 10 int[][] GROUP_INFO 0 0 0 0 0 0 1 0 2 1회차 인구 이동 결과 20 20..

문제 링크 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 - 첫 줄 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100) 주어짐 - 치즈 (1), 없는 부분 (0)으로 표시 - 치즈가 모두 녹아 없어지는데 필요한 시간을 출력 - 상,하,좌,우 격자형 그래프 문제 - 시간복잡도 O(N^2) 절차* - 가장 가리(1,1) 위치 부터 시작하여 공기(0)에 대해 BFS 탐색 수행하면 치즈를 만나면 +1 해..

문제 링크 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 해당 문제에 대한 아이디어가 떠오르지 않아, 기술 블로그를 찾아보았고 visit 배열 말고, finish 배열을 활용하여 그래프 노드를 구하는 기법을 알 수 있었다. 풀이 - 각 case 별 사이클 발생하는 인원 수를 구한 후 전체 학생 수와의 차이 구함 - N이 최대 10^5 이기때문에 O(N^2)으로 풀 경우 10^10 이므로 '시간 초과' 발생 가능 - finish 배열 활용하여 이미 ..

문제 링크 https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 문제 풀이 위한 아이디어가 처음 생각나지 않았다. 텀프로젝트(BOJ 9466) 문제 풀이 후 동일하게 visit과 finish배열 활용하여 결과 값을 구할 수 있는 것을 이해하게 되었다. 이런 기법을 어떻게 생각해내는지 대단하다 다들 :) 풀이 - 사이클 발생하거나, 노드가 자신을 가르키는 경우를 구함 - 시간복잡도 : O(N) - (기법*) finish 배열 활용하여 중복..

문제 링크 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 재귀 함수로 그래프 사이클 판별하는 함수가 이해 되지 않아 몇일 소요 - 재귀 함수를 스택으로 생각 - 이미 방문한 적 있고, 부모 노드가 다른 경우 사이클 발생 (=그래프) 풀이 - 케이스별로 정점 N, 간선 M 이 주어질 때 트리의 개수를 구하여 형식에 맞게 출력하게 됨 - 이때 연결된 간선이 없는 정점 또한 트리 개수로 카운팅함 - 재귀 함수 기법을 활용하여 그래..

문제 링크 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 - 주어진 치킨 집 중에 최대 M개 선택(조합)하여, 도시의 치킨 거리의 최솟값을 출력함 - 집의 개수는 N = 50 일때 최대 100개까지 가능 - 치킨집 개수는 최대 M = 13 1) 초기화 치킨집(2)과 집(1)의 좌표를 담은 리스트 구함 2) 치킨집 조합 구하기 조합 (Combination, nCr) : 서로 다른 n개 중에 r개를 중복없이 뽑음, 이때..

문제 링크 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 풀이 - 인접 리스트로 풀 경우 노드와 연결된 간선 정보만 조회 - 시간 복잡도 : O(V + E), 그리고 M번 반복 - Node 클래스 정의 후 양방향 그래프 표현 예제 입력에 따라 거리 값을 구하면 아래와 같다 # 시작, 끝 = 1, 2 [0, 0, 2, 5, 3] # 시작, 끝 = 3, 2 [0, 5, 7, 0, 2] 제출 코드 import java.util...

문제 링크 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 풀이 - 순열 (permutation) : N개 중 중복없이 N개를 나열하였을 때 최대값을 구함 - 최대치 8P8 = 8! = 40320 이기 때문에 DFS 로 구현 가능 예제 입력 1에 대한 순열을 구할 경우 아래와 같은 형태로 나옴 #입력 6 20 1 15 8 4 10 #순열의 경우 [20, 1, 15, 8, 4, 10] [20, 1, 15, 8, 10, 4] [20, 1, 15, 4, 8, 10..

문제 링크 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 풀이 - 역의 수 N, 한 하이퍼 튜브가 서로 연결하는 역의 개수 K, 하이퍼 튜브의 개수 M이 주어짐 (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) - 시간복잡도 O(V + E) 실패* 처음에 연결한 역 번호를 가지는 하이퍼 튜브와 연결된 하이퍼 튜브 번호를 가진 역 노드를 생각해서 List 2개 선언하여 풀었는데 '시간초과' 발생 확인 아이..

문제 링크 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 - BFS 로 각 노드에 대한 색상 (0, 1)을 번갈아 가며 지정 - 이때 연결된 노드의 색상이 동일한 경우 이분 그래프가 아님 - 테스트 케이스별로 BFS 탐색시 시간 복잡도 O(V + E) 만큼 시간 소요 실수 - 양방향 그래프 설정을 하지 않고 탐색을 해서 틀림 이분그래프 개념 참고 https://gmlwjd9405.github.io/2018/08/23/algorithm-b..

문제 링크 https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 풀이 - BFS 그래프 탐색 문제 - 첫 줄에 S, T 가 주어짐 (1 ≤ s, t ≤ 10^9) - 현재 값과 연산자를 담은 Object를 정의해서 Queue에 담아 처리하도록함 에러 - 만약 배열 선언시 최대 10^9 까지 있기 때문에 '메모리 초과' 발생 - 나누기(/) 연산시 값이 0 인 경우 '/ by zero' 에러 발생 실수 - Set을 사용하여 이미 구한 값 여부 ..

문제 링크 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A A 로 감소 시키면서 카운팅 처리하도록 풀이 1) 2 를 곱하는 경우는 => 2로 나누어지는 경우 2로 나누기 2) 끝자리에 1을 붙이는 경우는 => 끝자리가 1인 경우 10 으로 나누기 (*Java 에서는 실수값 나누기할 경우 실수만 취급) *실수 B 값이 2로 나누어지지 않거나, 끝자리가 1이 아닌 경우는 답을 구할 수 없으므..

문제 링크 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 - N * N 행렬 주어짐 (K 는 바이러스 번호인데, 사용하지 않음) - 상,하,좌,우 격자형 그래프 탐색 문제 - 아래 조건에 따라 바이러스는 번호와 초에 따라 정렬된 상태에서 탐색이 진행되야 함 (*실수 부분) 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다 - 따라서 Java에서 제공하는 우선 순위 큐(PriorityQueue) ..