링크: https://www.acmicpc.net/problem/10472문제각 칸이 색칠된 상태를 0/1로 보면, 3x3 크기의 보드는 크기가 9인 상태공간을 가진다.따라서 나타날 수 있는 보드의 상태의 수는 \(2^{9}\) = 512가지이다. 최초 보드의 상태에서 각 칸을 눌러보며 매번 9번의 상태 분기가 일어나는 BFS 탐색으로 해결 가능하다. 어떤 상태를 이미 확인했는 지에 사용되는 visit 배열은 취향에 따라 여러 형태가 가능할 것이다. 나는 000 000 000의 크기 9짜리 상태 공간을 2진법으로 변환하여 int 변수로 표현하였다. 그래서 visit[bit]로 했는데, key-value를 쓰면 string형으로 "000111000"처럼 저장할 수도 있다.어찌되었건 중요한건 중복 확인을 할..

링크: https://www.acmicpc.net/problem/1939 문제어떤 정점 S에서 다른 정점 E까지 가는 경로에서 등장하는 간선의 가중치의 최대값을 구하는 문제입니다. 최단 경로를 살피는 것이 아니라, 최대한 무거운 것을 옮기기 위한 다리만 선정한 경로를 만들어야하므로 최소 스패닝 트리의 반대인 최대 스패닝 트리가 떠오릅니다. 일반적으로 크루스칼 알고리즘은 최소 스패닝 트리를 위해 사용되지만, 이 경우에는 반대로 최대 스패닝 트리를 위해 사용할 수 있을 것 같습니다. (음수 가중치도 없으니 가능해보입니다.) 연결되지 않은 간선 중 가중치가 가장 큰 간선을 선택하면서 스패닝 트리를 만들어가면, 어떤 정점 S와 다른 정점 E이 같은 "연결된 집합"에 속하는 그 순간에 우리가 원하는 경로가 완성됩..

링크: https://www.acmicpc.net/problem/10799문제스택 문제로 유명한 한국정보올림피아드(KOI) 2015 지역본선 문제, 쇠막대기입니다. 사실 스택 없이 풀리는 문제지만요.문제를 읽어보면 쇠막대기의 왼쪽 끝은 여는 괄호, 오른쪽 끝은 닫힌 괄호로 표시하여, 레이저 "()"에 의해 잘려진 막대기 조각이 총 몇 개인지 구하는 문제입니다.잘못된 모양은 없다고 하니 스택으로 별다른 검증은 안해도 됩니다.풀이먼저 풀이의 중간 단계를 생각해봅시다. 문자열 "((()()))"은 쇠막대기가 2층으로 쌓인 형태일 것이고, 위 사진처럼 레이저(노란색 점선)에 의해 잘려나갈겁니다. 여기서 첫 번째 레이저에 집중해봅시다.첫 번째 레이저가 발사된다면 1층에서 2조각, 2층에서 2조각으로 나뉘어서 총 ..

링크: https://www.acmicpc.net/problem/16235문제시뮬레이션여름과 겨울은 양분을 더하는 것밖에 영향을 안 미치기 때문에 같이 처리할 수 있다.링크드리스트로 정렬된 상태 유지 + 나무 개수를 압축하여 표현나무의 개수를 압축해도 수명이 끝난 나무를 확인하는 것 때문에 시간복잡도는 거의 변화가 없어서 고민이 많았는 데, 항상 크기가 1인 나무들이 생기므로 링크드리스트의 앞과 뒤만 잘 관리하면 된다는 것을 Nada님의 코드를 보고 깨달았다.코드

2018년 제13회 전북대학교 프로그래밍 경진대회 포스터 대회 진행 시 나눠준 사은품(스티커) 실제 사진 http://acm.jbnu.ac.kr/

링크: https://www.acmicpc.net/problem/11058출력 결과에 영향을 미치는 연산이 A를 그냥 누르는 거랑(+1), Ctrl-V (+복사했던 크기) 인데 클립보드에 복사해놓은 크기때문에 재귀로 짜는데 애를 먹었다. 복사한 크기만큼 늘어나기 때문에, Ctrl-V 를 하기 위해서는 이전에 Ctrl-A, Ctrl-C 가 꼭 필요하다. 문제에 적힌 연산을 순서대로 A, S, C, V 라고 한다면 \(N=6\)인 경우는 아래와 같이 가능하다. AAAAAAAAASCVAASCVVASCVVV 이 정도가 의미있는 타이핑인거같다. 타이핑을 \(n\)번한 것을 \(f(n)\)이라 하자. 그럼 위 4줄은 각각 \(f(5)+1\), \(f(3)∗2\), \(f(2)∗3\), \(f(1)∗4\) 이다. $..

링크: https://www.acmicpc.net/problem/1509문제\(dp[i]\) = \(i\)번째 위치에서 가능한 팰린드롬 분할의 최소 개수\(isPaline[i][j]\) = \(i~j\) 가 팰린드롬인지 여부 예제에도 끼워져있지만 AABDBADD 와 같은 경우의 처리때문에 여러 경우를 탐색해야한다. 이것을 분할하는 경우는 아래와 같다.A - A - B - D - B - A - D - D A - A - B - D - B - A - DD A - A - BDB - A - D - D A - A - BDB - A - DD A - ABDBA - D - D A - ABDBA - DD AA - B - D - B - A - D - D AA - B - D - B - A - DD AA - BDB - A - ..

링크: https://www.acmicpc.net/problem/3079코드