선택은 나의 것

문제 BOJ 9251 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 접근 DP를 통해 문제를 해결하였다. 입력받은 두 문자열 s1, s2에서 각자 한 문자씩 가리키는 포인터 p1, p2를 통해 s1[p1]과 s2[p2]가 같다면 LCS의 길이를 늘여주기 위해 1을 더하고, 같지 않다면 p1을 한 칸 앞으로 전진하거나(rec(p1 + 1, p2)), p2를 한 칸 앞으로 전진시킨 경우(rec(p1..

문제 BOJ 12865 : https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 접근 이 문제는 전형적인 냅색(Knapsack)문제이다. DP를 구현하는 방법에는 재귀 호출을 사용하여 구현하는 탑다운(top-down) 방식과 반복문을 사용하여 구현하는 바텀업(bottom-up) 방식이 있다. 탑다운은 말 그대로 큰 문제부터 점차 작은 문제로(재귀를 통해) 쪼개어 가기 때문에 붙여진 이..

문제 BOJ 2206 : https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 접근 BFS를 이용하여 문제를 풀었다. 이때 문제의 조건을 보면 진행하는 과정에서 벽을 단 한 번 부수고 진행할 수 있다는 조건 때문에 방문처리를 어떻게 해야 할지 막막한 분들이 있을 것이다. 이를 처리하기 위해 방문 처리를 위한 배열 visit를 기존의 2차원이 아닌 3차원으로 만들어 임의의 좌표 (X, Y)까지 오는 동안 벽을 부수온 최단 거리..

문제 BOJ 18352 : https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 접근 BFS를 이용해 풀 수 있는 간단한 문제이다. queue에 값을 넣을 때마다 깊이를 체크해주며 깊이가 K라면 정답을 출력할 배열에 넣어주면 된다. 즉, 기존의 BFS를 구현하는 코드에서 if문 하나만 추가해주면 되는 것이다. 나는 이 과정에서 자동으로 오름차순 정렬을 위해 set을 사용하였으나..

이 문서는 마크다운으로 작성되었으며 github 스타일에 최적화되어있습니다. github 링크 를 통한 열람을 권장합니다. Pointer(포인터) & Reference(레퍼런스:참조자) Pointer와 Reference는 C++이 다른 언어와 큰 차이점을 가지는 지점이다. 바로 Pointer와 Reference를 이용해 메모리를 직접 핸들링 할 수 있기 때문이다. Pointer의 경우 C에도 있는 개념이지만 Reference는 C++에서 등장한 개념이다. 둘은 용도가 비슷해 보이는 데 어떤 차이가 있으며 Reference가 왜 등장하게 됐는지 알아보자. Pointer(포인터) 메모리의 주소값을 저장하는 변수이다. // 문법 예제 int a = 10; // 변수 선언 int *ptr = &a; // 포인터..

문제 BOJ 16973 : https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 접근 문제 접근법을 빠르게 생각해 내서 수월할 거라 예상했지만 의외로 많이 틀렸던 문제이다. 문제 접근법은 간단하다. BFS를 통해 시작 좌표 (Sr, Sc)부터 도착 좌표 (Fr, Fc)에 도착할 때까지 while문을 도는 것이다. 여기까지 생각해 내기는 쉽지만 다들 작은 실수로 시간 초과, 메모리 초과, 런타임 에러 등을 겪는다. 왜 이런 오..