[백준]

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net #문제 간단 정리 #문제 해결 방법 백트래킹이자 구현 문제라고 볼 수있다. 요지는 빈 공간을 찾아서 dfs를 돌면 되는 것인데. 우선 구현해야 될 것을 정하고 그에따라 체크함수랑 대입함수를 나눠서 차분히 구현하는게 관건이라고 생각한다. #전체 코드 #include #include using namespace std; int board[9][9]; bool check(int row, int c..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net #문제 간단 정리 우선 재귀를 통해서 모든 연산자 조합 계산을 하는게 정석적인 것 같다. 이건 다른블로그들이 그렇게 했고... #문제 해결 방법 우선 생각난게 next_permutation 함수로 모든 경우의 수를 도는 것이기 때문에 이 함수를 사용했다. 하지만 사용 안하고 재귀로 푸는게 더 좋은 풀이 같다. #전체 코드 #include ..

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net #문제 간단 정리 거두절미하고 고민할 필요가 없다 문제만 읽어도 빡구현 문제임을 알 수 가 있다. 가진역량을 동원해서 구현을 할 때 #문제 해결 방법 우선 첫번째로 구조체를 활용해서 구현을 좀 더 쉽게 할 수 있다. 그리고 각 물고기의 조회를 위해서 맵을 만들어주자. 다음생각은 dfs를 사용하는데 맵 복구가 중요하기 때문에 맵을 복사해서 넘겨줄 것. #전체 코드 #include ..

https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net #문제 해결 방법 dfs bfs 상관없을 것 같지만 dfs을 썻다 오랜만에 푼 그래프 문제였다 다른 그래프 문제들 푸는 요령이 있다면 금방 풀 문제 다만 (nx != fromX || ny != fromY) 이 로직에 주의하도록하자 사이클을 감지하기 위해서는 이전 노드로 가는경우를 제외하고 한바퀴 빙 둘러서 방문하는 경우만 감지해야 된다. 때문에 바로 이전노드로는 탐색 방지하는 이런 조건이..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net #문제 간단 정리 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053문제에서 한단계 더 나아간 문제이다 주요 로직은 이 문제를 참고하도록 하자 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분..

https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net #문제 해결 방법 간단하게 생각해보자 일단 시간복잡도를 계산하고 브루트 포스는 안된다는 결론을 내릴 수 있다. 그렇다면 dp를 사용해야 하는데 dp는 큰 문제를 작은문제로 쪼갤 수 있으며 작은 문제를 통해 큰 문제를 풀 수 있어야 한다 즉 dp[i][j] 는 i번째 동전을 사용해서 j 의 값을 만드는 횟수인데 이 횟수는 i번째 동전을 사용하지 않은 문제로부터 답을 구할 수 있다. ..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net #문제 해결 방법 투 포인터를 사용해서 두 값을 선택해서 더한값이 0보다 작다면 start++ 0보다 크다면 end-- 를 해서 0과 가장 같은값을 구할 수 있겠지만.. (n) 나는 일단 이분탐색을 생각했고 두 값을 더한값이 0보다 작다면 low = mid +1 해서 더 큰값을 찾고 0보다 크다면 high = mid -1 해서 더 작은 값을 찾는 방식을 사용했다 ..

https://www.acmicpc.net/problem/13422 13422번: 도둑 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마 www.acmicpc.net #문제 간단 정리 슬라이딩 윈도우를 이용해서 푼다 #문제 해결 방법 우선 슬라이딩 윈도우는 인자가 두개인 for문을 사용하면 쉽게 구현할 수 있다. 여기서 주의해야될 점은 집이 원형으로 연결되어있기 때문에 모듈러 연산으로 원형으로 탐색하게 끔하고 N == M 인 경우에는 슬라이딩 윈도우 크기가 N 과 같기 때문에 존재하는 구간이 하나임에도 불구하고 같은 구간을 여러번 탐색하게 되므로 N == M 인경우는..

https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net #문제 간단 정리 #문제 해결 방법 성원이의 현재 몸무게를 x, 기억하고 있는 몸무게를 y라고 할 때, 주어진 조건은 x^2 - y^2 = G입니다. 이 식은 (x + y)(x - y) = G로 변환할 수 있으며, 우리는 x와 y의 모든 가능한 쌍을 찾아야 합니다. 그러나 주어진 조건에 따라 x와 y는 모두 자연수여야 하며, x > y 조건을 만족해야 합니다 여기서 자연수임을 확인하는 방법은 구한 y^2 값을 ..

https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net #문제 해결 방법 이 문제를 해결하기 위한 로직은 '슬라이딩 윈도우' 기법을 사용합니다. 이 기법은 일정 범위의 데이터를 순차적으로 이동시키면서 연산을 수행하는 방법입니다. 구체적으로, 문제의 해결 로직은 다음과 같습니다: 초기화: maxVisitor: 최대 방문자 수를 저장하는 변수입니다. 이를 0으로 초기화합니다. nowVisitor: 현재 윈도우(즉, 연속된 X일)의 방문자 총합을 저..