제이티의 코딩 블로그 제이티의 코딩 블로그

학교에서 진행하는 수업에서 알고리즘 문제를 공유받아 문제를 풀어보았다. 문제의 난이도는 실버 5로, 정답률은 약 62%이다. 시간 제한은 1초이다.문제 링크https://www.acmicpc.net/problem/18242문제 설명네모네모 안과에서는 아래와 같은 방법을 이용하여 시력검사를 진행한다. 격자가 그려진 흰색 바탕의 N × M 직사각형의 내부에 한 변의 길이가 3보다 큰 홀수이며 행 또는 열에 평행인 단 하나의 정사각형의 테두리를 색칠한다. 이때 정사각형의 네 변 중 한 변의 가운데는 색칠하지 않으며 이 색칠하지 않은 변이 정사각형의 어느 변인지를 맞추어 보라는 것으로 시력 검사를 진행한다. 예를 들어 N = 7, M = 8 직사각형 내부에 조건에 맞는 다음과 같은 정사각형을 그릴 수 있다.왼쪽..

학교에서 진행하는 수업에서 어렵다고 생각하는 알고리즘 문제를 공유하고, 문제를 풀어보았다. 문제의 난이도는 골드 3으로, 정답률은 약 45%이다. 시간 제한은 1초이다.문제 링크https://www.acmicpc.net/problem/15683문제 설명 사무실에 총 5가지 종류의 CCTV가 설치되어 있다. 각 CCTV는 감시할 수 있는 영역이 제한되어 있는데 벽을 뚫을 수 없고, 90도 회전이 가능하다. 이 때 사무실의 크기와 상태, CCTV의 위치가 주어졌을 때 사각 지대의 최소 크기를 구하는 것이 이번 문제이다.문제 분석 사무실의 상태가 입력으로 들어온다. 먼저 세로 크기 N과 가로 크기 M을 입력받으며 0은 빈칸, 1 ~ 5는 CCTV, 6은 벽을 나타내는 각 칸의 정보가 주어진다. 해당 입력에 대..

학교에서 진행하는 수업에서 알고리즘 문제를 공유받아 문제를 풀어보았다. 문제의 난이도는 실버 1로, 정답률은 약 60%이다. 시간 제한은 2초이다.문제 링크https://www.acmicpc.net/problem/1992문제 설명 이번 문제는 흑백 영상을 압축하는 문제이다. 주어진 영상이 모두 0으로 되어 있으면 "0"으로 압축이 되고, 1로 되어 있으면 "1"로 압축이 된다. 0과 1이 섞여있는 경우에는 좌상단, 우상단, 좌하단, 우하단으로 나누어 영상을 압축하게 되고, 압축한 결과를 괄호로 묶어 표현한다.문제 분석 문제에서 주어지는 입력인 비디오를 보면 문자열로 입력이 들어온다. 문제 해결을 위해 해당 문자열을 video[N][N] 배열로 매핑하는 과정이 필요하다. 만약 비디오의 압축하고자 하는 영역..

학교에서 진행하는 수업에서 주어진 문제를 풀어보았다. 문제의 난이도는 프로그래머스 기준 레벨 2이다.문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42888문제 설명 이번 문제는 카카오톡 채팅방에서 '[닉네임]님이 들어왔습니다.', '[닉네임]님이 나갔습니다.'와 같은 메세지가 나타나는 상황에 대하여 어떤 유저가 들어오고 나갔는지 출력하는 문제이다. 이 때, 사용자가 닉네임을 변경하는 상황을 고려해야 하기 때문에 문제 난이도가 조금 높아졌다.문제 분석 채팅방에서 닉네임을 변경하는 방법은 총 두 가지 방법이 있다.채팅방을 나간 후, 새로운 닉네임으로 들어오기채팅방에서 닉네임을 변경하기닉네임을 변경하게 된 경우, 기존에 채팅방에 출력되어 있던..

학교에서 진행하는 수업에서 알고리즘 문제를 공유하기 위해 문제를 풀어보았다. 문제의 난이도는 골드 5로, 정답률은 약 20%이다. 시간 제한은 1초이다.문제 링크https://www.acmicpc.net/problem/5430문제 설명 이번 문제는 정수 배열에 연산을 한 결과를 출력하는 문제이다. 연산의 종류는 뒤집기 R과 버리기 D가 있다. 뒤집기 R은 배열의 순서를 뒤집기(Reverse)하는 함수이고, D는 첫 번째 수를 버리는 (pop_first) 함수이다. 배열이 비어 있을 때 D를 사용하면 에러가 발생한다.문제 분석 문제에서 주어지는 입력을 보면 배열이 문자열 [1, 2, 3, 4]와 같은 형태로 입력이 들어온다. 문제를 풀기 위해서는 이러한 문자열을 배열로 파싱하는 과정이 필요하다. 필자는 입..

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다. 문제의 난이도는 프로그래머스 레벨 3으로, 표기된 난이도와 비교하였을 때 비교적 쉽게 문제를 해결할 수 있었다. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42578 문제 분석 해당 문제는 의상의 종류와 이름이 주어지고, 각 의상의 조합의 수를 찾는 문제이다. 예를 들어 [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]가 clothes Input으로 들어오면 아래와 같은 조합이 가능하다. 1. yellow_hat 2. blue_sunglasses 3. gree..

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다. 문제의 난이도는 실버 1로, dp 방식을 활용해 푸는 것을 권장받은 문제이다. 문제 링크 https://www.acmicpc.net/problem/1932 문제 분석 이번 문제는 주어진 삼각형에 대하여, 모든 숫자의 합이 최대가 되는 경로에 있는 숫자의 합을 출력하는 문제이다. 자료 구조 및 알고리즘 DP (Dynamic Programming) dp는 큰 문제를 작은 문제로 쪼개고 합쳐 문제를 해결하는 방식 중 하나이다. 중복되는 연산을 방지할 때 주로 사용되며, 이는 메모이제이션이라고도 한다. 예를 들어 피보나치 수열을 계산할 때에 DP를 사용할 수 있다. 문제 풀이 이번 문제를 풀 때에 유심히 봐야할 것은 경로를 선택할 때에 현재 층에서..

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다. 문제의 난이도는 골드 5로, 유니온 파인드 방식을 활용해 푸는 것을 권장받은 문제이다. 문제 링크 https://www.acmicpc.net/problem/1717 문제 분석 이번 문제는 입력으로 n과 m을 받아, n개의 집합을 생성하고 m번의 연산을 수행한다. 연산은 집합을 합하는 합집합과, 두 원소가 같은 집합에 속해 있는지 확인하는 연산 두 가지가 존재한다. 두 원소의 집합을 합하는 합집합은 0 a b의 형태로 입력이 주어지고, 두 원소가 같은 집합에 속해 있는지 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이 때, 두 원소가 같은 집합에 속했는지 확인하는 연산을 수행한 후 같은 집합일 경우엔 "YES"를, 아니라면 "NO"를..