boj

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

15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 완전 탐색, 백트래킹 삼성 SW 기출 1. 문제 해결 아이디어 처음에 문제에 대한 감이 안 왔다. 백트래킹이라기엔 H가 너무 커 보였고 그래프라 하기엔 간선 정보를 어떻게 담아야 할지 생각이 안 났다. 그러다 완전 탐색 문제라는 말을 듣고 힘들게 접근을 시도할 수 있었다. 지금까지 만든 사다리에서 사다리 타기를 했을 때 각 line의 도착점이 시작 line의 번호와 같아야 true를 return 하는 함수를 만들었다. 그리고 사다리를 놓지 못하는 조건을 걸어주고..

[백준 17144] 미세먼지 안녕! C++

17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 시뮬레이션 삼성 SW 기출 1. 문제 해결 아이디어 [백준 17143] 낚시왕 C++ 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래 hyeo-noo.tistory.com 낚시왕 문제와 느낌이 비슷했다. 시뮬레이션 문제는 문제에 어떻게 구현해야 하는지 자세히 나와있어서 풀이라고 할 게 없다. ..

[백준 1613] 역사 C++

1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 플로이드-와샬 1. 문제 해결 아이디어 사건들의 전후 관계를 파악하는 문제라서 처음에 바로 위상 정렬로 풀기 시작했었다. 근데 위상 정렬을 해놓으니 관계도는 명확히 그려지지만 임의의 정점 2개를 선택했을 때 해당 정점들이 서로 어떤 관계에 있는지 알아보려면 매번 BFS가 필요해 보였다. 효율이 안 좋게 느껴졌고 위상 정렬은 아닌 것 같아 알고리즘 분류를 켜서 어떤 알고리즘을 써야 하는지 힌트를 받았다. 플로이드-와샬 알고리즘을 쓰는 문제였다. N이 400..

[백준 17143] 낚시왕 C++

17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 시뮬레이션 삼성 SW 기출 1. 문제 해결 아이디어 1. 낚시왕은 0번 col에서 오른쪽으로 한 칸 이동 2. 낚시왕이 있는 열에서 땅과 제일 가까운(row값이 가장 작은 상어)를 잡는다 3. 상어이동 상어 - 방향, 크기, 속도 특정방향으로 이동하다가 벽을 만나면 방향을 바꿔서 뒤로 감 상어 객체 생성 모든 상어가 일단 이동하고 겹치게 된 상어가 있으면 크기가 가장 큰 애들만 살아남음 맵에는 상어가 2마리 이상 있다는걸 알 수 있는 장치가 필..

[백준 11779] 최소 비용 구하기 2 C++

11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 1. 문제 해결 아이디어 A 도시에서 B 도시로 가는 최소 비용을 알아야 한다. 간선의 비용은 음수가 없다. 위 두가지 정보로 다익스트라문제인걸 알았다. 다익스트라 알고리즘에 의해서 도착점을 발견하면 현재 가지고 있는 최소 비용이 도착점 까지의 비용이된다. bfs를 수행하면서 현재 정점에 도달하기 직전에 거쳐온 정점을 저장해둔다. 예시 입력을 그래프로 나타냈다. 1이 시작점이고 우선순위 큐에 의해서 queue에 4, 2,..

[백준 14003] 가장 긴 증가하는 부분 수열5 C++

14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 이분 탐색 1. 문제 해결 아이디어 [백준 12015] 가장 긴 증가하는 부분 수열2 C++ 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 이전까지 풀.. hyeo-noo.tistory.com 위 문제에서 추가적인 요소만 넣어준다면 해결 ..

[백준 3055] 탈출 C++

3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS 1. 문제 해결 아이디어 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 위 문제랑 거의 똑같은듯 하다 고슴도치는 물이 곧 차오를 지역으로 가지 못하기 때문에 bfs를 통해서 물을 먼저 채워준다 이때 채워진 물을 nextwater 큐에 넣어준다. 물은 . 부분에만 채워질 수 있다. 물..

[백준 14891] 톱니바퀴 C++

14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 시뮬레이션 삼성 SW 기출 1. 문제 해결 아이디어 하나의 톱니가 돌아가면 다른 톱니도 돌아가야하므로 연쇄반응을 구현해야한다. 재귀로 풀어내려고 했고 현재 바퀴를 시계/반시계 방향으로 회전시키기 전의 3시, 9시 방향의 자기정보를 가지고 있어야 한다. 현재 영향을 주는 방향을 매개변수로 입력받아서(lr) (0은 양방향, 1은 오른쪽으로, -1은 왼쪽으로) 영향을 줄 바퀴를 정해서 함수를 호출했다. 로직은 이게 전부인듯 하다. 삼성 SW기출답게 구현력을 요구하는..

[백준 6087] 레이저 통신 C++

6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net BFS 1. 문제 해결 아이디어 처음에 시뮬레이션 문제인가? 생각했는데 그냥 BFS에 조건이 몇 개 추가된 문제였다. 먼저 DP풀듯이 각 칸에 도달하기 위한 최소 거울의 개수를 구해야 겠다는 생각을 했다. 그리고 이미 방문한 칸에 다시 도달할 수 있어야 올바른 최솟값을 구할 수 있다고 깨달았다. 가장 기본적으로, 주어진 W, H 범위 내에서만 움직여야하고, 벽인 경우 que에 넣으면 안된다. que의 초기값이 하나의 점이 아니라 임의의 C에서 4방향으로..

[백준 14890] 경사로 C++

14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 시뮬레이션 삼성 SW 기출 1. 문제 해결 아이디어 구슬 탈출 2 문제를 풀다가 코드가 너무 길어지고.. 구현이 더러워져서 도망치듯 풀게 된 문제다. 도망쳐왔지만 이 문제도 절대 만만하진 않았다. 분명 문제에는 경사로는 서로 겹치면 안 된다고 적혀있어서 가로와 세로 경사로끼리도 겹치면 안되는줄 알았다. 그런데 알보고니 가로 경사로와 세로 경사로는 서로 영향을 주지 않기 때문에 문제가 더 쉬워졌다! 가로길 + 세로길 해주면 답이 나오게 되었다! 문제 설명이 부실한듯해서 시간을 좀 잡아먹었..