알고리즘

[C++] 백준 15684번 사다리 조작

15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 백트래킹 문제. 삼성 SW 기출문제에 있어서 풀어봤는데, 구현 문제가 아니라 시뮬레이션 문제였다. (사실 거의 구현에 가깝다.) 시간 초과를 줄일 수 있는 방법이 떠오르지 않아서 게시판을 계속 봤는데 원하는 게시물이 없어서 많이 헤맸다. 그러다 한 게시물을 찾아서 탐색시, 중복을 제거하라는 것을 보고 맞출 수 있었다. 백트래킹은 중복을 줄여야 맞출 수 있다는 것을 다시 한 번 배운 문제다. 사실 아직도 왜 맞은지는 잘 모르겠다. 시간 복잡도를 계산했을때, 탐색하..

[C++] 백준 11660번 구간 합 구하기 5

다이나믹 프로그래밍 문제의 한 분야인 누적 합 문제. 처음에는 어떤 문제인지 몰라서 헤맸는데, 검색해서 이렇게 푸는 문제구나 라고 알게된 후 풀었다. 누적 합이라는 알고리즘을 사용해서 푸는 대표적인 문제였다. 문제풀이 문제에서 입력하는 (x1, y1)과 (x2, y2)를 입력받으면, 구간의 사이즈가 정해진다. 문제의 예시인 (2, 2)부터 (3, 4)까지라면 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 위에 파란색 배경에 흰색 글자로 된 숫자들이 구간으로 된다. 즉, x1이 행의 시작, y1이 열의 시작이 되고 x2가 행의 끝 y2가 행의 끝이 된다. 따라서 우리는 입력을 받을 때, 누적 합의 정보를 배열로 저장해놔야 한다. 어떻게 저장할 수 있을까? 누적 합 저장하기 나 같은 경우에는 위처..

[C++] 마법사 상어와 비바라기

구현 / 시뮬레이션 문제. 삼성 SW 역량 테스트 기출 문제였다. 삼성은 구현하는 문제를 참 좋아하는 것 같다. 천천히 정리하고 생각한 로직대로 풀면 되는 문제다. 문제풀이 문제의 주요 내용들을 정리해보자면 다음과 같다. 구름의 이동은 1행과 N행, 1열과 N열이 연결되어 있다. -> N + 1 -> 1, 0 -> N이 되면 된다. 최초 비바라기 시전 시 (N - 1, 1), (N - 1, 2), (N, 1), (N, 2)에 구름이 생긴다. 비바라기 시전 후에는 아래 로직들이 M번 반복된다. 모든 구름을 방향 D로 S번 이동한다. 모든 구름의 이동을 마치고 나면, 물의 양을 1 증가한다. 그리고 구름이 사라진다. 구름이 있던 곳에 물 복사 버그를 한다. 대각선 방향에 물이 있는 바구니의 수만큼 해당 지점..

[C++] 백준 15685번 드래곤 커브

15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 구현 / 시뮬레이션 문제. 삼성 SW에도 나왔다고 하는 문제다. 정답률이 높아서 풀어봤는데 마지막에 좌표를 이상하게 설정해서 틀렸었다. 좌표가 0부터 100까지인데 1부터 100까지만 고려해서 틀렸었다. (컴공은 1이 시작이 아니라 0부터 시작인데, 난 컴공이 아닌가보다;) 문제풀이 입력은 X좌표, Y좌표 순서이고, 각 방향에 따라 이미 숫자를 준다. 0 : 우 1 : 상 2 : 좌 3 : 하 3 3 3 0 1 4 2 1 3 4 2 2 ..

[C++] 백준 2493번 탑

스택을 이용해서 푸는 문제. 우선순위 큐로도 풀 수 있는 문제다. 자료구조의 기본적인 문제라고 한다. 평이 좋았던 문제였다. 문제풀이 탑들은 왼쪽 방향으로 레이저 신호를 보낸다. 만일, 자신의 왼쪽에 자신의 높이보다 큰 탑이 있을 경우에, 그 탑이 자기 자신의 레이저 신호를 받는 탑이 된다. 레이저 신호는 하나의 탑만 수신 가능하다. 즉, 스택, 우선순위 큐를 이용해서 탑의 높이를 기록해두는데, 지금 내가 탐색하는 탑의 높이보다 높은 탑의 높이가 나올 때까지 pop한다. 어차피 지금 탐색하는 탑보다 낮은 높이의 탑은 필요가 없기 때문이다. 그리고 stack에 넣을 때, 해당하는 높이가 몇번째 탑인지도 기록해 주어야 한다. 예제 6 9 5 7 4를 예로 들어보자. 1. stack : empty input ..

