티스토리

고양멍멍이

검색하기

블로그 홈

고양멍멍이

nato-blog.tistory.com/m

코딩초보 / 게임초보 / 뭐먹고 살지

구독자: 1

방명록 방문하기

주요 글 목록

[백준] 16987 - 계란으로 계란치기 [문제링크] 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 0. 내구도/데미지 값을 고려해서 가능한 많은 계란을 깨는 문제 1. 재귀를 사용해서 모든 경우의 수를 진행한다 현재 계란이 깨지지 않았다면, 이걸로 다른 깨지지 않은 계란을 친다 깨졌다면, 그냥 넘어간다 다음번 계란으로 넘어가서 반복한다 모든 계란에 대해 시도했다면, 종료하고 깬 계란 수를 관리한다 계산 편의, 효율을 위해 깨진 계란의 수를 인자로 관리한다 2. 위 과정에서 나온 값들 중 최댓값을 저장, 출력 import java.io.. 공감수 0 댓글수 0 2022. 1. 31.
[백준] 17086 - 아기 상어 2 [문제링크] 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 0. 상어와 가장 먼 칸에서의 상어와의 거리를 구하는 문제 1. 이동 방향이 8방향이므로, dir 배열을 8방향으로 구성한다 2. 상어를 기준점으로 주변 칸을 bfs로 탐색한다 위치와 거리 정보를 저장하는 class를 만들어 사용한다 탐색하며 거리 정보를 칸에 저장한다 탐색 중 특정 지점에 현재 거리보다 작거나 같은 값이 저장되있다면, 다른 상어가 더 가깝게 있다는 뜻이므로 탐색을 정지한다 3. 모든 상어로부터 bfs가 종.. 공감수 0 댓글수 0 2022. 1. 31.
[백준] 11047 - 동전 0 [문제링크] 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 0. 최소한의 갯수로 목표 금액을 맞추는 문제 1. 모든 고액권은 소액권의 n배수로 떨어지므로, 항상 가장 큰 액수부터 선택하는게 유리하다 그리디 알고리즘 2. 목표 금액을 초과하지 않는 선에서, 가능한 많은 금액을 고액권부터 채워나간다 3. 목표 금액이 완성되면, 최종 갯수를 출력 import java.io.BufferedReader; import java.io.InputStreamRe.. 공감수 0 댓글수 0 2022. 1. 16.
[백준] 1743 - 음식물 피하기 [문제링크] 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 0. 가장 큰 음식물 덩어리의 크기 구하기 상하좌우로 연결되 있을 경우 한 덩어리로 본다 1. 음식물의 여부를 boolean 배열로 표현한다 2. 탐색 중 음식물 발견시, dfs 탐색으로 진입한다 이미 탐색한 음식물 제거 (현재 위치 false로 변경) 상하좌우 4방향 각각으로 음식물이 있으면 진행한다 최종적으로 연결된 모든 음식물을 지우고, 그 크기를 반환 3. 모든 음식물 덩어리중 가장 큰 값 유지, 출력.. 공감수 0 댓글수 0 2022. 1. 16.
[백준] 15900 - 나무 탈출 [문제링크] 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 0. 모든 leaf 노드에 말이 있으며, 한 번에 하나씩 부모로 올리는 게임 모든 leaf 노드의 차수의 합에 따라 승/패를 알 수 있다 (짝수면 선공 패배, 홀수면 선공 승리) 1. 시작 노드는 1번으로 고정이므로, BFS를 이용해 모든 노드를 탐색, leaf 여부 및 depth를 저장한다 2. BFS를 진행할 때 연결된 노드에 이미 depth 정보가 있다면 : 이미 방문한 노드, 즉 부모 노드이다 depth 정보가 없다면 : 방문하지 않은 노드, .. 공감수 1 댓글수 0 2021. 12. 25.
[백준] 18428 - 감시 피하기 [문제링크] 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 0. 모든 선생님의 시야(일직선)를 피하도록 장애물을 설치할 수 있는지 묻는 문제 맵의 크기가 최대 6*6으로 작고, 선생님의 수도 5 이하로 적으니 brute-force로 해결 가능하다 1. setWall 재귀를 3번 진행하며 가능한 모든 조합으로 벽을 설치한다 2. 3개의 벽이 설치됬다면, 모든 선생님 기준으로 4방향 검사, 학생이 보이는지 검사한다 학생의 수(최대 30)에 비해 선생의 수(최대 5)가 적기 때문 3. 단 한 선생님이라도 .. 공감수 0 댓글수 1 2021. 12. 25.
[백준] 9934 - 완전 이진 트리 [문제링크] 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 0. 완전 이진 트리를 중위 순회한 결과가 주어졌을때, 원래의 트리를 복원하는 문제 1. 완전 이진 트리의 특성상, 왼쪽 subtree와 오른쪽 subtree의 크기가 동일하다 중위 순회는 왼쪽 - 자신 - 오른쪽 순서로 이루어지므로, 정 가운데 번호가 항상 root노드이다 2. 시작-끝 값으로 subtree 정보를 유지하면서, 가운데(root) 정보를 저장하며 재귀를 진행한다 재귀의 깊이에 따라 각 list에 저장 subt.. 공감수 0 댓글수 0 2021. 12. 22.
[백준] 14496 - 그대, 그머가 되어 [문제링크] 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 0. a-b 두 노드간 최단 거리 구하기 1. 다익스트라, 벨만 포드 등 다양하게 풀이 가능하다 2. bfs로 탐색, 목표 노드가 발견되는 즉시 탈출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue;.. 공감수 0 댓글수 0 2021. 11. 14.
[백준] 2346 - 풍선 터뜨리기 [문제링크] 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 1. 사용한 풍선은 표시해두고, 지나가더라도 카운트하지 않는다 2. 양 끝 간 이동 처리를 위해, 증감시 N으로 나머지 연산 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public static void main(String[] args)throws Exception .. 공감수 0 댓글수 0 2021. 10. 25.
[백준] 17276 - 배열 돌리기 [문제링크] 17276번: 배열 돌리기 각 테스트 케이스에 대해 회전 연산을 마친 후 배열의 상태를 출력한다. n줄에 걸쳐 각 줄에 n개의 정수를 공백으로 구분하여 출력한다. www.acmicpc.net 0. 단순한 구현 문제 1. 4개의 대각선을 옮기는 작업을 한다 두 수를 swap하듯, 하나를 백업하고 후에 복구 2. -X 각도로의 회전은 360-X 각도의 회전과 같다 별도의 함수를 만들지 않고, 45도 회전 함수를 동일하게 사용 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ static int[][] map; static int n,d;.. 공감수 0 댓글수 0 2021. 10. 10.
[백준] 1325 - 효율적인 해킹 [문제링크] 공감수 0 댓글수 0 2021. 9. 25.
[백준] 5567 - 결혼식 [문제링크] 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 0. 친구의 친구까지만 찾는 문제 1. BFS를 딱 두번만 돌린다 혹은 DFS를 깊이 2에서 종료한다 (깊이 1과 2를 공유하는 node에 유의하면서) 2. 방문한 노드의 수 = 초대할 사람의 수이다 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.. 공감수 0 댓글수 0 2021. 8. 8.
[백준] 14241 - 슬라임 합치기 [문제링크] 14241번: 슬라임 합치기 영선이와 효빈이는 슬라임을 합치는 게임을 하고 있다. 두 사람은 두 슬라임을 골라서 하나로 합쳐야 한다. 게임은 슬라임이 하나 남았을 때 끝난다. 모든 슬라임은 양수 크기를 가지고 있다. 두 www.acmicpc.net 0. x와 y 슬라임으로, x+y 슬라임을 만들며, x*y 점수를 획득한다 1. N번째 합칠 슬라임의 무게가 y였다면, N+1, N+2...번째 연산에도 y가 포함되게 된다 2. 크기가 큰 슬라임을 빠르게 합쳐, 이후 연산들에 최대한 많이 포함되도록 해야 한다 (그리디) 3. 슬라임을 크기순으로 2개씩 꺼내며 합쳐나간다. import java.io.BufferedReader; import java.io.InputStreamReader; import.. 공감수 0 댓글수 0 2021. 7. 7.
[백준] 1697 - 숨바꼭질 [문제링크] 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 0. 수빈이의 이동 방법 3가지를 활용해, 동생에게 가장 빠르게 갈 수 있는 경우 찾기 - 3개의 선택지가 있는 탐색 문제. - 어떤 선택지를 먼저 선택하느냐에 따라 해가 나오지 않거나 큰 해가 나오는 경우가 존재하므로 DFS가 아닌 BFS 사용 1. 수빈이의 시작지점 N에서 BFS방식으로 +1, -1, *2 지점을 큐에 넣으며 진행한다 2. 수빈이가 어떤 칸 X에 W초를 거쳐 도달했는데, 이미 해당 칸에 W보다 적은 시간.. 공감수 0 댓글수 0 2021. 5. 29.
[백준] 5639 - 이진 검색 트리 [문제링크] 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 0. bufferedreader로 EOF 입력받는법 : null인지 아닌지 체크하기 1. 모든 수를 입력받아서 list로 저장 2. 전위순회의 결과물이므로 [루트] [왼쪽 서브트리] [오른쪽 서브트리] 의 형태로 나눌 수 있다. 3. 루트보다 커지는 지점이 오른쪽 서브트리의 시작점이므로, [왼쪽 서브트리] > [오른쪽 서브트리] > [루트] 의 순서로 재귀를 실행한다 4. 인자로 받은 서브트리가 1칸짜리면 그 원소를 list에 넣고 반환.. 공감수 0 댓글수 0 2021. 4. 14.
[백준] 2564 - 경비원 [문제링크] 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 0. 블록의 길이는 n*m이며 블록 중간에는 상점도 길도 없으므로 한바퀴 도는 경로를 n+m+n+m크기의 1차원 배열로 관리할 수 있다 1. 북쪽 > 동쪽 > 남쪽 > 서쪽 순서의 경로를 가정하고, 입력받은 상점의 위치를 가공해 저장한다 2. 마지막에 시작점을 입력받고, 배열을 한바퀴 순회(배열의 범위를 넘어가면 0으로 초기화)하며 거리를 누적한다 - 거리는 정방향(i)과 역방향(totalLen - i) 중 짧은쪽을 누적한다 import java.io.B.. 공감수 2 댓글수 0 2021. 4. 13.
[백준] 2110 - 공유기 설치 [문제링크] 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 0. 집에 n개의 공유기를 설치할 때, 가능한 최대 거리를 구하는 문제 - 집 사이의 간격에 대해 바이너리서치 진행 1. 바이너리 서치의 시작점은 0, 끝점은 가장 먼 집의 좌표 2. 구한 dis에 따라, 최대한 그리디하게 집에 공유기를 설치했을 때의 갯수를 센다 3-1. 공유기가 목표 갯수를 충족했다면, ans를 갱신 후 min값을 갱신, 더 큰 dis를 시도해본다 3-1. 공유기가 목표 갯수에 .. 공감수 0 댓글수 0 2021. 4. 13.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.