고양멍멍이

[문제링크] 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 0. x, y좌표에 val값이 들어갈 수 있으려면 - 같은 행에 val이 존재해선 안되고 - 같은 열에 val이 존재해선 안되고 - 같은 3*3블록에 val이 존재해선 안된다 - chk함수로 이를 판단 - 하나의 행/열에서 1~9의 숫자는 한번씩만 등장하므로, boolean배열로 중복 여부를 판단한다 1. x,y의 값이 0일때, 1~9까지 가능한 모든 숫자를 넣어보면서 다음 단계로 진행한다 - 0이 아니면 바로 다음으로 진행 2. 진행이 불가능..

[문제링크] 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 0. 직전 단계의 결과 중 최소 / 최대값만을 취하는 간단한 DP 1. 메모리 제한이 작으므로 직전 단계만을 저장하도록 2칸의 배열을 잡는다 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public static void main(String[] args)throws Exception { Buffere..

[문제링크] SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 0. 현재 파이프의 모양 - 인접 파이프의 모양 에 따라 갈수 있는지 없는지 여부가 결정된다 - 총 4방향이므로, 4개의 bit에 bitmask로 저장해 정보를 나타낸다. 1. 입력값(0~7)에 따라 해당하는 bitmask정보를 부여한다 2. 시작점에서 time만큼 bfs를 돌며 - 현재 노드에서 상/하/좌/우 통로가 존재하고 + 진행 노드에서 하/상/우/좌 통로가 존재한다면 - 진행 가능, 큐에 넣는다 - 방문체크 대신 큐에 넣을때 자기 위치의 값을 0으로 바꿔 재방문을 방지한다 3. time이 다 지났다면 (혹은 도중에 탐색을 마쳐 qu가 비었다면..

[문제링크] 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 0. 슬라이딩 윈도우로, 다음 초밥을 넣고, 첫 초밥은 빼가며 종류를 센다 (큐 사용) - 회전초밥벨트이므로, 시작한 K개의 초밥이 마지막 초밥에 이어진다 - [시작부분] - [나머지] - [시작부분] 의 순서로 저장해서 처리 1. end포인터를 1씩 늘려가며 k개의 초밥을 받고, 종류를 센다 2. end포인터가 N+k가 될 때까지, end포인터의 초밥을 포함시키고, fst포인터의 초밥을 내보내는것을 반복한..

[문제링크] 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 0. 내부 공기엔 인접해도 녹지 않으므로, 외곽 공기에 대해서만 bfs를 진행. - 0,0은 항상 밖의 공기이다 1. 0,0을 시작점으로, 외곽 공기를 bfs로 순회한다 - 치즈를 처음 만나면, 표시만 한다 - 치즈를 2번째로 만나면, 제거 대상 치즈로 판단, 저장한다 2. 1번에서 저장된 제거대상 치즈를 제거한다 3. 위 과정을 치즈가 없어질때까지 반복한다 import java.io.BufferedReader; import java.io...

[문제링크] 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 0. 치킨집의 총 개수를 모르므로 arraylist로 관리 - 살릴 치킨집의 개수는 알고 있으므로 배열로 관리 1. 가능한 모든 살릴수 있는 치킨집의 조합을 구한다 (combi 함수) 2. 각 조합에 대해, 치킨집 위치를 시작으로 bfs를 돌려 모든 집까지의 최소 거리를 구한다 (bfs함수) 3. bfs함수에서 구한 최소 거리가 더 작다면 min을 갱신 import java.io.BufferedReader; import java...

[문제링크] SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 0. shoot함수 : n번째 구슬을 모든 경우의 수에 대해 쏴보고, n+1번째로 재귀하는 함수 - remove함수 : x, y좌표의 벽돌이 깨졌을 경우 모든 벽돌을 재귀로 깨는 함수 - getDown함수 : 벽돌을 깬 후 모든 벽돌을 빈공간 없이 아래로 쌓는 함수 1. shoot함수가 모든 경우의 수에 대해 remove -> getDown 해본다 2. n번 구슬을 쐈을때 남아있는 ball값과 min을 비교, 갱신 * ball(remain)값을 인자로 넘기지 말고 전역변수로 관리할 수 있을것같은데, 피곤해서 포기 import java.io.Buffer..

[문제링크] 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 0. 폭탄 진행현황을 index로 검사한다 1. 현재 index에 맞는 문자가 들어오면 : 누적 후 index+1 2. 현재 index와 다른 문자가 들어오면 - 폭탄의 첫 문자이다 : 새 폭탄의 시작점일 가능성, 현재 index정보를 백업하고 누적, index=1부터 다시 시작 - 일반 문자이다 : 폭탄이 아니므로 모든 index를 제거, 누적된 문자들을 출력 문자열에 추가하고 index=0 - 폭탄의 마지막 문자이다 : 폭탄이 터진..

[문제링크] 13137번: Exchange Problem 만약 병찬이가 사용한 방법이 항상 최적이라면 'Yes'를 출력하고, 그렇지 않다면 'No'를 출력한다. www.acmicpc.net 0. 그리디를 이용해 가격 구하기 - n번 동전의 가치가 w이고, n-1번 동전까지 사용하여 w-1 금액까지는 옳은 해가 구해져 있다면 - w원 이후의 가격 x에 대해선 ( (x%w)의 최적해 + (x/w) ) 이 최적해이다 - ex) 한국 동전에 대해, w가 500원일때 650원의 최적해는 (150원의 최적해 + 1) 이다 - DP는 이 문제에서 항상 옳은 해를 구할 수 있다 - DP를 이용해 구한 해와 그리디를 이용해 구한 해가 일치한다면, 그리디가 최적해를 구하는 것 - 그리디를 통해 w ~ 2*w까지 최적해를 ..

[문제링크] 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 0. bufferedreader로 EOF 입력받는법 : null인지 아닌지 체크하기 1. 모든 수를 입력받아서 list로 저장 2. 전위순회의 결과물이므로 [루트] [왼쪽 서브트리] [오른쪽 서브트리] 의 형태로 나눌 수 있다. 3. 루트보다 커지는 지점이 오른쪽 서브트리의 시작점이므로, [왼쪽 서브트리] > [오른쪽 서브트리] > [루트] 의 순서로 재귀를 실행한다 4. 인자로 받은 서브트리가 1칸짜리면 그 원소를 list에 넣고 반환..