본문 바로가기

Algorithm

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 ..
BaekJoon 7568 덩치 2018. 12. 27. Link : https://www.acmicpc.net/problem/7568 소스 결과 : 1984 KB / 0 ms 출처 : BackJoon / 한국정보올림피아드시, 도지역본선 지역본선 2013 초등부 2번 소스코드 #include using namespace std; int weight[50]; int height[50]; int mRank[50]; int main() { int n; cin >> n; for (int i = 0; i > weight[i] >> height[i]; for (int i = 0; i weight[i] && height..
BaekJoon 2583 영역구하기 2018. 12. 26. Link : https://www.acmicpc.net/problem/2583 소스 결과 : 2068 KB / 0 ms 출처 : BackJoon, 한국정보올림피아드시, 도 지역본선 지역본선 2006 고등부 2번 프로그래머스에서 카카오 문제로 나왔던 문제랑 비슷한문제인데 정작 풀어보지 못했던게 아쉬워서 풀어본 문제.. 문제로는 어피치랑 무지가 나왔던거 같은데 그 때에는 BFS를 잘 몰라서 못 풀었던 문제로 배우고 난 뒤에 다시 한번 풀 기회가 없을까 하던 도중에 발견해서 풀어본 문제 영상처리에서 Labeling과 유사하게 풀어보았다. 풀고나니 재밌다. 소스코드 #include #include using namespace std; int paper[100][100]; int checkMap[100][100]..
BaekJoon 11403 경로찾기 2018. 12. 26. Link : https://www.acmicpc.net/problem/11403 소스 결과 : 2064 KB / 12ms 출처 : BackJoon DFS나 BFS를 사용하는 기초적인 문제라는 느낌이 들었다. 지금 BFS를 공부하는 중이기에 BFS로 문제를 풀었는데 cycle로 처리해서 문제를 해결하는 건가 하는 고민을 처음에 좀 했었다. 결론은 cycle 처리는 bool 배열 하나를 넣는것으로 처리를 마무리 했다. 정답은 맞았지만 메모리 2064KB에 12ms 처리 속도 아마 동적배열을 사용하지않고 100개를 미리 만들어두어서 메모리를 좀 많이 잡아먹은 느낌이 있다. 소스코드 #include #include using namespace std; int map[100][100]; int moveMap[10..

티스토리툴바