live the life you love

www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 카테고리 분류에 BFS가 있어서 당황했던 문제이다. 이런류의 문제를 BFS에 접목시킨다는 발상을 하기가 어렵다. 실제 코테에 나왔다면 못풀었을 것이다. 어려웠고 놓쳤던 부분은 다음과 같다. '123' 을 R 연산하면 312가 아니라, '2031'이된다. 숫자는 무조건 4자리로 고정되어있기 때문이다. 숫자 하나당 4가지의 경우의 수가 발생해서 4^n 만큼의 경우의 수가 나올 거 같은데, 어떻게 시간 ..

www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 문제의 구현 로직은 다음과 같다. 모든 치즈가 다 녹았는지 확인한다. 남은 치즈가 있다면 전부 녹을 때 까지 아래의 과정을 반복한다. 다른 치즈 내부 공간에 있지 않은 치즈들 중 외부 공기와 2개 변 이상 접촉한 치즈를 체크한다. 체크된 치즈를 녹인다. 1, 3번은 크게 어렵지 않은데 2번이 조금 까다로운 편이었다. 단순히 상,하,좌,우 중 공기인 칸이 2개 이상인지만 확인하면 안된다. 왜냐하면 상하좌..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 전형적인 BFS 탐색을 활용해서 푸는 문제였다. 상근이는 무조건 집 -> 편의점 -> 편의점 .. -> 페스티벌 로 움직이기 때문에 다음번 편의점에 가서 항상 맥주를 최대로 살 수 있다. 굳이, 이동할 때 마다 이동거리를 50m로 나누면서 이동 가능 여부를 판단하지 않고 맥주를 20개 먹었을 때 갈 수 있는 최대 거리인 1,000m를 기준으로 다음번 편의점 또는 페스티벌 장 까지의 거리가 1..

www.acmicpc.net/problem/16113 16113번: 시그널 zxcvber는 외계인을 연구하는 과학자다. 그는 지난 10년간 우주에서 오는 시그널를 연구했지만, 아무런 성과가 없었다. 그러던 어느 날, 갑자기 우주에서 이상한 시그널이 오기 시작했다. zxcvber는 � www.acmicpc.net 시뮬레이션 문제였다. 구현 방법을 떠올리는데 크게 어렵진 않았지만, 사소한 오류를 고치는 과정이 꽤 걸렸다. 또한, 코드도 깔끔하지 않다. 중복된 코드도 있고 예외처리를 위해 goto를 사용했다.. 좀 더 깔끔하게 짤 방법이 있을 것이다. 문제 해결 방법 디지털 숫자를 위에서 아래로 읽었을 때 나오는 값을 '#'과 '.' 의 형태의 문자열로 따로 저장해둔다. 예를들어 2라는 숫자를 왼쪽 위에서 시..

처음에는 어떤 유형의 문제인지 감을 못잡아서 2번 실패를 했다. 병사는 자신의 위치를 유지해야 하므로 따로 정렬을 하면 안되고, 그 안에서 내림차순으로 가는 가장 긴 수열을 찾아야 한다. 즉 LIS 알고리즘을 사용하면 된다. 이때, LIS는 최장증가부분수열이지만 이 문제는 숫자가 감소하는 길이가 가장 긴 것을 찾아야 하므로 최장감소부분수열을 찾으면 된다. LIS는 이중 for-loop을 사용하여 시간복잡도가 O(n^2)인 방법과 이분탐색을 사용하여 시간복잡도가 O(nlogn)인 방법이 있다. 이 문제는 N이 최대 2000이므로, O(n^2)의 시간복잡도를 가진 방법을 사용해도 무리가 없다. 소스코드 #include #include #define MAX 2000 using namespace std; int..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 벽을 세울 수 있는 위치를 찾기 위해 next_permutation을 사용하였다. 연구소의 크기가 최대 8X8이고, 벽은 3개를 세워야 하..

다익스트라에 대한 문제를 우선순위 큐를 사용하여 풀어보았다. 우선순위 큐는 최대 힙의 구조를 가지고 있는데, 최소 비용을 탐색해야하기 때문에, 비용 값을 음수화 하여 힙에 넣었다. 이 코드는 내가 구현한 코드가 아니라https://jaimemin.tistory.com/555 의 코드를 참고하였다. 함수의 형태가 void나 int가 아닌 vector를 사용하였는데 이런식의 코드 구현은 처음해봤다. return값을 담는 부분을 유의해야 할 것같다. 우선, 전역변수는 다음과 같이 선언하였다. #include #include #include const int MAX = 20001; const int INF = 987654321; using namespace std; int V, E, K; vectorgraph[..

덱(Deque)을 사용하는 문제 중 하나. 문제를 이해하는데는 많이 어렵지 않았지만, 배열의 입력이 [1,2,3] 으로 들어오는 것을 처리하는게 까다로웠다. 빈 배열이 입력되는 경우 덱의 자료형이 int이기 때문에 원소 사이사이 쉼표를 넣고 마지막 원소에는 쉼표를 넣지 않는 처리 ex) [1,2,3,] 이렇게 되지 않도록 또한, 'R' 입력의 경우 실제로 덱을 reverse 하는것이 아니라 flag 변수를 선언하여 배열이 reverse 상태인지 확인만 시켜주어야 시간초과가 안난다. 테스트 케이스가 첫줄에 주어지는 문제여서 사용한 변수들의 초기화도 중요한 부분이다. 이 문제에서는 덱만 초기화 시켜주면 되었다. 처음에 문제를 풀때 덱의 자료형을 'char'로 선언하였다. 이렇게 하면 숫자가 두자리 숫자일 때..

기존의 백준 문제들과는 달리, 테스트케이스의 개수가 주어지다 보니 사용했던 벡터, 배열의 초기화가 필요했다. 코드에는 graph[j].clear()로 되어있지만, 처음에는 graph->clear()로 나와서 어떤게 문제인지 고민했다. 이분그래프란 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 2가지 색으로만 칠할 수 있는 그래프이다. [문제 해결 방법] color 배열을 만들어서 방문 정점, 정점과 이어진 정점의 숫자를 다르게 하여 설정하였다.(빨강 = 1, 파랑 = 2) 초기화 : 0 첫 정점 방문시 : 1 color가 1인 정점과 연결된 정점 : 2 color가 2인 정점과 연결된 정점 : 1 정점이 100개 이어져 있다고 해도, 1~4번 정점 사이에 이분그래프가 만들어지지 않으면 절대 이분그..

https://www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열의 앞과 뒤에는 공백이 있을 수도 있다. www.acmicpc.net getline(cin, str)을 사용해볼 수 있는 문제였다. "Hello world"와 같은 입력을 받는 경우 cin>>str을 하면 str에는 Hello 까지만 담기게 된다. getline의 경우 공백을 포함하여 입력을 받기 때문에 공백이 있는 문자열 처리에 사용하기 좋다. [문제 해결 방법] 공백의 아스키 코드값인 32를 확인하여 단어의 개수..