본문 바로가기

구현9

[C++,구현, 중복 순열] 백준 17825번 주사위 윷놀이 문제풀이 https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 주사위 윷놀이, 구현에서도 어려운 축에 속한다고 생각한다. 주사위에서 나올 수 있는 10개의 수 순서에 각각 4개의 말들을 매칭 시킨다고 하면 중복 순열이다. 전체의 경우의 수는 4^10 가지가 나온다. 처음에는 아래와 같이 풀이하였다. #include #include using namespace std; typedef struct lo { int x, y; }; int pan[4][30] = { { -1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 3.. 2020. 6. 1.
[C++,구현,BFS,DFS] 백준 15686번 치킨 배달 문제풀이 문제링크 백준 15686번 치킨 배달 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net DFS,BFS를 모두 쓴 조금은 힘든? 문제이다. 최대 M개의 치킨집을 고르는 건 DFS, 치킨집을 골라 최소거리를 구하는 건 BFS로 구현하였다. 밑에 코드에 나.. 2019. 5. 25.
[C++,구현] 백준 16234번 인구 이동 문제풀이 문제 링크 백준 16234번 인구 이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net 문제를 풀고 나서 생각해보니 연합을 만들 때 DFS/BFS 어느 방법으로 해도 상관없을것 같다. 나는 DFS를 사용하였다. side case에 걸리지 않고 한번에.. 2019. 5. 24.
[C++,구현] 백준 17143번 낚시왕 문제풀이 문제 링크 백준 17143번 낚시왕 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하 www.acmicpc.net 코테에서 2문제 "완벽히" 풀 자신이 없다면 선택적으로 한문제 완벽히 맞추고 넘어가야 한다! 명심 또 명심! 1 2 3 4 5 6 7 8 9 10 11 12 13 14.. 2019. 4. 28.
[C++,구현] 백준 17144번 미세먼지 안녕! 문제풀이 문제링크 백준 17144번 미세먼지 안녕! 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼 www.acmicpc.net 이문제 1솔 했다고 생각했는데 결과는 불합이었다...ㅜ 수행시간이 문제였던건가ㅜ 아쉽다. 좀더 실력을 갈고 닦자 지금 다시 풀어보니 백준에서는 통과가 .. 2019. 4. 25.
[C++,구현] 백준 14890번 경사로 문제풀이 문제 링크 백준 14890번 경사로 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 오늘 종일 고민한 문제이다. 다른일이랑 같이 하려니 정신이 분산되어 머리만 더 복잡해지는거 같다ㅜㅜ 앞으로 조용한 곳에서 단시간 집중하고 해치워야겠다. 아이디어가 생각 나지 않아 구현이 어려웠다. 찾아보니 핵심아이디어는 현재까지 연속된 높이의 계단수를 세는것! 아이디어를 얻어 완성한 후 한번 WA를 받았는데 조건에 계단의 높이가 1일 차이일때만 경사로를 설치할 수 있다는 조건이 있었다. 문제도 제대로 읽자..ㅜ 1 2 3 4 5 6 7 8 9 10 1.. 2019. 4. 6.
[C++,구현] 백준 14891번 톱니바퀴 문제풀이 문제 링크 백준 14891번 톱니바퀴 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다. 톱니바퀴를 회전시키려 www.acmicpc.net 구현문제이다. 간단하다면 간단할 수 있는 문제인데 오류찾는거까지 순수하게 2시간정도 걸린거 같다ㅜ 문제를 많이 풀어서 보다 빠르고 능숙하게 풀도록 해야겠다. 1 2.. 2019. 3. 27.
[C++,구현] 백준 1764번 듣보잡 문제풀이, 배열,vector,map 속도비교 문제링크 백준 1764번 듣보잡 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. www.acmicpc.net 간단한 문제열 처리문제를 가지고 흔히 알고리즘에서 사용하는 단순 배열, STL vector, STL map을 써서 다양한 방법으로 문제를 풀어보고 속도차이를 비교해보려 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #in.. 2019. 3. 26.
[C++,구현] 백준 14499번 주사위 굴리기 문제풀이 문제링크 백준 14499번 주사위 굴리기 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마 www.acmicpc.net 구현문제를 풀어보았다. 구현문제가 익숙치 않아 코드도 길고 복잡하게 짜버렸다ㅜㅜ 다른분들의 코드를 보면서 최적화 시켜야겠다. 1 2 3 4 5 6 7 8 .. 2019. 3. 14.

티스토리툴바