본문 바로가기

알고리즘15

BOJ 16987) 계란으로 계란치기 (C++) 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 백트래킹을 이용해 풀었다. 1. 가장 왼쪽의 계란을 든다. 2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다. 3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정.. 2021. 9. 24.

BOJ 1941) 소문난 칠공주 (C++) 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 처음에는 각 점에 대해 DFS나 BFS로 탐색을 시도하려고 했는데 그럴 경우 다음과 같은 경우가 탐색이 되지 않았다. O O O O O O O O O O O O O O 어떻게 해야 하나 머리를 싸매다가 https://transferhwang.tistory.com/294 님의 블로그에서 도움을 얻었다. 1. 7명의 학생을 뽑는다. 2. 해당 학생들 중 이다솜파가 4명 이상인지, 모든 학생이 인접해 있는지를 검사한다. #include using namespace std.. 2021. 9. 23.

[프로그래머스 고득점Kit] 전화번호목록(해시) - c++ 접근 처음에 문제를 보고 길이순으로 정렬한 다음에 비교하면 되겠다 라고 생각하고 코드를 짰다. 길이가 같으면 서로 같은 문자열은 없으므로 비교할 필요가 없으니 continue를 해주면 효율성을 충분히 고려하는거라고 생각했는데 정확성은 다 통과하지만 효율성 3, 4번을 통과하지 못했다. 오답코드 #include #include #include using namespace std; bool compare(string a, string b){ if(a.size()==b.size()){ return false; } else { return a.size() 2021. 9. 18.

BOJ 4179 ) 불! (C++) 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net BFS로 풀리는 문젠데 예외 처리 하는 부분에서 미처 고려하지 못한 부분이 있어 좀 헤맸다. 1. 불의 이동경로에 대한 큐와 지훈이의 이동 경로에 대한 큐를 각각 만들어주고 입력을 받으면서 시작점들을 각 큐에 입력해준다. 그리고 지훈이의 이동 시간을 체크할 배열(dist)과 불의 이동 시간을 체크할 배열(burn)에 이동 가능한 좌표를 -1로 체크해준다. (따로 체크하지 않은 좌표는 0으로 초기화 되어 있으므로 추후 방문여부 체크 시 해당 좌표가 .. 2021. 7. 28.

BOJ 1012 ) 유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net DFS로 간단히 해결 할 수 있는 문제. 왠진 모르지만 예전에 풀려고 시도했다가 실패한 흔적이 남아있었다. 벡터를 이용해 밭의 크기를 런타임에 지정해주고 배추는 1로 표시한다. 방문여부는 배추가 없는 곳은 방문할 필요가 없으므로 기본은 모두 0으로, 배추가 있는 곳은 배추 위치를 표시하면서 같이 방문여부를 1로 변경해준다. 그 이후에는 반복문을 돌면서 배추가 심겨진 곳을 dfs로 탐색한다. 다음 칸을 방문할지 말지는 배추가 있는지와 방문한적이 없는지를 모두 고려해준다. #i.. 2021. 3. 12.

BOJ 1003 ) 피보나치 함수 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 간단한 DP로 해결할 수 있는 문제다. '피보나치 + 제한시간이 짧음' 에서 바로 DP가 생각나서 그렇게 풀었다. 그냥 피보나치문제를 풀 수 있다면 어려움 없이 풀 수 있는 문제. #include #include #define pii pair #define x first #define y second using namespace std; int T,N; pii fib[42]; void makefib(){ fib[0]={1,0}; fib[1]={0,1}; for(int i=2;i>T; makefib(); while(T--){ cin>>N; cout 2021. 3. 12.

이전 1 2 3 다음

티스토리툴바