본문 바로가기

전체 글548

백준 16724 c++ "피리 부는 사나이" -PlusUltraCode- https://www.acmicpc.net/problem/16724[필자 사고]이 문제는 방문처리 dfs를 사이클 판정하는 문제다.dfs로 사이클을 판정했따ㄴ라는 신호를 어떻게 알 수 있을까. visited를 0 ,1 ,2 형태로 놓는다.0은 방문하지 않은 상태,1은 방문한 상태만약 탐색 도중 1을 발견하게 되면 방문한 상태이므로 사이클에 해당한다.그리고 해당 dfs마지막에 visited =2 를 넣게 되어 탐색이 완료됨을 보인다. 이러한 형식으로 코드를 만들면 문제를 해결할 수 있다. 아래는 자세한 코드 해설이다. [코드 해설]1. 문제의 핵심 개념지도는 N×M 격자로 구성되어 있으며, 각 칸은 네 가지 방향 중 하나(U, D, L, R)를 가진다.즉, 각 칸은 정확히 한 칸으로 이동하는 단방향 경로를.. 2025. 10. 15.
백준 2482 c++ "색상환" -PlusUltraCode- https://www.acmicpc.net/problem/2482[필자 사고]DP문제다. 일단 머릿속에 있는 내용으로 글을 써보자.원형태다. 이럴 경우 일단은 선형으로 생각을해보자. 문제에서 n이 주어지면 n-1개는 선형이라고 생각하고 DP문제를 풀면 된다.해보자.DP[I][K]라고 했을 경우 I개의 색이 있고 그중 K개를 택하는 경우의 수를 의미한다.즉 이 DP는 마지막 새로운 색깔을 택하냐 안택하냐 라고 생각하면 쉽게 점화식을 도출 할 수있다.만약 마지막 색깔을 택하게 될 경우 바로 이전꺼는 택하면 안된다. 그래서 DP[I-2][K-1] 자기꺼 현재와 이전꺼를 밴 I-2개의 색중에서 k-1개를 뽑으면 된다.다음으로 마지막 색깔을 택하지 못하는 경우는 자기꺼 I-1개와 그중 k개를 뽑으면 된다. 초기값.. 2025. 10. 15.
백준 17386 c++ "선분 교차 1" -PlusUltraCode- https://www.acmicpc.net/problem/17386 [필자 사고]CCW 선분교차 판정 문제다.규칙성이 있다.세 점을 기준으로 CCW 함수를 만든다.a.x*b.y + (b.x*c.y) +(c.x*a.x) -((a.x*c.y) + (b.x*a.y) +(c.x*b.y));위와 같은 공식을 이용하여 선분 ab를 기준으로 c 와 d 선분 cd를 기준으로 a 와 b 의 각 곲이 음수면은 선분은 교차된다 판정한다. 아래는 자세한 코드 해설이다.[코드 해설]struct Point2차원 좌표를 표현하는 구조체이다.x, y 멤버 변수를 가지고 있으며,read() 메서드는 표준 입력으로부터 한 점의 좌표를 입력받는다.즉, 점 하나를 쉽게 다루기 위한 기본 단위 역할을 한다.int ccw(Point a, P.. 2025. 10. 14.
백준 17299 c++ "오등큰수" -PlusUltraCode- https://www.acmicpc.net/problem/17299[필자 사고]자신의 위치에서 오른쪽에 어떠한 숫자 관련된 문제.. 스택을 떠올려보자. 자신의 현재 idx를 스택에 저장한다. 다음 인덱스로 넘어갔을 때 조건에서 주어진 값에 충족이 되면 stack 을 꺼내고 result 값을 저장한다.그렇지 않으면 넘어간다. 이런 while()문은 여러개의 idx조건에 해당될 수 있다. 아래는 자세한 코드 해설이다.[코드 해설]1. 프로그램 개요이 코드는 백준 17299번 오등큰수(Next Greater Frequency) 문제를 해결하기 위한 프로그램이다.주어진 수열에서 각 원소 Ai에 대해, 오른쪽에 있으면서 더 자주 등장하는 수 중 가장 가까운 값을 찾는다.그러한 수가 존재하지 않으면 결과는 -1로 .. 2025. 10. 12.

티스토리툴바