본문 바로가기

Problem Solving

BOJ 2605 - 줄 세우기 문제 링크https://www.acmicpc.net/problem/2605 문제 해결 1. 매 번 뽑기가 진행될 때, 중간에 삽입이 될 수 있다. → 자료구조 List를 사용하는 것이 좋다. 주의할 점 || 생각해볼 점 1. iterator사용하는 C++ 문법을 조금 신경쓰면 될 거 같다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기
BOJ 2504 - 괄호의 값 문제 링크https://www.acmicpc.net/problem/2504 문제 해결1. 여는 괄호문자들은 스택(이 문제에선 Deque를이용했다)에 삽입한다. 이 때, 문자와 Boolean값을 Pair의 형태로 유지한다. 그 이유는 여는 괄호문자가 중복이 되었을 때, 곱하는 데에 사용되었는 지 체크하기 위해서다. 2. 만약 닫는 괄호문자 이 나오면, ① 스택이 비어있거나, 제일 최근에 쌓인 문자가 닫는 괄호문자와 쌍을 이루지 않는다 → 잘못된 괄호열② ①번이 아니고, 답에 괄호 값을 곱했다 → 값에 영향을 주지 않고 되돌아간다.③ ①, ②번이 아니다 → 스택의 처음 괄호문자부터 최근에 쌓인 괄호문자까지의 괄호 값을 곱해서 답(ans)에 더 해준다. 3. 모든 괄호 문자열을 체크했는데 스택에 문자가 남아있.. 더보기
BOJ 1644 - 소수의 연속합 문제 링크https://www.acmicpc.net/problem/1644 문제 해결 1. 에라토스테네스의 체를 사용해서 소수들을 구하고 벡터에 삽입한다. 2. 소수들의 연속된 합이 되는 개수를 구한다. 주의할 점 || 생각해볼 점 1. 에라토스테네스의 체는 보통은 sqrt(N)만큼만 확인해서 소수임을 판별하는 데 사용하는 경우가 대부분인데, 이 문제에서는 sqrt(N)을 넘어가는 숫자들의 합으로 N이 될 수 있으므로, N만큼 확인해봐야한다. 2. N의 최대 범위가 4,000,000이고 소수의 개수는 2,831,461개가 된다. for문을 이중으로 사용하나 연속된 두 소수의 합이 N이 되거나 N을 초과하게 되므로 크게 문제될 것이 없다. 참고 - https://ko.wikipedia.org/wiki/%E.. 더보기
BOJ 2526 - 싸이클 문제 링크https://www.acmicpc.net/problem/2668 문제 해결 1. 다음 정점 = (P로 나눈 나머지) * N % P; 2. 배열을 만들어서 numbering한 값을 넣어준다. 3. 만약 배열의 값이 0이 아니라면 사이클이 생긴 것이므로 그 때의 값과 사이클 시작의 값의 차를 출력한다. 주의할 점 || 생각해볼 점 1. P의 범위가 97 밖에 안되므로 사이클이 생기는 정점은 0 ~ 96 까지다. 2. 한 정점에서 나가는 간선은 무조건 하나라는 사실을 인지하면 더욱 수월하게 해결할 수 있다. 참고 - http://vjerksen.tistory.com/30 (사이클을 DFS로 해결) ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기
BOJ 2668 - 숫자고르기 문제 링크https://www.acmicpc.net/problem/2668 문제 해결 1. 간선이 하나인 그래프로 생각하고 문제를 해결할 수 있다. 2. 그래프 내에서 생기는 사이클 중에서 겹치지 않는 큰 사이클들을 모두 구한다. 주의할 점 || 생각해볼 점 1. 오름차순으로 출력하는 것과 정점의 중복을 막기 위해서 Set을 사용했다. 참고 - http://vjerksen.tistory.com/30 (사이클을 DFS로 해결) ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기
BOJ 14585 - 사수빈탕 문제 링크https://www.acmicpc.net/problem/14585 문제 해결 1. (0, 0) 에서부터 x 좌표가 증가하는 방향과 y 좌표가 증가하는 방향으로만 이동한다. → Dynamic Programming으로 해결할 수 있음을 알 수 있는 부분. 주의할 점 || 생각해볼 점 1. M의 값이 1,000,000이고 N의 값이 300이면 M*N = 3억이 될 수 있으므로 (int형 범위를 초과할 수 있으므로) 자료형은 long long을 선택한다. 2. 매 시간마다 1씩 줄어드는 것을 따로 구현할 필요가 없이 가로와 세로의 값을 최초 사탕의 값에서 빼주면 된다. ( a[x][y] - (x+y) ) 3. 처음 문제를 봤을 때, BFS(넓이 우선 탐색)를 이용해서 문제를 해결하려 했다. 그러나 문.. 더보기
BOJ 1072 - 게임 문제 링크https://www.acmicpc.net/problem/1072 문제 해결 1. 처음 주어진 게임 수와 승리 수를 토대로 승률 (winning_rate)을 구한다. 2. 앞으로 치뤄야 할 경기의 수를 Parametric Search로 구한다. 주의할 점 || 생각해볼 점 1. 앞으로 계속 이길 예정이므로 게임을 치루게되면 승률은 99~100% 사이가 된다. 이미 승률이 99% 이상이면 더 이상 오를 승률이 없게된다. 이 때 문제에서 요구한대로 ' -1 ' 을 출력한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기
BOJ 12758 - 토쟁이의 등굣길 문제 링크https://www.acmicpc.net/problem/12785 문제 해결 1. DP[i][j] = (1, 1)에서 (i, j)까지 가는 경우의 수 2. DP[i][j] = DP[i-1][j] + DP[i][j-1] 3. a : (1, 1)부터 토스트 집의 좌표 (x, y)까지의 경우의 수 b : (x, y)부터 학교까지의 경우의 수(M, N)까지의 경우의 수 → (x, y)를 (1, 1)로, (M, N)을 (M-x+1, N-y+1)로 생각하자. a*b가 답이된다. 주의할 점 || 생각해볼 점 1. 1,000,007로 계산할 때마다 나누어 줘야한다. 2. a와 b 모두 1,000,007이 넘지 않는다고 해도 곱하는 과정에서 넘어갈 수 있기에 long long 자료형을 사용한다. 참고 - ※ .. 더보기
BOJ 5557 - 1학년 문제 링크https://www.acmicpc.net/problem/5557 문제 해결 1. DP[i][j] = 첫 번째부터 i 번째까지의 합 또는 차가 j 인 경우의 개수 주의할 점 || 생각해볼 점 1. 처음부터 i 번까지의 합이 0 이상 20 이하임을 인지한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기
BOJ 1695 - 팰린드롬 만들기 문제 링크https://www.acmicpc.net/problem/1695 문제 해결 1. dp[i][j] = 인덱스 i 부터 j 까지의 끼워넣는 수의 최소값. 주의할 점 || 생각해볼 점 1. i가 j를 넘어갈 수 있음을 고려해줘야한다. 참고 ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기

티스토리툴바