알고리즘

[C++] 백준 2110번 공유기 설치

이분 탐색 문제. 시간 복잡도가 이게 되나? 생각되는 문제지만 이분 탐색 + 되는지 순차적으로 확인 해주면 풀리는 문제이다. 많이 틀렸었는데, 이유는 이분탐색 최소부분을 1부터 시작하지 않고 집의 번호들 중 가장 작은 부분부터 시작해서 틀렸다. 문제풀이 이분 탐색을 하면서 나오는 숫자들을 하나씩 가능한지 여부를 살펴보면 된다. 이분 탐색은 늘 그렇듯 front < tail일 때까지 고려해주면 된다. front는 1로 시작해야한다. 처음에 이 부분을 간과해서 집 번호 중 가장 작은 부분부터 시작해서 틀렸다. 만일 집이 3개가 있고 2개의 공유기를 설치한다고 해보자. 집의 번호가 각각 10000, 10001, 10002 이렇게 있다면 가장 멀리 공유기를 설치하는 법은 10000, 10002 이렇게 된다. 따..

[C++] 백준 1707번 이분 그래프

그래프 탐색 문제. 처음에 진짜 말도 안되는 방법으로 구현했다가 틀렸다. (아무 생각없이 풀어버렸다.) 근데 또 예제들은 잘 나와서 뭐가 틀렸는지 몰랐는데 반례 게시판에 나와있는 반례를 통해 해결했다. 이번에 대회에 이분 그래프 문제가 나왔었는데,(사실 이분 그래프보다는 심화적인 내용이였다. 당연히 못풀었음ㅠ) 이분 그래프 문제는 유명한 문제 같아서 이번에 풀어봤다. 문제풀이 문제내용에 따르면 그래프에서 인접하지 않은 정점들끼리 집합을 나눌 수 있는 그래프인지 여부를 확인하면 된다. 그래프에서 정점에 색을 칠하는데, 인접한 정점끼리는 다른 색을 가지게 되면 해당 그래프를 이분그래프라고 할 수 있다. 나는 이 문제를 내가 빨간색, 파란색 붓만 가지고있고, 색칠되지 않은 정점에 빨간색 붓을 칠하면서 시작하고..

[C++] 백준 17142번 연구소 3

17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 에 수록된 문제. 골드 4 문제이며 연구소 문제의 후속작(?)인 것 같다. 연구소 문제는 골드 5에 정답률도 55%를 기록하고 있지만, 이 문제는 골드 4에 정답률이 25%를 기록하고 있다. 연구소 문제는 그래프 탐색 이론 문제이고, 너비 우선 탐색(BFS)을 통해서 푸는 문제이다. 사실 왜 맞았는지 잘 모르겠다. TC들이 제대로 나오지 않길래, 조건을 조금 수정해서 TC들이 잘 나와서 제출했더니 맞았습니다!! 가 나와버렸다... 한번 글..

[C++] 백준 21608번 상어 초등학교

