url : https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 스택을 이용한 꽤 유명한 문제이다. 연산자 우선순위를 고려하여 적절하게 출력한다. 연산자 우선순위 () > *,/ > +, - *, / : 우선순위 가장 높음 (숫자 2) -- 숫자가 클수록 우선순위 크다고 가정 +, - : 우선순위 낮음 (숫자 1) 문자의 경우 등장시마다 문자열에 저장하고, 연산자의 위치와 순서를 로직에서 결정한다. ()의 경우 ) 부분에서 ( 앞 부분까지 먼저 ..
url : https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 순열 서로 다른 N개의 원소를 일렬로 나열 순열 그래프 순열을 그래프로 표현한 것 - 각 노드는 단 하나의 다른 노드로만 연결된다 + 단일 방향 - 모든 노드는 하나 이상의 사이클을 형성한다. 틀린 이유 맞췄다고 생각했는데 자꾸 틀렸다.. 4%대에서 틀렸는데, 이렇게 초반에 틀릴 경우 출력 형식을 확인해보아야한다...
url : https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름 leaf노드 ~ leaf노드까지의 거리 구하기 1. leaf 노드 구하기 (dfs) 2. leaf 노드에서 출발하여 dfs 최대 거리 구하기(leaf 노드 ~ leaf 노드) 코드 #include using namespace std; int v, n, a, b, farthestNode, maxDistance; vector tree[100004]; int vi..
url : https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 완전탐색 문제인 줄 알았는데, dp문제이다. 완전 탐색으로 풀 경우 O(3^N) 시간복잡도이고, 좀 더 단순한 방법을 생각해야 통과할 수 있다. 구하는 것은 최소 비용이므로 부분 문제의 해가 전체 문제의 해가 될 수 있다. 즉, dp로 풀 수 있다. dp의 경우 시간복잡도는 O(N)이다. DP 생각 타이밍 완전탐색의 시간복잡도가 클 경우 / 1번부터 N번까지 차례대..
오늘은 매주 알고리즘 스터디에서 진행하는 이벤트 날인데, 모여서 3문제를 3시간 안에 푸는 날이다. 문제 난이도는 스터디원을 고려하여 실버 3~골드 2, 프로그래머스 level 1,2로 출제했다. 쉬운 문제, 중간문제, 좀 더 어려운 문제 순으로 문제를 냈다.(내가 스터디 장이라 문제를 출제했다.) 결과적으로 어려운 문제(3번 문제)는 풀지 못했는데, 카카오 문제였다!! ㅠㅠ 내일 문제를 다시 한번 풀 예정이다. 1번 문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/147355 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받..
url : https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 오랜만에 쉬운 DFS 유형 문제를 풀었다. dfs가 오랜만이다보니 헤맸는데, 역시 계속해서 다양한 문제 유형을 접하는 것이 중요한 것 같다. 코드 #include using namespace std; int n, m, tmp; int visited[10], num[10]; vector arr; void dfs(int here, int cnt){ if (cnt==m){ for(i..
Happy New Year! url : https://school.programmers.co.kr/learn/courses/30/lessons/181187 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 수학 문제는 로직 구현시 기존 존재하는 공식이나 정리가 있는지 확인하고, 이를 사용하는 것이 중요하다. 원 공식 : x2+y2=r2 을 이용하여 x 지점에 대해 두 원 사이에 속하는 y 점 개수를 구하면 된다. 원이므로 대칭을 이용하여, 4사분면의 한 부분만 구하고, 구한 개수 *4 를 하여 답을 구한다. 로직 1) x 위치를 기준으로 1~r2 까지 반복문..
url : https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 내일 좀 더 자세하게 정리할 예정... 수학적 지식 +1 코드 #include using namespace std; const int MOD = 1000000007; // 빠른 거듭제곱 함수 long long pow(long long base, int exponent) { long long result = 1; while (exponent > 0) { if (exponent % 2 == 1) result = ..
