live the life you love

https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다. 두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 www.acmicpc.net 어려운 자료구조나 복잡한 알고리즘이 있진 않았지만, 구현할게 많아서 귀찮았다. 타순에 따라, 득점하는 결과가 다르므로 최대 득점하는 타순을 ..

https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다 www.acmicpc.net 이 문제는 지난 19년도 삼성 하반기 역량테스트에 나온 문제이다. 다시 풀어보니 특별한 알고리즘을 사용하기 보다는 그냥 정말 요..

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net 문제에 사용한 알고리즘 bfs 문제 해결 순서 전체 그래프를 '.' 이 아닌 위치에서 bfs 탐색 bfs 함수는 모여있는 뿌요들의 개수를 return한다. 모여있는 뿌요들의 개수가 4개 이상인 경우 폭발하는 함수를 실행한다 memset으로 정점들을 초기화 시켜준다. --> 이부분이 중요 문제의 조건 중 '터질 수 있는 뿌요가 여러개 있을 경우 한번의 연쇄로 처리한다' 때문이다. 폭발이 발생했으면 연쇄 횟수를 1증가 한다. 공중에 떠있는 뿌요를 바닥으로 내린다

https://www.acmicpc.net/problem/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 구현을 잘 하는거 말고는 딱히 어려운게 아니었다. 주사위가 움직일 때 어떻게 바뀌는지 잘 체크하는 정도? 문제를 푼 방법은 다음..

https://www.acmicpc.net/problem/5397 5397번: 키로거 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다. 강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 테 www.acmicpc.net 처음에 이렇게 풀어서 틀렸었다 #include #include using namespace std; int main() { listpass..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마 www.acmicpc.net BFS 문제를 풀어보았다. BFS는 큐를 사용해서 탐색을 구현하는 것으로 알고 있었는데 어떤식으로 큐에 넣어야 할 지 감이 잘 안잡혔다. ..

다익스트라에 대한 문제를 우선순위 큐를 사용하여 풀어보았다. 우선순위 큐는 최대 힙의 구조를 가지고 있는데, 최소 비용을 탐색해야하기 때문에, 비용 값을 음수화 하여 힙에 넣었다. 이 코드는 내가 구현한 코드가 아니라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[..

그래프 문제 중 사이클의 개수에 대한 문제이다. 생각보다 어렵지 않게 구현했는데 사이클의 개수를 구하는 부분이 조금 어려웠다. 1 3 5 7의 사이클 개수는 1개인데 방문할 때마다 체크 하면 값이 4가 나오고 그랬다. 특히 재귀에 대한 부분을 해결하는게 관건이었다. 처음엔 void dfs로 했는데 int dfs로 구현하여 return 값을 통해 구해야 할 부분만 구하고 종료시키는 방법을 선택하였다. 입력 int size; cin >> size; int n; for (int i = 1; i > n; graph[i].push_back(n); } 처음에 입력받는 것에 잘못 접근해서 조금 헤맸었다. 입력 값을 정렬하여 새로운 벡터에 넣고 서로 이어줘야 하는지 생각했었다. 하지만 그럴 필요 없이 1,2,3..N번..

덱(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번 정점 사이에 이분그래프가 만들어지지 않으면 절대 이분그..