21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 에 수록된 문제. 실버1 문제이고 나온지 얼마 안 돼보이는 문제였다. 문제가 과하게 친절하게 해야할 것들을 다 알려준다. 문제에 나온대로만 구현해주면 풀 수 있다. (물론 나는 학생 수를 잘못 고려해서 틀렸다. 아마 대부분 사람들이 이것때문에 런타임 에러나서 틀린 것 같았다. 학생 수가 N * N명인데, N으로만 생각해서 틀렸다. 좀 더 생각했으면 좋았을 것 같은데, 게시판에 누가 이렇게 올려놓은 걸 보고 바로 알 수 ..

[C++] 백준 20055번 컨베이어 벨트 위의 로봇

20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 에 수록되어 있는 문제중 하나. 실버1 문제이고, 정답률이 높길래 풀어봤는데, 문제가 상당히 표현이 애매모호하게 되어있다. 게시판을 참조해서 사람들이 해석해준 방법을 보고난 후에 풀 수 있었다. 문제풀이 문제의 조건을 정리하면 다음과 같다. 컨베이어 벨트는 2층구조이고, 1층은 1 ~ N, 2층은 N + 1 ~ 2N의 범위이다. (2층은 2N ~ N + 1이라고 생각해야한다.) 각 컨베이어 벨트 칸 하나마다 ..

[C++] 백준 17779번 게리맨더링 2

17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 에 수록된 문제. 구현 / 브루트포스(완전탐색) / 시뮬레이션 문제. 처음에 조건 한줄을 잘못설정해줘서 계속 틀렸다. 반복문에서 break를 걸어주어야 하는데, continue를 써준게 틀린원인이였다. 정답률도 높은 편이고 생각한대로 구현을 잘 해주면 쉽게 맞출 수 있는 문제였다. 문제풀이 문제의 조건을 요약하면 다음과 같다. 선거구를 5개로 나눈다. 선거구를 나누는 것은 기준점 x, y와 길이 d1, d2를 정해서 나눠준다. d1은 ..

[C++] 백준 17140번 이차원 배열과 연산

구현 / 정렬 / 시뮬레이션 문제. 삼성 S/W 기출문제 중 한 문제이다. 문제에 나온 그대로 구현하면 시간복잡도 고려할 필요없이 맞출 수 있다. 조건들이 생각보다 복잡하지만 골드4 구현 문제치고는 쉬운 편에 속한다고 생각한다. 정답 비율도 높은 걸 보면 쉽게 풀 수 있는 것 같다. 문제풀이 구현 문제는 문제에 나온 내용을 잘 정리하는 것이 중요하다. 문제의 내용을 간략하게 정리하면 다음과 같다. 배열 A의 최초 크기는 3x3이다. 그리고 1초마다 다음과 같은 연산을 한다. 행의 길이 >= 열의 길이 일 경우, 배열 A의 모든 행을 정렬 행의 길이 < 열의 길이 일 경우, 배열 A의 모든 열을 정렬 배열 A를 정렬하기 위해서는 각 수가 몇번 나왔는지 알아야 하고, 정렬의 우선순위는 다음과 같다. 등장횟수..

[C++] 백준 14890번 경사로

14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 삼성 SW 기출문제. 구현 문제이며, 골드3 문제치고는 높은 정답률을 기록하고 있다. 문제에서 세부조건들까지 상세하게 줘서, 문제에 있는 그대로 구현만 하면 맞출 수 있는 문제다. 문제풀이 문제의 조건들을 간략하게 요약해보면 다음과 같다. N x N 지도에서, 나갈 수 있는 길을 찾는다. 나갈 수 있는 길이란 해당 길에서 높이가 모두 같은 곳을 의미한다. 나갈 수 있는 길은, 1행 또는 1열의 모습으로 나타난다. 따라서 최대 2N개가 가능하다. 길에는 경사로를 설치할 수 있다. 경사로에..

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

17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 구현 / 시뮬레이션 문제. 처음에 상, 하, 좌, 우를 움직이길래 BFS문제인 줄 알았는데 아니였다. (BFS와 비슷하게 구현하긴 했다.) 삼성 SW기출문제에 나와있는 문제다. 골드4 문제치고 반례같은 것도 없었다. 정답률도 높은 편이였다. 문제풀이 문제를 다음과 같은 순서대로 구현만 해주면 된다. 1. 미세먼지 확산. 이 때 상, 하, 좌, 우 방향으로 확산되는데 확산되는 미세먼지의 양은 A/5이다. 그런데 확산되는 방향 중 공기청정기가 있거나, 공간이 없는 ..

[C++] 백준 17135번 캐슬 디펜스

구현 / 시뮬레이션 문제. 삼성 A형 기출 문제에 수록되어 있는 문제다. 조합, 구현으로 문제를 풀었는데 그래프 탐색 이론으로도 풀 수 있다고 한다. (그래프 탐색 이론은 상상도 못했고 지금도 잘 감이 안온다. 아마 궁수마다 BFS돌면서 제일 가까운 적을 죽이는 방식인 것 같다.) 골드 구현 문제를 많이 풀어봤다면 시도해볼법한 문제였다. 처음에 테스트 케이스를 다 맞춰서 문제를 푼 줄 알았는데, 자꾸 31%를 못넘었었다. 나는 적들의 좌표를 기록해주고, 거리와 c값에 따라 정렬해 준 후에 푸는 방식으로 풀었는데, 죽은 적들의 좌표를 기록에서 지워주지 않아서 틀리고 있었다. 문제풀이 각 문제의 조건들을 어떻게 해결할 수 있을까? 1. 두 위치의 거리는 |r1 - r2| + |c1 - c2|로 해결할 수 있..