알고리즘/백준
백준 5587 - 카드 캡터 상근(Java)
www.acmicpc.net/problem/5587 5587번: 카드 캡터 상근이 1번째 줄에 상근이의 점수를 출력하고, 2번째 줄에 근상이의 점수를 출력한다. www.acmicpc.net 1. 유형 구현 2. 자료구조 우선순위큐 3. 기능 - 상근카드, 근상카드 나누기 - 타겟카드 보다 큰지 작은지 판단하는 함수 4. 풀이 조건에서 가장 작은 카드부터 출력해야하기 때문에 우선순위큐를 선언 그 다음은 큐에서 하나씩 수를 빼와서 타깃과 비교하면 끝. 코드. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Pri..
백준 18428 - 감시 피하기(Java)
www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 1. 유형 시뮬레이션 2. 자료구조 어레이리스트 3. 기능 - 2차원 배열에서 3개 선택 (조합) - 한 방향으로 끝까지 탐색하기 4. 풀이 N*N의 맵에서 3개를 선택하는 경우의 수는 8000 아래다. 즉 브루트포스로 푸는 것이 가능. 2차원 배열에서 조합을 구하는 방법은 순서대로 0~N*N-1까지의 수를 한칸마다 할당. 이때 row는 k/N, col는 k%N 공식이 나온다. k가 2, N이 5라고 ..
백준 18249 - 근손실(java)
www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 1. 유형 구현, 백트래킹 2. 자료구조 없음 3. 기능 - 순열 4. 풀이 - 재귀를 사용해서 순열을 구한다. 다음 재귀를 호출할 때, 500미만이면 백트래킹 코트. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; publ..
백준 2310 - 어드벤처 게임(Java)
www.acmicpc.net/problem/2310 2310번: 어드벤처 게임 입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타 www.acmicpc.net 1. 유형 그래프, 구현, 재귀 2. 자료구조 - 어레이리스트 3. 기능 - 인접리스트 만들기 - E,L,T 조건에 맞게 통과시키기 4. 풀이 재귀의 매개변수로 소지금, 현재노드를 주고 ELT 조건에 맞게 소지금을 변경해 주면 된다. 코드. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRe..
백준 3987 - 보이저 1호(Java)
www.acmicpc.net/problem/3987 3987번: 보이저 1호 첫째 줄에 시그널을 보내는 방향을 출력한다. (U: 위, R: 오른쪽, D: 아래, L: 왼쪽) 만약, 방향이 여러 가지가 존재한다면, U, R, D, L의 순서 중 앞서는 것을 출력한다. 둘째 줄에는 가장 긴 시간을 출 www.acmicpc.net 1. 유형 구현 2. 자료구조 없음 3. 기능 - 방향 바꾸기 - 무한대 판단 방향은 그냥 노가다로 16가지 경우의 수를 모두 구현 무한대는 맵 크기가 500*500이니깐 250001번이 나오면 무한대이다. 코드. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; im..
백준 17225 - 세훈이의 선물가게(Java)
www.acmicpc.net/problem/17225 17225번: 세훈이의 선물가게 첫 줄에 상민이가 선물 하나를 포장하는 데 걸리는 시간 A, 지수가 선물 하나를 포장하는 데 걸리는 시간 B, 어제 세훈이 가게의 손님 수 N(1 ≤ N ≤ 1,000)이 주어진다. 이후 N개의 줄에 걸쳐 1번부 www.acmicpc.net 1. 유형 우선순위큐, 구현 2. 자료구조 우선순위큐, 어레이리스트 3. 기능 - 우선순위 정하기 - 큐에 넣기 - 시작하는 시간 찾기 4. 풀이 일단 클래스 필드값으로 시작시간, 포장지색을 선언한다. 그리고 우선순위는 시작시간을 오름차순으로 정한다. 예외는 서브태스크 2 같은 경우다. 시작시간이 같은경우가 있다. 그때는 색깔 순서대로 상민이가 먼저 오도록 정한다. 큐에 넣는 것은 ..
백준 13022 - 늑대와 올바른 단어(Java)
www.acmicpc.net/problem/13022 13022번: 늑대와 올바른 단어 첫째 줄에 단어가 주어진다. 단어는 w, o, l, f로만 이루어져 있으며, 길이는 50을 넘지 않는다. www.acmicpc.net 1. 유형 문자열, 구현 2. 자료구조 HashMap 3. 기능 - w o l f 순서로 연속하는지 - 각 단어가 같은 횟수씩 나왔는지 확인 - 한 싸이클이 끝날때를 확인 4. 풀이 문제는 간단하지만 너무 노가다 스러운 문제였다. 우선 w o l f를 해쉬맵을 사용해서 0 1 2 3 으로 파싱한다. 그러면 그전 단어와 현재 단어를 비교해서 연속하는지를 알 수 있음. 각 단어를 탐색하면서 count배열에다가 각 단어가 몇번 나왔는지를 기록 만약 (현재 - 이전)이 -3일 경우 즉, 0 -..
백준 1922 - 네트워크 연결(Java)
www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 1. 유형 그래프, 구현, MST 2. 자료구조 우선순위큐, 어레이리스트 3. 기능 - 인접리스트를 만들어서 가중치 그래프 만들기 - 프림알고리즘 4. 풀이 프림알고리즘만 알고 있었다면 쉽게 풀 수 있는 문제. minRute[N+1]-> N까지 연결된 가장 짧은 가중치를 넣는다. minRute보다 더 짧다면 갱신 시켜준다. 끝. 코드. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; ..
백준 18405 - 경쟁적 전염
www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 1. 유형 구현, 우선순위큐, bfs 2. 자료구조 우선순위큐 3. 기능 - 바이러스 4방향 퍼뜨리기 - S초후 멈추기 4. 풀이 문제에서 주어진 조건대로 바이러스는 오름차순으로 퍼진다. 그렇기 때문에 Comparable을 사용해서 우선순위큐에 집어 넣는다. 그리고 4방향으로 bfs돌리면 끝. 주의할점은 S초 후에 멈춰야 한다. 그렇기 때문에 우선순위큐를 cur, next 만든다음..
백준 1756 - 피자 굽기(Java)
www.acmicpc.net/problem/1756 1756번: 피자 굽기 첫째 줄에 오븐의 깊이 D와 피자 반죽의 개수 N이 공백을 사이에 두고 주어진다. (1
백준 9944 - NxM 보드 완주하기 (Java)
www.acmicpc.net/problem/9944 9944번: NxM 보드 완주하기 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 www.acmicpc.net 1. 유형 구현, 백트래킹, dfs 2. 자료구조 - 딱히 없음 3. 기능 - EOF로 입력받기 - 처음 구슬 시작점 설정 - 벽 만날때 까지 이동 벽 만난 경우 제자리에서 벽 부딪힌 경우 이동하다가 벽 부딪힌 경우 - 재귀를 나와서 방문배열 복구 4. 풀이 구슬 시작점은 2중 탐색으로 벽이 아닌 위치에서 시작 4방향 탐색하면서 while문을 돌려서 벽인경우, 맵 이탈하는 경우, 중복하는 경우에서 반..
백준 18808 - 스티커 붙이기(Java)
1. 유형 구현 2. 자료구조 - 3차원 배열(스티커 저장) 3. 기능 - 90도 돌리기 - 노트북에 붙이기 - 붙일 수 있는 위치 찾기 4. 풀이 90도를 돌릴때 생각할 점은 스티커가 직사각형 이라는 점이다. 때문에 일반적으로 90도를 돌리는게 아니라 배열의 크기를 가로 세로를 바꾼다음 다시 설정해야 한다. 그 후, 90도 돌리기 노트북에 붙이는 것은 노트북을 2중 탐색하면서 하나씩 비교해준다. 노트북이 비어있고 스티커가 1이라면 붙 일 수 있다. 스키티커를 전부 다 붙일 수 있다면, flag값을 사용해서 다음 스티커로 넘어간다. 마지막에 노트북을 2중 탐새해서 1의 갯수를 세어준다. 코드. import java.io.BufferedReader; import java.io.IOException; imp..
백준 17472 - 다리 만들기2 (Java)
www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 1. 유형 구현, 프림알고리즘, bfs 2. 자료구조 섬들의 연결관계 ArrayLIst 프림알고리즘 PriorityQueue 3. 기능 - 섬들을 번호로 구분 - 섬들끼리 거리 - 섬들을 그래프로 표현하기 - 프림 알고리즘으로 섬들간의 최소 거리 구하기 - 연결이 안 된것 탐색 4. 풀이 위에 있는 기능 하나하나는 골드5 정도의 수준인것 같다. 하지만 저것들을 전부 한 문제에 때려 넣어서 ..
백준 15787 - 기차가 어둠을 헤치고 은하수를 (Java)
www.acmicpc.net/problem/15787 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net 1. 유형 구현, set 2. 자료구조 Set 3. 기능 - 명령어 구현 - 중복 판단 4. 풀이 기차의 손님은 boolean의 2차원 배열로 구현 HashSet을 사용해서 중복을 판단. 기차가 true일 경우 1, false면 0으로 String을 만든 후, set에 집어 넣음. set의 사이즈가 정답. 끝 코드. import java.io.BufferedReader; import java.io...
백준 13335 - 트럭(java)
www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 1. 유형 구현 2. 자료구조 ArrayList, 큐 3. 기능구현 트럭을 한칸 씩 앞으로 트럭중 다리 벗어난거 제외 다음 트럭이 다리에 올라 올 수 있다면 올려놓기 4. 풀이 Pair의 필드값으로 트럭의 무게, 다리에서 흘러간 시간을 설정한다. 반복문은 주어진 트럭이 전부 다리에 올라온 시점에서 반복문 탈출 그리고 3번의 기능들을 순서대로 반복문 안에서 구현해 ..
백준 5567 - 결혼식(java)
www.acmicpc.net/problem/5567 5567번: 결혼식 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다. www.acmicpc.net 1. 유형 그래프, 구현 2. 자료구조 양방향 인접리스트(arrayLIst배열) 3. 기능 - 인접리스트 만들기 - 재귀를 통해 깊이 2까지 탐색 - 탐색중 중복은 배제 4. 풀이 일단 인접리스트를 만든다. 그 후, 재귀를 통해 연결된 친구를 탐색. 다만 깊이가 3이 됐을때, return을 함. 코드 import java.io.BufferedReader; import java.io.IOException; imp..
백준 1713 - 후보 추천하기(java)
www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1≤N≤20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 www.acmicpc.net 1. 유형 우선순위 정렬, 구현 2. 자료구조 ArrayList 3. 기능 N개의 프레임 중에서 중복된 것을 찾기 -> 추천수 업 중복되지 않으면 -> 앞에꺼 제거후 푸쉬 N개가 다 채워졌는지 탐색 -> 다 채워짐 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import jav..
백준 1034 - 램프(java)
www.acmicpc.net/problem/10www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net 1. 유형 그리디, 브루트포스 2. 풀이 처음 풀이는 M의 길이만큼 뒤집을 수 있는 조합을 만들어서 전부 구하려고 했다. 하지만 그렇게 되면 2^M 즉, 최대 2^50가지의 경우가 나오기 때문에 시간 초과가 걸린다. 때문에 다른 접근 방식이 필요하다. 풀이2 위와 같은 예시에서 정답은 3이다 위와 같은 예시에서는 정답이 0 이다. 이걸로 K값의 홀짝 여부를 ..
![[백준 - 20208] 골드5 - 진우의 민트초코우유(java)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FUQiwG%2FbtqQptRI3m6%2F0wfwL6UGRwpXFmY2XxjRTK%2Fimg.png)
[백준 - 20208] 골드5 - 진우의 민트초코우유(java)
www.acmicpc.net/problem/20208 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 1. 유형 순열 시뮬 2. 풀이 구현기능 민트에 대한 순열 다음 민트까지의 계산 자료구조 민트가 몇개인지 모르기때문에 ArrayList사용 좌표저장 Pair 클래스 민트초코가 10개 밖에 되지 않는다. 그러므로 10!경우의 순열을 구한다 집에서 -> 민트1 -> 민트2 -> .... 민트10-> 집 까지의 시뮬레이션을 돌린다 만약 중간에 체력이 떨어져서 다음 민트로 갈수 없다면 반복문을 종료..
![[백준 - 20303] 골드3 - 할로윈의 양아치](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FBgShr%2FbtqP6nqup69%2Fk9n0yySh89OkdFPG9OActk%2Fimg.png)
[백준 - 20303] 골드3 - 할로윈의 양아치
www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 1. 유형 dfs, 다이나믹 프로그래밍, 슬라이딩 윈도우 2. 풀이 구현기능 : 인접리스트 만들기 dfs로 아는 사람끼리 묶기 배낭문제 자료구조 어레이 리스트 주어진 입력값을 인접리스트로 만듬 아는 사람끼리 묶고, 합과, 사람수를 구해서 Pair클래스에 입력 묶음 들을 배낭문제의 요소로 사용 위 처럼 총 4묶음을 구할 수 있다..