Algorithm/백준79 [백준][C++] 20040번: 사이클 게임 <230> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 대표적인 Union Find 문제인것 같다. Union Find 알고리즘이 궁금하다면 다음 글을 읽어보길 권장한다. https://blogshine.tistory.com/103 Algorithm/백준 2022. 6. 23. [백준][C++] 16724번: 피리 부는 사나이 <229> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 이 문제를 보고 생각한 방식은 cycle을 찾는 방식이였다. 우리 문제의 예시 를 생각해보자! 3 4 DLLL DRLU RRRU 우선 맨 왼쪽 위 부터 탐색을 시작한다고 해보자.. Algorithm/백준 2022. 6. 22. [백준][C++] 9328번: 열쇠 <228> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 이 문제를 가장 쉽게 해결하기 위해서는 지도의 태두리를 이동할수 있는 길('.') 로 만들어야 한다. 다음 그림을 살펴보자. 위 그림과 같이 초록색 부분이 원래의 MAP이고, 회색 영역이 우리가 추가해준 부분이다. 이는 외부.. Algorithm/백준 2022. 6. 10. [백준][C++] 1389번: 케빈 베이컨의 6단계 법칙 <227> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 일단 모든 구성원들 자신의 케빈수를 다 구해야 한다는 점에서 플로이드-와샬 방식을 선택하였다. 크게 어려운 부분은 없는데, 생각 못한 부분이 있어 이를 적어본다. if (MAP[i][k] != 0 && MAP[k][j] != 0) { .. Algorithm/백준 2022. 6. 8. [백준][C++] 2098번: 외판원 순회 <226> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 DP[k][visited] : k: 현재 도시, visited: 방문했던 도시들을 비트로 표현 이때 핵심은 방문했던 도시들을 bit 로 저장하는 것 이다. 예를 들어 00001 이라면 0번 도시를 방문, 00011 이라면 0번, 1번 도시를 방문.. Algorithm/백준 2022. 6. 3. [백준][C++] 5525번: IOIOI <225> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 'I' 가 나올때 마다 매번 Pn이 포함됬는지 확인하기는 시간안에 해결이 불가능하다. while문을 돌면서 'OI' 를 하나의 단위로 보고, 단위로 확인을 한다. while(str[i+1] == 'O' && str[.. Algorithm/백준 2022. 6. 2. [백준][C++] 11286번: 절대값 힙 <224> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 문제 자체는 엄청 쉽다. 그냥 Queue 2개 만들어서 각각 minus, plus 용으로 사용하면 된다. 다만 주의할점이... 아무 생각없이 그냥 queue를 사용하면서 삽질하면 안된다. 우선순위큐를 사용해서 minHeap을 만들어줘야 한다. priority_qu.. Algorithm/백준 2022. 5. 30. [백준][C++] 5430번: AC <223> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 각 케이스마다 별도로 bool값을 담아두는 isReverse 와 isError 변수를 만드는 것이 핵심이다. 1) isReverse 의 사용처 이 문제를 읽자마자 든 생각은, "이걸 직접 진짜 배열을 뒤집으면 시간안에 못풀겠는데?" 였다. 당연히 직접 뒤집을 필요도 없는 문제이다. isReverse 에 true가 담겨있으면 -> 뒤집.. Algorithm/백준 2022. 5. 26. [백준][C++] 16928번: 뱀과 사다리 게임 <222> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x HTML 삽입 미리보기할 수 없는 소스 음 일단 횟수의 최소값을 구해야 하니, BFS 방식을 가장 먼저 떠올렸다. input을 nextNumber[101]이라는 배열로 받아야 겠다 생각했다. nextNumber[31] = 42 는 31번 칸에 도착시 42번 칸으로 사다리를 타고.. Algorithm/백준 2022. 5. 23. [백준][C++] 16946번: 벽 부수고 이동하기 4 <221> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제를 1이 나올때마 전체 이동 가능한 칸을 직접 확이하면 시간안에 해결할수가 없다. 총 방문 가능한 칸이 1000*1000 칸이 있는데, 각 칸마다 확인하려면 1000*1000(모든 칸)*1000*1000(이동 가능한 최대 칸) 만큼 돌아야 한다. 시간안에.. Algorithm/백준 2022. 5. 19. [백준][C++] 3055번: 탈출 <220> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 기존의 BFS 알고리즘을 적용하는 문제들과는 조금 다른 점이 있는 문제이다. 이 문제는 두더지가 이동하는 동시에 물도 함께 차오르기 때문에 Queue를 2개 사용해야하는 문제였습니다. 물이 차오를 예정인 위치로는 두더지가 움직일 수 없기 때문에 1) 먼저 물이 차오르는 과정을 진행한 다음 2) .. Algorithm/백준 2022. 5. 13. [백준][C++] 15684번: 사다리 조작 <219> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 사다리 좌표계를 다음과 같이 생각하였다. ladder[i][j] == true 는 i행 j열에 가로 사다리가 배치되어있다는 의미이다. 우선 isValid라는 메서드를 다음과 같이 만들었다. bool isValid(){ for(int col = 1; col Algorithm/백준 2022. 5. 12. 이전 1 2 3 4 5 6 7 다음
