매일 조금씩

문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 이런 문제 유형은 처음이라, 쉽사리 해결 방법이 생각나지 않았다. 질문 게시판 힌트를 보고 풀었다. 일단 기본 뼈대는 BFS로 구현한다. 이후 벽 한개를 어떻게 파괴할 것인가? 이 문제에 맞닥뜨린다. 벽을 최대 한 개 파괴할 수 있지만 반드시 파괴해야 하는 것은 아니다. 이 문제의 핵심은 방문 체크에 있다. 보통 좌표의 방문체크를 2차배열로 구현하지만, 해당 문..

문제 https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 풀이 의상을 입는 조합의 수를 구하는 문제이다. 종류에 따른 의상 수를 구한다. HashMap 이용 얼굴 - 2 상의 - 1 하의 - 1 겉옷 - 1 조합의 수는 각 의상 수를 곱해주면 되는데, 의상을 입지 않는 경우의 수가 있으므로 +1을 한 후 곱한다. 3 * 2 * 2 * 2 = 24 의상을 최소 한 개는 입어야 한다는 조건이 있으므로 여기서 의상을 모두 안입는 경우의 수 (-1)를 빼줘야 한다. 24 - 1 = 23 아래 백준 문제와 풀이가 동일하다. 2021.11.11 - [Problem Solving/BOJ] - [BOJ 9375]..

문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 풀이 전형적인 BFS 문제. 이동 가능한 좌표를 정의하고 시작한다. 아래 dir을 순회하면서 현재 x좌표에 첫 번째 원소, y좌표에 두 번째 원소를 더하여 다음 좌표를 계산한다. public sta..

문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 배열이 3차원일 뿐 풀이는 아래와 동일하다. 2021.11.19 - [Problem Solving/BOJ] - [BOJ 7576] 토마토 (Java) [BOJ 7576] 토마토 (Java) 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의..

문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/42889# 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 풀이 단순 구현 문제이다. 변수가 헷갈려서 머리가 핑 도는 모먼트가 몇 번 있었다. Stage 클래스를 만들어서 문제를 풀었다. 소스코드 import java.util.*; class Stage implements Comparable{ int no; double passCnt; double failCnt; double rate; public Stage(i..

문제 https://programmers.co.kr/learn/courses/30/lessons/1835?language=java 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 풀이 완전 탐색과 DFS로 풀었다. 데이터 개수가 8개로 정해져 있고 크지 않기 때문에 시간초과는 발생하지 않았다. 모든 경우의 수를 구하고, rule에 부합하지 않는 케이스는 count 하지 않는다. 소스코드 import java.util.*; class Solution { public boolean[] used; public ..

문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 아래와 같이 짜면 시간/메모리 초과가 발생한다. public static long recur(long a, long b, long c){ if(a==1 || b==1) return a; return a * recur(a, b-1, c) % c; } recur(a*a, b/2, c)로 호출하여 함수 호출 횟수를 줄이는게 핵심이다. overflow가 발생하지 않도록 여러 곳에 c로 mod연산을 해야한다. b가 1인 조건일 때 mod연산을 누락해서 한참 헤..

문제 https://programmers.co.kr/learn/courses/30/lessons/42627# 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 문제 설명 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를들어 - 0ms 시점에 3ms가 소요되는 A작업 요청 - 1ms 시점에 9ms가 소요되는 B작업 요청 - 2ms 시점에 6ms가 소요되는 C작업 요청 와 같은..

문제 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 풀이 아래 문제와 달리 해당 문제는 분할을 9개로 한다. (내부에서 좌표를 갱신하여 재귀함수를 9번 호출) 이 외에 풀이는 아래 문제와 유사하다. 2021.11.16 - [Problem Solving/BOJ] - [BOJ 2630] 색종이 만들기 (Java) [BOJ 2630] 색종이 만들기 (Java) 문제 https://www.acmicpc.net/problem/2630 263..