전체 글
[백준] 테트로미노
https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net dfs방법과, 직접 구현하는 방식 두 방식으로 문제를 해결하였습니다. 총 두가지 풀이에 대해 설명해 보겠습니다. 우선 문제부터 간단하게 요약하면, 이렇게 4개의 정사각형으로 만들어진 조각들로 숫자들이 놓인 N x M 크기의 종이안의 합이 최대가 되는 경우의 값을 구하는 문제입니다. 실제로 문제를 읽어보는 것을 추천합니다. 총 두가지의 방법으로 해결하였는데 각각의 방법에 대해 설명해 보겠습니다. 방..
[백준] 주사위 굴리기
https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 구현 문제입니다. 우선 문제부터 간단하게 요약하면, 가로가 N, 세로가 M인 지도에서 규칙대로 주사위를 굴릴 때, (지도 밖으로 주사위가 나가는 경우에는 안굴립니다.) 굴리는 것에 성공 한 경우, 주사위의 가장 윗면에 적힌 숫자를 출력하는 것이 문제입니다. 실제로 문제가 조금 기니 한번 읽어보는 것을 추천합니다. 주사위의 전개도를 ..
[백준] 연산자 끼워넣기
https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net dfs를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, N개의 수와, N-1개의 연산자가 주어지면, 연산자를 적절하게 배열하여, 앞에서 부터 계산하였을 때, 최댓값과 최솟값을 return해야 하는 문제입니다. (이 때, 연산자는 +,-,*,/ 가 있습니다. 또 N개의 수의 위치는 고정되어 있다고 가정하고, 연산자의 위치만 바꾸어야 합..
이얼즈어고 GARDEN FLOWER CONVERTIBLE COLLAR SHIRTS
오랜만에 쇼핑했다. 이얼즈어고 꽃무늬 셔츠를 샀다. 가끔 박스에 담겨서 오기도 하는데 오늘은 종이로 된 팩에 담겨서 왔다. 재질이 엄청 좋아보인다. 린넨 이런 느낌보다는 약간 실크같은 린넨..? 비스코스 셔츠? 같은 아무튼 그런 특이한 소재인것 같다. 날씨 비안오고 조금 괜찮아지면 입고 나가야지 ㅎ
[백준] 상어 초등학교
https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 구현 문제입니다. 우선 문제부터 간단하게 요약하면, 학생들을 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다. 다..
[백준] 불 끄기
https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 일종의 brute forcing하는 문제인데 규칙성을 찾아 횟수를 줄여야 하는 문제입니다. 우선 문제부터 간단하게 요약하면, #O######## OOO####### #O######## ####OO#### ###O##O### ####OO#### ########## ########O# #######OOO ########O# 다음과 같이 10 x 10의 array에서 O는 불이 켜져있음을 의..
[백준] 스도쿠
https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net dfs를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 하다 만 스도쿠가 input으로 들어오면, 마저 끝내서 return을 해야 하는 문제입니다. 처음에는 시간초과가 나왔습니다. 처음 풀이 아이디어와, 나중에 어떻게 고치는지 순서로 설명을 해보겠습니다. 우선 이 문제를 보면, dfs를 사용해야 하는 것을 알 수 있습니다. 간단한 예시를 통해 아이디어를 살펴봅시다. 다음 그림과 같이..
[백준] 팰린드롬 분할
https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 다이나믹 프로그래밍을 두번 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 주어진 문자열에 팰린드롬 분할을 한 갯수의 최솟값을 출력해야 합니다. 처음에 두개의 다이나믹 프로그래밍중 하나만 이용하여 시간초과가 났었고 이후에 해결을 하였는데 각각 과정들을 한번 설명해 보겠습니다. (큰 아이디어에서 출발해서 수정을 한 부분의 아..