본문 바로가기

분류 전체보기

BaekJoon 1987 알파벳 2019. 1. 1. Link : https://www.acmicpc.net/problem/1987 소스 결과 : 1984KB 488ms 출처 : BackJoon, Croatian Highschool Competitions in Infomatics 2002 Regional Competition Jonior 설명 DFS 문제 조건 1. 시작하는 칸도 포함 : 즉 최대값은 1부터 시작 2. 칸을 기준으로 중복 체크를 하는 것이 아닌 현재 칸의 알파벳을 밟은 적이 있는지를 검사 사용 입력 케이스 2 20 ABCDEFGHIJKLMNOPQRST BCDEFGHIJKLMNOPQRSTU 21 3 3 ABC DEF GHI 9 4 4 AAAA BAAA CAAA DEFG 7 2 2 AA AA 1 20 2 AB BC CD DE EF FG GH H..
BaekJoon 1205 등수 구하기 2018. 12. 31. Link : https://www.acmicpc.net/problem/1205 소스 결과 : 1988KB / 0 ms 출처 : BackJoon 설명 Sorting 문제 구경중에 정답률이 생각보다 낮아서 풀어본 문제 알고리즘 1. 크기 n 의 벡터 생성 2. 내림차순 정렬 3. 기준 점수보다 큰 점수와 같은 점수 개수를 저장 4. 큰 점수 + 같은 점수 의 수가 랭킹 저장 수와 비교 5. 비교 값이 목표 커트라인보다 작으면 큰 점수 +1 아니면 -1 소스코드 #include #include #include using namespace std; bool comp(int x, int y) { return x > y; } int main() { int n; int songScore; int cut; cin >>..
BaekJoon 1427 소트인사이드 2018. 12. 31. Link : https://www.acmicpc.net/problem/1427 소스 결과 : 2048 KB / 0 ms 출처 : BackJoon 설명 시간제한 2초 최대 배열 크기 10 Bubble Sort로 구현해도 금방 푸는 문제 문제 찾던중 눈에 걸려서 풀어본 문제 알고리즘 1. log를 이용하여 자리 수 추출 2. 각 자리 값을 digits 배열에 저장 3. Selection Sort를 이용하여 정렬 4. 출력 소스코드 #include #include using namespace std; int main() { int n; cin >> n; int size = log10(n) + 1; int digits[10]; for (int i = 0; i < size; i++) { digits[size - ..
BaekJoon 1325 효율적인 해킹 2018. 12. 31. Link : https://www.acmicpc.net/problem/1325 소스 결과 : 3444KB / 3188ms 출처 : BackJoon 설명 참 간단해 보이는데 생각보다 생각을 오래 한 문제 조건이 몇가지 존재 했다. 첫번째로는 N이 10000이기에 인접행렬을 사용하게 되면 10000 * 10000 * 4 byte를 사용. 메모리 초과가 나온다. 두번째로는 A가 B를 신뢰한다에서 단방향 그래프라는 것인데, B 가 A의 부모 정도로 생각하면 간단했다. 세번째로는 M이 100,000 이기에 Queue의 크기를 10만으로 잡은 원형 큐를 하나 사용했다. 첫번째 조건은 가변배열을 사용 해야만 하는 조건이었기에 평소와는 다르게 vector를 사용해서 해결했다. 알고리즘 1. A B를 입력받은 동시에 부..
BaekJoon 2997 네 번째 수 2018. 12. 31. Link : https://www.acmicpc.net/problem/2997 소스 결과 : 1984 KB / 0ms 출처 : BackJoon, Croatian Open Competition in Infomatics COCI 2007/2008 Contest #33 설명 풀어도 이해가 안가는 문제.. 예제 말 뜻을 이해하는데 조금 오래 걸렸다 4 6 8 이면 정답이 10 이라는데 정답이 8이 될 수도 있다고 생각한다.... 4개중 3개만 알려 줬다 했는데 나머지 하나가 2 4 6 8 일 수도 있지 않나 하는 생각이 든다. 소스코드 #include using namespace std; int main() { int num[3]; for (int i = 0; i > num[i]; f..
BaekJoon 9663 N-Queens 2018. 12. 31. Link : https://www.acmicpc.net/problem/9663 소스 결과 : 1988 KB / 4588 ms 성공 출처 : BackJoon 설명 백준 Back Tracking 기초 문제 Back Tracking 대표 문제라고해서 풀어봤는데 이틀이나 걸렸다. 알고리즘을 2번 고쳤는데 처음에는 15 by 15 배열을 만들어 기록 하는 방식으로 제작했다가 타임아웃의 늪에 빠졌다. 같은 열을 제외하는 부분을 없애고 대각선 계산도 개선 해봤지만 결과는 똑같이 타임아웃 성공한 알고리즘은 2차원 행렬을 만드는게 아닌 현재 저장된 지점들을 스택처럼 저장하는 15 by 2 배열을 만들어 저장하고 현재 저장된 배열들을 재 탐색 하면서 사용 가능한 곳인지 확인하는 방법 구글링을 해보고 느낀거지만 훨씬 빠른 ..
BaekJoon 2644 촌수계산 2018. 12. 28. Link : https://www.acmicpc.net/problem/2644 소스 결과 : 2028 KB / 0 ms 출처 : BackJoon, 한국정보 올림피아드 KOI 1999 중등부 1번 설명 헛다리를 너무 많이 짚은 문제.. 이번에는 queue를 추가하지 않고 간이 형태로 제작해서 사용 처음에 부모가 누구인지만 아는 방법으로 해결하려고 했으나 자식으로 내려가야 되는 경우가 존재해서 2차원 행렬로 제작하는 방향으로 변환 굳이 2차원 행렬이 아니라 희소행렬로도 가능할 것 같다. 소스코드 #include using namespace std; int relation[100][100]; int check[100]; int queue[100]; int pos = -1; void push(int val) {..
BaekJoon 1065 한수 2018. 12. 28. Link : https://www.acmicpc.net/problem/1065 소스 결과 : 1984 KB / 0 ms 출처 : BackJoon 설명 생각보다 쉬운 문제 일단 범위가 자연수 한정에 1000 이하 이지만 실질적으로 1 ~ 99 까지는 무조건 등차수열이고 1000은 등차수열이 아니니 100 ~ 999 까지만 계산하면 되는 문제였다. 소스코드 #include using namespace std; int main() { int n; int count = 0; cin >> n; if (n == 1000) // 1000 is not arithmetic sequence n = 999; if (n < 100) // under 100 is arithmetic sequence count = n; else ..

티스토리툴바