Archived(CSE Programming)/알고리즘(C++) (55) 썸네일형 리스트형 프로그래머스_N으로 표현 https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 | 프로그래머스 programmers.co.kr 처음 해당 문제를 접했을 때는 DP로 풀려고 하였다. 그런데 DP로 생각해보려니 최적화 원리가 어떻게 적용될 수 있는지 이해가 잘 안되서 쉽지 않았다. 그러던 중 DFS로도 할 수 있지 않을까 생각하였고 다행히 터지지 않고 해결할 수 있었다. DFS로 접근법은 간단하다, 숫자에 대해 연산을 재귀적으로 수행하면서 목적값 number를 찾아가면 된다. 이 때 백트랙킹 조건으로 다음의 두 가지를 포함시켰다. 1) 숫자 사용 수가 8번이 넘어가는 경우 2) 현재까지 만들어둔 결과값 num이 0일 때는 굳이 곱하거나 나누는 경우 나누.. 프로그래머스_2*n 타일링 https://programmers.co.kr/learn/courses/30/lessons/12900# 코딩테스트 연습 - 2 x n 타일링 | 프로그래머스 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다. 타일을 가로로 배치 하는 경우 타일을 세로로 배치 하는 경우 예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 s programmers.co.kr 기본적인 DP 문제이다. Level 3의 카카오 추석 트래픽 문.. 백준 17144_미세먼지 안녕! 문제 : https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼 www.acmicpc.net 해당 문제 역시 시뮬레이션 문제였다. 공기청정기의 조건들과 그 외 문제들의 조건들 덕에 조금 헤매긴 했지만 하드코딩으.. 백준 14502_연구소 문제 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 해당 문제는 DFS와 BFS를 모두 활용하는 시뮬레이션 문제였다. 먼제 바이러스의 확산에서 나는 상하좌우 한 번씩의 감염이 시작되.. 백준 15683_감시 문제 : https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 www.acmicpc.net 해당 문제는 DFS로 해결했다. CCTV들의 위치를 기록해두고 해당 CCTV들의 방향을 하나씩 조정해가며 모든 CCTV의 방향을 .. 백준 14890_경사로 문제 : https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 마찬가지로 시뮬레이션 문제이다. 행열을 뒤집어서 체크하고 싶으면 입력을 받을 때, a[i][j] 뿐 아니라 b[j][i]로 뒤집어서 같이 받으면 커버 가능하다. 구현할 때, 경사로의 조건 중에서 높이 차이가 1만 허용한다는 사실을 반드시 명심해야 한다. 이를 통해 1이상이 차이가 나면 결코 길이 만들어질 수 없다. 나는 문제 접근을 실제 경사로를 만들어 해당 길이 내림차순 또는 오름차순으로 한방향으로 정리되면 .. 백준 14503_로봇 청소기 문제 : https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 시뮬레이션 문제 중에서도 쉬운 편에 속한다(고 한다... 나한테는 어렵다...) 기본적으로 문제가 주어진 조건에만 유의해.. 백준 14891_톱니바퀴 문제 : 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 해당 문제도 역시 시물레이션 문제였다. 그래서 상황을 코드로 옮기는 것에 주안을 해야하는데, 문제의 조건을 하나 잘못 이해한.. 이전 1 2 3 4 5 6 7 다음
