티스토리

정리하기 위한 블로그
검색하기

블로그 홈

정리하기 위한 블로그

limdef.tistory.com/m

글을 많이 쓰자

구독자
5
방명록 방문하기

주요 글 목록

  • 중복 조합(combinations with repetition) / N과 M(4) - 중복 조합 중복을 허용하여 원소를 선택하는 조합. n개의 원소를 r번 중복 허용하여 선택하는 경우의 수. nHr = n+r-1Cr 예를 들어보자. n개의 원소 {1,2,3,4,5}가 있다고 가정. 이때 3개를 중복 허용하여 선택한다고 하자. {1,1,1} , {1,1,2}, {1,1,3}, ... , {1,2,2} , {1,2,3} , ... , {5,5,5} 가 될 것이다. 조합이므로 순서 개념이 없으므로 {1,1,2}, {1,2,1}, {2,1,1} 은 하나의 경우로 취급. ( {1} 2개 , {2} 1개) - 왜 nHr = n+r-1Cr 일까? 위의 예를 든 5H3을 생각해보자. ㅁ ㅁ ㅁ 3개의 빈칸(r)과 / / / / 4개의 칸막이(n-1)가 있다고 생각. ㅁ ㅁ ㅁ / / / / -> 1.. 공감수 0 댓글수 0 2023. 7. 1.
  • 백준 BOJ 15650 N과 M(2) permuation - 순서가 있는 경우의 수 combination - 순서 개념이 없는 조합의 경우의 수 permuation, combination 구현과 차이점 - permutaion은 탐색 시 처음 원소부터 다시 탐색. (3을 골라도 이후 재귀에서 1부터 다시 탐색) - combination은 탐색 시 현재 원소(idx)의 이후의 idx만 탐색. (3을 골랐으면 이후 재귀에서 4,5,6.. 만 고려) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmic.. 공감수 0 댓글수 0 2023. 7. 1.
  • 백트래킹(Backtracking) / N과 M(1) 용어에 대한 정리가 필요하여 작성. 백트래킹이란? - 모든 경우의 수를 전부 고려하는 알고리즘. 단 탐색 중에 유망하지 않은 경우에는 이전 단계로 돌아가서 다른 후보 탐색. 완전 탐색의 일종. 완전탐색(Bruteforce)과 백트래킹은 무엇이 다른가? - 완전탐색은 모든 경우의 수를 대입. 유망성을 검사하지 않음. 간단한 백트래킹 문제 하나. https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 경우의 수는 nPr = n! / (n-r)! 이 된다.. 공감수 0 댓글수 0 2023. 7. 1.
  • 외판원 순회 (Traveling Salesman Problem) 외판원 순회 문제 - 여러 도시가 있고 도시 간 이동 비용이 있을 때 모든 도시를 한 번씩만 방문하여 시작 위치로 돌아오는 경로의 최소 비용을 구하는 문제. 각 도시가 20개라하면 20개의 도시를 모두 방문하는 경우의 수는 20! 이 된다. 모두 계산하지 않고 bitmask + memoization을 이용한다. https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 왜 dp[12 의 경로를 탐색하고 dp[101]의.. 공감수 0 댓글수 0 2023. 6. 20.
  • LIS (Longest Increasing Subsequence) LIS 구현 1. lower bound 사용하여, 2. 새로운 값 x가 기존 lower bound 배열의 가장 큰 값보다 크면 뒤에 추가 기존 lower bound 배열에서 x보다 같거나 큰 값 중 첫 번째를 찾아 업데이트 해준다. 즉 F, F, ... F, T, .. T 인 분포에서 x 공감수 0 댓글수 0 2023. 6. 17.
  • 백준 BOJ 11025 요세푸스 문제 3 풀이를 안 보고 풀진 못 했다. 해답이 많이 올라와 있지만 스스로 정리를 하며 기억하기 위해 작성해본다. 1. 문제 https://www.acmicpc.net/problem/11025 11025번: 요세푸스 문제 3 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000,000) www.acmicpc.net 1번부터 N번까지 원형으로 앉아있고 K번째 마다 제거 할 때, 마지막에 남은 번호를 구하는 문제. 1 > n >> k; int ans = 1; for(int i=2; i 공감수 0 댓글수 1 2023. 1. 22.
  • 백준 BOJ 12849 본대산책 예전에 어떤 알파벳은 특정 알파벳 다음에만 올 수 있다는 규칙의 문제와 같다 (ex u는 e,i,o 다음에 올 수있고 e 는 a,u,o 다음에 올 수있고..) 특정시점의 어느 위치는 그 바로 이전의 연결된 위치에서만 올 수 있다 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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #include #include #include #include #include #include #include #define INF 1e9 #define MOD 1000000007 using namespace.. 공감수 0 댓글수 0 2021. 1. 2.
  • 백준 BOJ 2473 세 용액 모든조합, 즉 완탐하면 5000*5000*5000으로 터진다(아마) 모든 기준점(mid)에 대해 투포인터로 탐색하면 되는데 이 경우 O(n^2)으로 가능하다. 정렬 후 세용액의 합이 0보다 클때 그 시점의 right보다 큰 값은 탐색할 필요가없다 당연히 현재 세용액의 합보다 더 클테니 반대로 세용액의 합이 0보다 작을때는 그 시점의 left보다 작은 값은 탐색할 필요가 없다. 결론 투포인터 응용문제였다. 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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #include #include.. 공감수 0 댓글수 0 2020. 12. 31.
  • 백준 BOJ 2568 - 전깃줄-2 가장 긴 증가하는 부분 수열과 같은 문제이다. 가장 긴 증가하는 부분 수열을 구할때 d[] 배열로 수열의 크기는 알 수 있지만, 수열의 순서를 보장해주진 않는다. 따라서 p[]배열에 따로 d[] 배열에서의 인덱스를 저장해놓는다. 그 후 가장 큰 인덱스부터 1까지 부분수열인지 체크를 하면된다. 이때 수열을 순서대로 출력해야한다면 stack을 사용하면 되고, 이 문제에서는 해당하지 않는 전깃줄만 자르면 되기 때문에 해시맵에 저장을 하면된다. 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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 5.. 공감수 1 댓글수 0 2020. 12. 31.
  • 백준 BOJ 14725 개미굴 Trie의 자료구조를 참고하고 map을 잘 사용하면 쉽게 풀린다고 한다. 어떻게 접근해야할지 감이 안잡혔는데 풀이를 익혀놔야겠따. 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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #include #include #include #include #include #include #include #include #include #define M 1e7+19 using namespace std; using lld = long long int; using.. 공감수 0 댓글수 0 2020. 12. 29.
  • 백준 BOJ 2536 버스 갈아타기 시도1 . 현재위치 cx,cy를 큐에 넣고 이 위치를 지나가는 버스를 큐를 pop 할때마다 탐색하여 타지않은 버스를 타고 그 버스의 경로에 뿌리며 큐에 넣는 방법은 시간초과 시도2. 버스의 경로를 보고 교차점이 존재하면 서로 연결된 노드로 판단한다. ( 5000 * 5000 ) - 가로 가로 , 가로 세로 , 세로 가로, 세로 세로 4가지 케이스로 나누어서 판단. bfs 탐색 시간과 메모리가 조금 크긴한데 통과하였다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858.. 공감수 0 댓글수 2 2020. 12. 5.
  • 백준 BOJ 5719 거의 최단 경로 재채점이 되고 메모리초과가 되어있길래 무엇이 문제인지 추측 if (visited[cur_v][next]) continue; visited[cur_v][next] = true; 위 코드를 추가했더니 통과하였따. 저 부분에 걸리는 테케를 생각해보는데 모르겠다..... 무엇일까 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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85.. 공감수 0 댓글수 0 2020. 12. 5.
  • 백준 BOJ 2904 수학은 너무 쉬워 이 문제는 각각의 수를 소인수분해하여 각각의 숫자들이 소인수를 잘 나눠 가지면 답을 구할수 있다. 예제에서 8 24 9 가 주어졌는데 8 - 2 2 2 24 - 2 2 2 3 9 - 3 3 2가 6개 3이 3개 이를 잘 나눠가지면 각 숫자들이 2 2 3 = 12 가 될 수 있다. 즉, 각 소인수를 " 소인수의 총 개수 / 주어진 n " 으로 나눠가지면 가장 큰 점수를 구할 수 있다. 그 과정은 다음과 같다. 1. 소수체크를 해준다. 2. 각 숫자를 소수로 나눠주며 총 소인수 개수를 count해준다. 3. 각 숫자당 소인수와 그 개수를 알아야 최소 몇번만에 가능한지 알 수 있다. 이를 어떻게 세야할지 고민하다가 map을 n개만큼 배열로 선언하여 세어주었다. (1,000,000 * 100 의 배열을 하면 메.. 공감수 0 댓글수 0 2020. 10. 31.
  • 19237 BOJ 어른상어 주의할 점 1. 로직 처리 순서 잘 파악하기 괜히 구조체 맵 배열 선언하지말고 맵을 여러개 선언하는것이 훨씬 더 편함 (ex amap[20][20] , bmap[20][20], cmap[20][20]) 2. 정답 출력할 때 확실히 if(cnt==1)로 처리하니까 time이 1001이 되면서 cnt가 1이되는 경우에 틀려버림 if(time= n || ny >= n) continue; if (bmap[nx][ny] == 0) sc++; } return sc; } void scatter() { for (int i = 0; i 0) { bmap[i][j]--; if (bmap[i][j] == 0) cmap[.. 공감수 0 댓글수 0 2020. 10. 11.
  • 백준 BOJ 10407 - 2타워 1. "2가 짝수개 있으면 3으로 나눈 나머지는 1이다. " -> (A*B)%X = (A%X * B%X)%X -> 2가 2n개 있다면, ( (2*2)%3 * (2*2)%3 * ... *(2*2)%3 ) %3 = (1*1*...*1)%3 = 1 1 , 2, ... , n 2. "높이가 2이상인 2타워는 2가 짝수개다. " -> 높이 i+1의 수는 높이 i 의 수만큼 2를 곱한값이다. -> 높이 1은 짝수 -> 다음 높이는 짝수개만큼 2가 있음 = 2가 짝수개 -> 다음 높이는 그 짝수만큼 2가있음 -> 다음 높이는 그 짝수만큼 2가있음 .................... 3. "따라서 높이가 2이상인 2타워의 나머지는 1이다. " 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17.. 공감수 0 댓글수 0 2020. 9. 25.
  • 백준 BOJ 4752 - HTML 에디터 부분문자열의 끝(e)까지 열려있는 태그를 저장해둔다. 이때 다음의 경우에대해 예외처리를 해준다. 1.부분문자열 안에 여는태그 닫는태그 둘다있는경우 2.부분문자열 안에 여는태그만 있고 닫는태그가 없는경우 3.부분문자열 안에 여는태그가 없고 닫는태그가 있는경우 부분문자열까지의 (b까지) 태그 관리 = v 부분문자열 안의 태그관리 = v2 1번의 경우 - v2가 0보다 큰경우이다. v2를 pop_back 해준다. 2번의 경우 - v2에 태그를 추가해준다. 3번의 경우 - v2가 0인 경우이다 이때의 경우를 cnt++ 해준다. 그 다음 부분문자열까지의 여는태그의 닫는태그 출력시 cnt를 이용해 이미 닫은태그는 출력하지 않는다. 그후 저장된 태그들을 순서에 맞게 출력해준다. 1. 부분문자열까지 여는태그 출력 2... 공감수 0 댓글수 0 2020. 8. 23.
  • 백준 BOJ 5052 - 전화번호 목록 테스트 케이스가 50개이고 주어지는 전화번호의 수가 최대 10000개이다. O(N^2)의 풀이는 10000x10000x50 = 5억 으로 시간초과 날것이다. 그렇다면 nlogn 혹은 n으로 풀어야한다. 완탐인가 싶지만 곰곰히 생각해보면 정렬(nlogn) 이후 o(n)으로 풀 수 있다. 먼저 문자열들을 알파벳순으로 정렬한다. (만약 133과 13이 있다면 13-> 133순서로 정렬이됨) 그 후 내 다음 순서에오는 문자열하고만 포함관계가 성립하는지 판별한다. 즉 i번째 문자열이 i+1번째 문자열에 포함이된다면 그대로 NO로 끝나게되고 포함이 되지않는다면 i+2번째 이후의 모든 문자열에 포함이 되지 않는다. 123456789101112131415161718192021222324252627282930313233.. 공감수 0 댓글수 0 2020. 8. 18.
  • 백준(BOJ) 2517 달리기 sum함수에서 s~e 까지의 합 = tree[node] 구하고자하는 범위 l~r 먼저 실력을 등수로 매핑을 해야한다. 실력의 범위가 1 이상 1,000,000,000 이하라서 10억 배열을 선언할 수 없기 때문에 그 후 등수를 기준으로 세그트리를 활용한다. 트리를 0으로 세팅후 나의등수 p 보다 작은 1~p-1의 구간합을 구한다. 이때 구한 값이 내가 앞지를 수 있는 선수의 숫자이다. 그 후 등수 p (==idx)를 1로 update 해준다. 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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 5.. 공감수 0 댓글수 0 2020. 7. 17.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.