본문 바로가기

전체 글

[Lev.3] 자물쇠와 열쇠(C++) 1. 문제 2. 접근 방법 1. 문제 조건 보면서 범위 줄여가기 1) 모든 홈이 다 차야 한다 => 홈이 발생한 구역을 구한다. 만약 열쇠 사이즈가 홈 구역보다 작으면 false return(경우의 수가 아예 안만들어 진다.) 2) 자물쇠의 돌기와 열쇠의 돌기가 맞닿으면 안된다 => 홈이 아닌 부분은 무조건 돌기이다 => 자물쇠의 홈 구역 밖으로 열쇠의 돌기가 있는 경우는 열 수 없음 3) 자물소의 홈 모양 전체와 열쇠의 돌기 모양 일부가 일치해야 한다. -> 나는 처음에 이렇게 접근했었는데, 이렇게 좁은 범위나 예외 케이스부터 생각하지 말고 큰 관점에서 먼저 생각하는 연습을 하자. 2. 가장 간단한 방법부터 생각하기 1) 모든 경우에 대해서 열쇠를 돌려가면서 맞춰본다 -> 완탐 -> 범위를 보니 가능한.. 더보기
N으로 표현(DP) / C++ 1. 문제 2. 접근 방법 1) 문제 조건, 제한 범위 찾기 - N은 최대 8번 사용 가능하다 => 연산을 수행할 수는 N~NNNNNNNN까지 가능 - 괄호 사용 가능 2) DFS로 풀기 2-1) 종료 조건 : 원하는 수를 찾았을 때, cnt가 8을 넘어갔을 때 2-2) 재귀 함수 호출 : 0부터 시작, 현재 수에 N부터 NNNNNN까지 사칙 연산을 각각 수행하면서 재귀함수를 호출한다. => 현재 수 (+ / - / * / 나눗셈) N,NN,NNN,...,NNNNNN 2-3) 효율적으로 짜는 법 : - 현재 수가 0인 경우엔 곱셈 나눗셈 수행 안함 - 2-2)에서 현재 수에 연산할 N의 범위는 최대 NNNNNN이다. (for문은 N부터 NNNNNN까지 6번 수행) NNNNNNN과 NNNNNNNN이 안되는.. 더보기
[2장] 운영체제 개요 1. 운영체제(Operating system) 정의 - 시스템(System): 기반이나 틀이되는 하드웨어를 지칭. 소프트웨어인 운영체제가 시스템으로 쓰이는 것은, 하드웨어가 OS와 같이 동작이 되어야만 사용자가 쓸 수 있는 하나의 "컴퓨터 시스템"이 되기 때문임 - 하드웨어 바로 윗단에 설치되는 소프트웨어 - 컴퓨터를 동작시키기 위해 필요한 소프트웨어 - 메모리에 항상 상주하며, 전원을 켬과 동시에 실행되는 운영체제를 커널(Kernel)이라 함 - 시스템을 위한 유틸리티(copy)는 넓은 의미의 운영체제라 함 2. 운영체제 기능 - 하드웨어와 사용자 사이에 존재하므로, "하드웨어를 위한 역할"과 "사용자를 위한 역할" 두 가지로 나눌 수 있다. 1) 시스템 내의 자원을 관리(resource manager.. 더보기
[9251] LCS(C++) 1. 문제 2. 접근 방법 - 못풀어서 해답을 찾아보았다. http://melonicedlatte.com/algorithm/2018/03/15/181550.html [백준] 9251번 C/C++ 풀이 _ LCS - Easy is Perfect 출처 : https://www.acmicpc.net/problem/9251 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB76453240240041.746% 문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, � melonicedlatte.com - dp[i][j] : s1.substr(0,i) , s2.substr(0,j)의 LCS 길이 (i번째, j 번째 문자열을 선택했을 때가 아님) .. 더보기
[2293] 동전 1(C++)/DP 1. 문제 2. 접근 방법 1. 순서는 고려하지 않는다 = 사용한 각 동전의 "개수"가 중요하다. = 사용한 동전의 개수 기준으로 경우의 수 나누기 2. 경우의 수를 구하라 1) 아래 두 가지 중 더 접근하기 쉬운 것이 무엇인지를 인지하면서 점화식 구해보기 return 1 + foo(n-1) 형식으로 접근하는 법 (1가지 경우의 수 씩 count) return foo(n-1) + ...foo(n-2) 등 n-1과의 점화식으로 접근하는 법 2) 경우의 수 만드는 기준 정하기 어려울 때 : 문제에서 input으로 주어진 값들을 기준으로 하기 or 값의 범위가 더 제한적인 것을 기준으로 하기 ex) 이 문제에선 사용할 수 있는 동전의 가치가 연속(1,2, ... , n)이 아니라 주어진 값만 쓸 수 있다.(제.. 더보기
상반기 마무리 / 하반기 계획 & 생각 > 건동홍 , 4점대 초반, 융합 전공 이수, 정처기&컴활, IM2, 수상 2회, 연구생 경험, 플젝 3~4개, 외부 교육 4회 1. 상반기 결과 1) 채용 결과 - 총 서류 제출 23회 * 서류 불합: 13회( 코테 & 서류 전형 2회, 교육 2회, 서류 전형 9회) * 코테/(코테 없이)1차 면접 불합 : 5회 * 직무 면접 불합 : 2회 * 최종 불합: 1회 * 진행 중: 2회 - 산업군 별 합격률 * 반도체/하드웨어 : 2회 중 서류탈 2회 (서합률 0%) * 은행 : 4회 중 서류탈 3회, 코테 탈 1회 (서합률 25%) * 금융권(증권사, 보험사) : 4회 중 인적성/1차 면접 탈 2회 , 최종 탈 1회, 진행 중 1회 (서합률 100%) * 교육 : 3회 중 2회 서류탈(1회는 추가 합격),.. 더보기
[백준]수학1 1. 나머지 연산 답을 M으로 나눈 나머지를 출력하라는 문제 시 유의 할 것 분배법칙 성립 1. (A + B) mod M = ( (A mod M) + (B mod M) mod M) 2. (A * B) mod M = ( A mod M) * (B mod M) mod M) 3. (A - B) mod M = (( A mod M) - (B mod M) + M) mod M) //뺄셈의 경우 주의 4. 나눗셈은 성립 X 2. 최대 공약수 최대공약수는 GCD라고 함 가장 쉬운 방법: 2부터 min(A,B)까지 모든 정수로 나누어 보는 방법 for(int i=2; i (3/3 = 1 ...0) => (1/3 = 0 ...1) 따라서 답은 102 5. 소수 약수가 1과 자신 밖에 없는 수 2, 3, 5, 7, 11, 13.. 더보기
[1010]다리 놓기(C++)/DP 1. 문제 2. 접근 방식 1) DP 1) 항상 n개의 다리를 만들어야 한다. 1번째 다리의 동쪽 사이트 번호는 1이상 (M - N + 1 )이하 n번째 다리의 동쪽 사이트 번호는 N이상 M이하 i번째 다리의 동쪽 사이트 번호는 i 이상 (M - N + i ) 이하 2) (i번째 다리의 동쪽 사이트 번호) > (i-1번째 다리의 동쪽 사이트 번호) 3) 1과 2를 합쳐보면 i번째 다리를 만들 때 고려해야 하는 것 :"i-1번째 다리를 만들 때 몇 번 사이트를 선택했는가"임을 알 수 있다. 직전에 몇 번 사이트를 선택했는지를 알면 내가 현재 선택할 수 있는 다리의 개수를 알 수 있기 때문이다. 따라서 "현재 나는 몇 개의 다리 중 하나를 고를 수 있는가" = "직전에 몇 번 사이트를 선택했는가" 로 이해할.. 더보기

티스토리툴바