본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 12100번 : 2048(Easy) www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net Easy?? 하지 못한 시뮬레이션 문제였습니다. 풀이방법 1. 각 합치는 방향을 0,1,2,3(상,우,좌,하)으로 생각했을 때 4진법으로 5번의 이동을 4^5의 수로 표현할 수 있습니다. 2. 합칠 때 합친 결과를 출력할 필요가 없으므로 돌린뒤 위쪽방향으로 합치는 것으로 가정합니다. 어떤 이동의 방향이 0이라면 돌리지 않습니다. 방향이 1이라면 90도 오른쪽으로 돌린 뒤 위로 합칩니..
(C++) - 프로그래머스(고득점 kit - Greedy) : 단속카메라 programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 회의실 배정 문제와 같은 방식의 문제였습니다. 풀이방법 1. 고속도로에서 나가는 지점이 빠른 순으로 routes를 정렬해줍니다. 2. 고속도로의 전체 길이를 빠르게 탐색하기 위해서는 나가는 지점만 비교하는 것입니다. O(n)으로 routes의 원소를 나가는 지점만 비교해 지나가는 자동차의 수 가장 많이 겹치는 지점마다 answer변수를 더합니다. 어떤 자동차를 골랐을 때 그 자동차가 나가는 지점이 가장 빠르다면 그 지점보다 작은 지점에서 출발하는 모든 자동차를 단속할 수 있습니다...
(C++) - 프로그래머스(고득점 kit - Greedy) : 섬 연결하기 programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 크루스칼 문제였습니다. 풀이방법 1. 간선을 가중치의 오름차순으로 정렬합니다. 2. 사이클이 생기지 않는다면 n-1개의 간선을 union해준 후 뽑아줍니다. Code #include #include #include #include using namespace std; int parent[100001]; int find(int a){ if(a == parent[a]) return a; return a = find(parent[a]); } int unionParent(int a..
(C++) - 백준(BOJ) 1213번 : 팰린드롬 만들기 답 www.acmicpc.net/problem/1213
(C++) - 백준(BOJ) 15683번 : 감시 답 www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 시뮬레이션 문제였습니다. 풀이방법 1. 초기화 : 카메라의 개수를 구합니다 1 ~ 5사이에 있는 수들의 개수를 세준다면 카메라의 개수입니다. 이 때 회전상태를 저장할 수 있는 구조체를 만들어 x번째 카메라가 저장되어 있는 행,열의 좌표와 카메라의 종류 회전상태를 저장해줍니다. 2. 각 카메라의 회전횟수(상태)를 모두 확인해줍니다. 0번에서 ~ 1=m) break; if(office[x][y]==6) ..
(C++) - 백준(BOJ) 3029번 : 경고 답 www.acmicpc.net/problem/3029 3029번: 경고 첫째 줄에 현재 시간이 hh:mm:ss 형식으로 주어진다. (시, 분, 초) hh는 0보다 크거나 같고, 23보다 작거나 같으며, 분과 초는 0보다 크거나 같고, 59보다 작거나 같다. 둘째 줄에는 나트륨을 던질 시간 www.acmicpc.net 문자열을 처리하는 문제였습니다. 풀이방법 * 정인이는 1초 ~ 24시간 사이를 기다릴 수 있습니다. 따라서 시간이 같으면 24시간을 기다려야합니다. * 시 : 분 : 초 이렇게 출력시 시간부분이 24이상의 숫자가 출력되서는 안됩니다. Code #include using namespace std; int nowTime[3], doTime[3]; int sec1,sec2,waitTime; stri..
(C++) - 백준(BOJ) 9372번 : 상근이의 여행 www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net unoin find를 이용해 푼 문제였습니다. 풀이방법 1. 생각하기 : 국가의 개수가 n이라면 1 ~ n까지의 국가를 여행해야하기 때문에 국가를 노드로 생각하고 여행하는 경로를 간선이라고 생각해 모든 노드가 연결된, 사이클이 없는 양방향 그래프를 만드는 문제라고 생각할 수 있습니다. 2. union find : parent를 처음에는 다르게 둡니다. find를 이용해 두 ..
(C++) - 백준(BOJ) 5639번 : 이진 검색 트리 www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 재귀를 활용해 이진 검색 트리를 구현 한 뒤 후위순회를 하는 문제였습니다. 풀이방법 배열로는 풀 수 없습니다. 이진 트리의 구조상 자식이 최대 2개이므로 극단적인 경우에서 만약 노드의 수가 10,000개이고 한쪽 자식이 계속 없는 식으로 구성된다면 비어있는 자식을 표현하기 위한 배열공간도 필요합니다. 따라서 2^10,000의 배열 크기를 선언해야하는데 파일 크기 제한으로 seg fault를 맛볼 수..

티스토리툴바