본문 바로가기

Study/Algorithm

 (36)
백준 #1963 : 소수경로 https://www.acmicpc.net/problem/1963 > b; cout
백준 #9019 : DSLR bfs문제였다. 최단경로 => BFS ! 그리고 path reconstruct할때 reverse하는거 잊지말자! /** * @name: DSLR * @link: https://www.acmicpc.net/problem/9019 * @date 2020-04-30 * @author sunmon * TIP: String으로 이용 **/ #include #include #include #include using namespace std; int parent[10000]; string DSLR[4] = {"D","S", "L", "R"}; int dslr(int n, int t){ if(t == 0) return (n a >> b; cout
[백준] #10844 쉬운계단수 개요 동적계획법을 사용했다. 이 문제를 풀면서 많은 것을 배울 수 있었다. 1. 재귀로 너무 많이 돌리거나, cache[10000+1]이런식으로 커지면 메모리 초과가 난다.. 2. 메모리 초과가 나면 bottom-up방식을 생각해보자 3. 재귀 대신 for문 사용도 고려해보자 4. 어차피 피보나치처럼 n-2, n-1만 쓸거면 캐시를 100개씩 만들필요없고 3개만 만들어도 된다! 5. INT말고 LONG LONG쓰는거 주의하자 6. MOD연산도 주의하자 기존에는 맨날 재귀로만 돌려서 어떻게 bottom-up과 for문을 사용하는지 몰랐었는데 이 문제를 풀고 알게됐다. 재귀함수에 쓸 파라미터 수를 고려하여 cache나 저장할 변수를 만들어서 사용하면 된다. 코드 기존에 썼던 방법 (재귀): for문으로 bo..
코딩테스트에서 신경쓸 것 첫 번째 테스트케이스만 맞고 두번째부터 틀린다면 : 전역변수 초기화 전 역 변 수 초 기 화 뭔가 이상하다 dp인데 너무 복잡하다싶으면 : 조건 확인하기 문 제 조 건 확 인 너무 국소적인 부분으로 파고든다 싶으면 : 천천히 문제 다시 읽기 문 제 다 시 읽 기 최소값, 최대값 입력해봐서 결과 확인하기 최 대 최 소 입 력 테스트케이스끼리 순서 바꿔서 넣어보기. input받다 break; return;하면 다음 테스트케이스에 영향감 순 서 바 꿔 보 기 1. 전역변수 초기화 solution함수에서 계속 쓰는 전역변수. vector에 push_back하기 전에 초기화 했는가? - vector.clear() ; 원소만 지움. 메모리 할당한 것은 그대로! - 메모리까지 아예 초기화하는 방법; (vector v..
코 드 조 아 이번주 문제: https://www.hackerrank.com/challenges/angry-children/problem Max Min | HackerRank Given a list of N integers, your task is to select K integers from the list such that its unfairness is minimized. www.hackerrank.com https://www.hackerrank.com/challenges/non-divisible-subset/problem?utm_source=mobile&utm_medium=mobile_browser Non-Divisible Subset | HackerRank Find the size of the maximal ..
[2017 카카오 예선] 보행자 천국 2017 카카오코드 예선 https://programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 | 프로그래머스 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr 컨셉 고등학교 때 했던 수학문제. 간 단 쓰. way[i][j] //(i,j)까지 갈 수 있는 방법의 수 way[i][j] = way[i-1][j] + way[i][j-1] //위에서 오는 방법의 수 + 왼쪽에서 오는 방법의 수 단, 직진코스(city_map 값이 2인 경우)이 있는 경우는 조금 다르다. - 직진인..
[동적계획법테크닉] 3. 광학 문자 인식 컨셉 1. A라고 인식한 단어가 B일 확률 == B인데 A라고 인식할 확률. - 이유: 다음 표를 보자. (X → Y : X인데 Y로 인식할 확률) X(실제)＼Y(인식) A (인식) B C A (실제) 0.5 0.2 0.3 B 0.1 0.7 0.2 C 0.3 0.0 0.7 예) 실제 A인데 B로 인식할 확률 = 0.2 / B로 인식했는데 실제론 A일 확률 = 0.2 실제론 X인데 Y로 인식할 확률(X를 보고 →Y찾기)이나, Y로 인식했는데 실제론 X일 확률이나(Y를 보고 X를 찾기) 같다. 2. OCR(index, real) //인식한 index번째 단어가 사실은 단어 real일 확률 OCR(index, real) = ∑ OCR(index-1, 단어 i) * (단어 i 다음에 단어 real이 올 확률) ..
[동적계획법 테크닉] 2. 여행 짐 싸기 컨셉 int packing(int index, int capacity) //capacity만큼 용량이 남은 경우, item[index]부터 짐을 쌌을 때 가능한 최대 절박도를 리턴한다. //packing(index,capacity) = item[index]를 짐에 넣은 경우, 안 넣은 경우 중 절박도가 큰 것 packing(index, capacity) = MAX(packing(index+1, capacity) , packing(index+1, capacity - items[index].volume); 초안 내가 쓴 코드(정답, 12ms) ...더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32..

티스토리툴바