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

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net bfs 문제. 입력받은 데이터를 순서대로 읽어들이면서, 1을 만날 경우 해당 위치에서 bfs로 도달할 수 있는 모든 지점을 확인한다. bfs로 탐색하면서 count..

https://www.acmicpc.net/problem/5397 5397번: 키로거 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다. 강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 테 www.acmicpc.net 커서가 이동할 때, 커서 앞뒤의 값을 어떻게 처리하는지 고민하는 게 매우 어려웠던 문제. 커서의 왼쪽 / 오른쪽에 있는 값을 전부 stac..

https://www.acmicpc.net/problem/9012 9012번: 괄호 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(conc www.acmicpc.net 말이 복잡하지만, 결국 1 .왼쪽 괄호와 오른쪽 괄호 개수가 동일하며 2. 처음에는 (로 시작하고 마지막에는 )로 끝나면 VPS라고 부른다는..

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