본문 바로가기

전체 글139

[백준 17070] 파이프 옮기기 1, C++ https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 www.acmicpc.net 본 문제는 가로, 세로, 대각선으로 파이프를 설치하여 n-1, m-1에 도착하는 경우의 수를 출력하는 문제다. 1은 벽이고 .. 2020. 4. 22.
[백준 16933] 벽 부수고 이동하기 3, C++ https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 벽 부수고 이동하기 시리즈 문제다. 0은 빈 칸, 1은 벽이다. 이동하는 방법은 상하좌우로 움직일 수 있고, 그 자리에 멈출 수 도 있다. 부술수 있는 벽의 개수가 주어지고, 벽은 낮에만 부술수 있다. 따라서 위치 좌표, 벽을 부순 개수, 낮밤을 저장할 4차원의 배열이 필요하다. 벽 부수고 이동하기 2 문제에서 낮밤만 추가된 문제로 낮밤을 표시하기 위해 3차원 .. 2020. 4. 22.
[백준 15683] 감시, C++ 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 본 문제는 주어진 cctv를 회전하여 사각지대의 최솟값을 구하는 문제다. cctv는 총 5가지가 존재하여 회전은 4방향으로 가능하다. 따라.. 2020. 4. 16.
[백준 15662] 톱니바퀴 (2), C++ https://www.acmicpc.net/problem/15662 15662번: 톱니바퀴 (2) 총 8개의 톱니를 가지고 있는 톱니바퀴 T개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, ..., 가장 오른쪽 톱니바퀴는 T번이다. 아래 그림은 T가 4인 경우이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다 www.acmicpc.net 본 문제는 톱니바퀴 문제와 마지막 12시에 톱니 개수를 구하는 부분만 다른 문제다. 톱니바퀴 문제를 풀 때를 생각해보면 참 어.. 2020. 4. 12.
[백준 1938] 통나무 옮기기, C++ https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 n; vector B; vector E; for (int i = 0; i > s; for (int j = 0; j 2020. 3. 30.
[프로그래머스] level 3 - 단어 변환 https://programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 본 문제는 프로그래머스 level 3 문제로 DFS 문제다. 개인적인 생각으론 프로그래머스는 BFS 보다 DFS를 이용하여 풀었을 때 코드가 간결하고 쉽게 풀리는거 같다. 최단 거리를 구하는 문제는 BFS를 사용하는게 빠르지만 이 문제는 DFS를 이용하였고 target에 도착할 때 마다 값을 비교하여 최솟값을 구하였다. 자세한 설명은 주석처리 하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14.. 2020. 3. 27.
[프로그래머스] level 3 - 보행자 천국, C++ https://programmers.co.kr/learn/courses/30/lessons/1832 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 본 문제는 2017 카카오코드 예선 문제로 DFS 문제를 활용한 DP 문제다. 예를들어 DP 문제는 d[i] = MAX( d[i-1], d[i-2] )와 같이 작은 문제로 나누어 계산하는 방식인데 중복되는 경우가 많을 경우 1번만 계산을 하여 연산량을 줄이는 방법이다. /* 개인적인 DP 문제 해결 방법은 점화식이 바로 떠오르면 아! DP 문제구나 하고 bottom up으로 풀다. 그게 아니면 먼저 모든 경우를.. 2020. 3. 26.
[프로그래머스] level 3 - 여행경로, C++ https://programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 본 문제는 DFS 문제로 주어진 모든 항공권을 이용하여 여행하는 방법을 찾는 문제다. 이때, 경로가 여러개인 경우 알파벳 순으로 앞선 경우를 return 한다. 다른 어려운 DFS/BFS 문제들은 연산량이 많아 메모리 초과가 되어 다른 방식으로 DFS/BFS 연산을 해야 하는데 이 문제는 딱 한가지 경우를 생각 못하면 풀기 힘든 문제다. 바로 [["ICN", "COO"], ["ICN", "BOO"], ["CO.. 2020. 3. 26.
[프로그래머스] 2020 KAKAO BLIND RECRUITMENT - 자물쇠와 열쇠, C++ https://programmers.co.kr/learn/courses/30/lessons/60059 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 본 문제는 2020 KAKAO BLIND RECRUITMENT 문제로 정답률 7.4%다. 문제를 보면 설명이 좀 길다. 간단하게 설명하면 키를 회전과 이동을 하여 자물쇠의 모든 값이 1인 경우 true를 return하는 문제다. 문제 해결 과정은 다음과 같다. 우선 개인적으로 프로그래머스에서 vector로 입력되는게 싫다. 따라서 2차원 배열로 값을 저장하였다. cal() 함수를 이용해 키를 회전하였다. 배열.. 2020. 3. 24.

티스토리툴바