관찰과 질문, 그리고 데이터

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다. 다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴 www.acmicpc.net 저 긴 글에서 '문제에 필요한 조건'을 정확히 찾아내고 구현해야 하는 시뮬레이션 문제. 시계 방향 / 반시계 방향으로 값을 회전시켜야..

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 문제 조건에 맞게끔 코딩하면 되는 시뮬레이션 문제. 조건에 맞는 방법을 구현하는 데 삽질을 꽤나 많이 했다. 문제의 조건에서 가장 까다로웠던 부분은 '궁사의 적 공격 조건'이었다. 1. 거리가 D 이하인 적들 중 가장 가까운 적. 2. 가까운 적이 여러 명이면 '가장 왼쪽'의 적을 공격한다. 3. 여러 궁사가 같은 적을 공격할 수 있다. 여기서 '가장 왼쪽'의 적을 선택하는 방법을 구현해보려고 - 궁사의 위..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 www.acmicpc.net 이전에 풀었던 '등굣길' 형태의 길찾기 문제의 심화 버전 느낌이었다. [Python] 프로그래머스. 등굣길 (Level 3)..

https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오. www.acmicpc.net 시뮬레이션 문제. 문제에서 요구한 조건대로 코딩하면 된다.

https://programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 | 프로그래머스 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다. 1원을 5개 사용해서 거슬러 준다. 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다. 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준 programmers.co.kr 풀이를 찾아보면 다들 전형적인 DP문제라고 하는데, 나한테는 왜 이렇게 어..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 삼성SW역량테스트 기출문제로, DP를 사용해 풀 수 있는 문제. table[i] = i번째 날에 얻을 수 있는 최대 보수라고 정의하면 table[i]의 초기값은 '해당 날짜에 일할 수 있을 때 기본값' 이 된다. 해당 날짜에 일할 수 없으면 0으로 정의한다. 점화식은 table[i] = max(table[i-1] + i번째 날에 일했을 때 얻는 보수, table[i]) 형태가 된다.

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 www.acmicpc.net 이분탐색 + BFS 활용문제. start지점과 end지점이 이미 정해져 있으므로, BFS에서는 'start -> end'로 이동하는 모든 ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net DP 점화식을 세워서 해결할 수 있는 문제. 각 집마다 R, G, B 색깔로 칠할 때의 비용이 주어지므로, idx 0 = R, 1 = G, 2 = B로 정의하면 0

https://programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr DP를 사용해 풀 수 있는 문제. board의 y좌표, x좌표를 기준으로 볼 때 board[y-1][x-1], board[y][x-1], board[y-1][x] 세 개의 좌표값이 전부 1이라면 board[y][x]는 세 개의 정사각형이 왼쪽, 위쪽, 왼쪽 대각선에 포진해 있게 된다. 따라서 이 경우 결과적으로 정사각형 4개가 붙어 있는 모양이 되므로 변의 길이가 2인 정사각형이 된다. 따라서 DP 점화식을 board[y][x] = ma..

https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 | 프로그래머스 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모 programmers.co.kr 사람 한 명당 보트를 한 번 사용하는 경우가 보트를 최대한으로 사용한 경우..