[C++] 백준 16234번 인구 이동

구현 / 시뮬레이션 / 그래프 탐색 - 너비 우선 탐색 문제. 인구 이동이 같은 날에 동시에 일어날 수 있다는 것을 생각하고 풀어야 한다. 위 부분을 생각하지 못해서 게시판을 참고하면서 왜 테스트 케이스가 다르게 나오는지 확인했던 문제였다. 문제풀이 N x N 크기의 땅이 있을 때, 인접한 두 땅의 인구 수 차이가 L이상, R이하라면 연합을 한다. 그리고 연합 땅들의 인구 수를 (연합의 총 인구수 / 연합의 칸의 개수)로 만든다. 사실 BFS로 풀면 어려운 조건은 없다. 그러나 유의해야 할 점이 있다. 위에서 말한 것 처럼, 우리는 인구 이동의 수가 아닌, 며칠동안 인구 이동이 지속되냐 이다. 따라서 같은 날에 인구 이동이 2번, 3번, 4번, ... 이렇게 발생해도 결국 우리는 며칠동안 지속되는지만 확..

[C++] 백준 15683번 감시

15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 문제가 길어서 링크로 대체하겠다. 구현, 시뮬레이션, 브루트 포스 문제. 노가다해서 풀었는데, 사실 마땅한 좋은 방법이 딱히 떠오르지가 않았다. 코드 길이가 너무 길어서 비효율적이라고 생각하지만, 시간은 빠르게 나왔다. 문제풀이 CCTV가 1번부터 5번까지 있다. 각 번호마다 감시하는 방향이 존재하는데, CCTV는 90도 회전이 가능하다. 이 때, CCTV들의 방향을 설정해서 사각지대가 최소가 될 때 몇 개가 되는지 구하는 문제이다. 1번 CCTV가 가..

[C++] 백준 11404번 플로이드 - 다시 풀어야함

플로이드-와샬 알고리즘을 사용해서 푸는 문제인데, 다익스트라를 사용해서 풀었다. 나중에 플로이드-와샬을 공부한 후 다시 풀어봐야겠다. 다익스트라 풀이 다익스트라는 BFS와 비슷하다. 따라서 queue를 사용해야 한다. queue STL을 사용했다. 그리고 인접리스트에서 번호와 비용을 저장하기 위해 vector STL을 사용했다. 각 도시의 개수 vertexCnt, 버스 노선의 개수 edgeCnt, 정답배열인 answer배열, 그리고 해당 도시를 방문했는지를 저장하는 visit 배열이 있다. answer 배열은 정답(한 정점에서 특정 정점까지의 비용을 저장하는 배열)을 저장한다. 미리 1억을 넣어주어서, 만일 특정 정점까지 가는 비용이 발생했을 때 초기에는 갱신이 될 수 있도록 1억을 넣어준다. 도시의 개..

[C++] 백준 4179번 불!

그래프 탐색 문제. 최근에 이런 비슷한 문제인 3055번 탈출이라는 문제를 풀다가 실패했었다. 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 아예 조건이 똑같던 문제였는데 불! 문제는 풀었었다. (오히려 정답률은 탈출이 높다..뭐지..?) 다른 사람들 풀이를 보니 조금 쉽게 접근한 거 같았다. 시간도 내가 훨씬 많이 걸리고 있었다. 다른 사람들 코드를 봐도 크게 다른 점은 못 찾았다. 아마 priority_queue를 custom해서 쓰는데, 이게 문제인 것 같았다. queue 자료구조만 사용해서 풀어도 풀 수 있는 문..

[C++] 백준 10819번 차이를 최대로

백트래킹 문제. N의 크기가 3부터 8이다. 따라서 최대 경우의 수가 8! 이므로 40,320번 안에 모든 탐색을 마칠 수 있다. 처음에 부등호를 잘못 표기해서 틀렸습니다. 를 받았다. 백트래킹인 것을 알고서 접근하면 어려운 문제는 아니다. 문제풀이 문제 그대로 구현해주면 된다. 순차적으로 가능한 모든 배열의 경우의 수를 만들어서 그 중 최대값을 골라서 갱신하면 된다. 어려운 부분은 없으므로 바로 코드로 설명하겠다. vector를 사용하기 위한 vector STL, max() 메서드 사용을 위한 algorithm, 절대값 abs() 메서드 사용을 위한 math.h를 사용했다. numCnt : 배열에서의 숫자의 개수 arr 배열 : 처음에 입력받는 숫자들을 저장할 배열 visit 배열 : 백트래킹 메서드를..