목록언어
Step-by-Step
https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 3번의 시도 끝에 성공 N+1까지 경우의 수를 계속 붙여가면서 진행했는데, 내가 생각해낸 건 3가지 경우다 O : 출석 1번 AO : 연속된 결석 1번 AAO : 연속된 결석 2번 그리고 마지막이 A로 끝나는 경우를 대비하여 N+1까지 찾은 후, 마지막 O를 빼버렸다. 또 지각은 N+1까지 찾은 후 O를 빼고, O들 중 하나를 L로 바꾸는 방식으로 함 1차시도 : BFS → 메모리 초과 (C++로도 해봤는데 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/1c7hl/btrTKcGBPKz/CGzBjb8hNKEto3STMiMIUk/img.png)
https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net DP 없이 풀다가 시간 초과..ㅋㅋ ㅠㅠ 일단 사각형이 되기 위해서는 사각형 내부(테두리 포함) 모두 1이어야 한다. DP를 이용하면, 해당 좌표( i, j )의 ↑ ↖ ← 세 방향의 값의 최소값에 1을 더해주면 된다. 만약 세 방향 중 하나라도 0이 있으면 값이 1이 되고, 1은 칸 1개짜리 정사각형이다. ex) 세 방향의 값이 각각 2, 4, 5 인 경우 dp값은 3이 된다. 초록색 부분은 신경 안 써도 된다. 4랑 5 앞칸이 0이었다면 4랑 5칸에 1이 있었을 ..
https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 어렵지 않은 골드문제 결론부터 말하면 가야하는 여행 장소(맨 마지막줄 입력)들이 다 연결되어 있는지만 확인하면 된다. 풀이는 마지막 줄 첫번째 원소를 출발점으로 잡고 BFS 탐색을 통해 전부 연결되어있는지 확인했다. 방문한 정점은 재 방문하지 않고, 방문해야 하는 정점은 hashSet에 담아서 방문할때마다 지웠다. [풀이] package BOJ_1000; import java.io.Buffered..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/uDhFV/btrSCHz5265/6Yd1uQRE80qmcXOC0rFf2K/img.png)
https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 풀면서 이거 골드문제 같은데?! 했는데 실버였다. (어려운만큼 내 실력이 부족하다는거겠지) 사실 풀고 나서는 실버라는게 수긍이 갔던 문제..! 모든 DP문제가 그렇듯이 점화식만 깨우치면 쉽다..! 문제를 읽자마자 DP 문제라는 것을 알 수 있는데, 저번에 풀었던 동전 문제와 비슷했다. ※ 백준2293 https://smile-devel..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bvq9dG/btrSnDMeDbe/WkIPsHh9Q3dU8eKXbZKsd0/img.png)
JAVA는 Class를 이용하여 객체를 만드는데, C++은 Class가 있음에도 불구하고 다들 Struct를 사용하는 걸까 일단 구조는 비슷하다 (거의 똑같음) 중요한 차이는 접근제어자에 있다. 접근제어자 private : 동일 클래스 내에서만 접근 가능 protected : 해당 클래스와 상속받은 파생 클래스에서만 접근 가능 public : 어디서든 접근 가능 ※ 참조 : JAVA는 package 개념이 있지만, C/C++은 없다. Class vs Struct Class : private이 default Struct : public이 default 예를 들어보자 클래스 객체를 생성하고, 메소드를 이용하여 값을 가져오는 코드이다. private 멤버라 접근할 수 없다고 나온다. 해결 이런식으로 publi..
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net DP 느낌이 나는 문제! 근데 조건은 벽 문을 1번만 부술 수 있다는 것이다. N*M 격자에서 DP 값을 저장하는데, 매 위치마다 벽을 부수고 온 경우 1와 벽을 부수지 않고 온 경우 0 별로 각각 최소값을 구해주었다. DP[행 index] [열 index]에 벽 부쉈는지에 따라 다르게 체크하기 위해 3차원으로 하나 더 넣어주었다. ※ 크기 선언 : DP[N][M][2] ..
https://www.acmicpc.net/problem/1522 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net 투포인터 사용하는 문제이다. 처음에는 연속된 b값이 가장 많은 것을 기준으로 옆에 붙이려고 했는데, bababa 이런 경우는 맨 앞의 b를 두번째 b와 세번째 b사이에 넣는 작업 한 번만 해주면 연속적이게 된다. ※ 방법 a의 개수를 구한 후, 연속적인 a 범위 내에서 내부에 있는 b의 개수가 최소인 경우를 구하면 된다. 0~aCnt / 1~(aCnt+1) / .. → 이런식으로 투 포인터 사용 코드..
Java만 쓰다가 C / C++ 중에 하나를 선택해야 하는 순간이 왔을 때, C++를 선택한 건 정말 잘 한 결정이었다. 함수 기반 C언어와 달리 객체 지향인 C++은 Java를 잘 알고 있으면 금방 이해하고 다룰 수 있는 것 같다. ※ 다만 JAVA는 대부분 Pascal 표기법을 사용하는데, C++은 대부분 스네이크 표기법이다. ex) JAVA → PriorityQueue // C++ → priority_queue Struct struct Person { int h, w, idx; Person(int height, int weight, int index) : h(height), w(weight), idx(index) {} bool operatorh w < p.w) return..