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

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다. www.acmicpc.net 이분탐색 문제. 이분탐색으로 찾아야 할 값은 '랜선의 길이'이고, 이분탐색의 기준은 '랜선의 개수'가 된다. 랜선의 길이 최솟값은 1, 최댓값은 주어진 랜선 길이로 정한 뒤 mid = (최솟값 + 최댓값) // 2로 잘라낼 길이를 ..

https://www.acmicpc.net/problem/2231 2231번: 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그 www.acmicpc.net 수학적 센스가 있어야 하는 것 같다. 나는 그게 없어서 다른 분의 풀이를 참고했다. 백준 2231. 분해합 문제 풀이 백준 2231. 분해..

https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 | 프로그래머스 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다. 제거한 바위의 위치 각 바위 사이의 거리 거리의 최솟값 [21, 17] [2, 9, 3, 11] 2 [2, 21] [11, 3 programmers.co.kr 이분탐색 문제. distance 제한사항이 1,000,000,000인 것에..

https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 | 프로그래머스 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solut programmers.co.kr 간단한 DP 문제. 아무 칸도 뛰지 않는 경우 (0칸) = 경우의 수 1..

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]) 형태가 된다.