본문 바로가기

전체 글

 (403)
백준 1107번 리모컨 (C++) https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 내 접근 - Greedy 문제라고 생각했다. 만약 4987 인데 9가 금지라면 9대신에 가장 근접한 8을 배치하고 49XX보다 48XX가 더 작으므로 격차를 최소로 하기 위해 사용할 수 있는 가장 큰 값을 배치하여 4888로 지정하고 4987 - 4888 + 자리수 = 103 이렇게 생각했다. 그러나 이러면 자리수가 바뀔 때를 계산할 수 없다. 예를 들어 9998 이고 9가 금지..
백준 11000번 강의실 배정 (C++) https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 이전에 풀었던 BOJ문제 공주님의 정원 문제와 비슷하다고 하여 풀어봤다. 공주님 문제를 어렵게 느꼈고 깨달은 것이 많은 문제여서 비장한(?) 마음으로 임했다. 먼저 최대한 수업시간들이 이어져있도록 꼬리물기를 시켜야한다. 그러므로 한 수업이 끝나고 다음 수업들의 수업을 스캔하는 과정이 필요하다. 1 2 1 2 2 7 2 4 3 7 이라고 가정하자. 그렇다면 먼저 1~2 수업을 할 것이다. 그리고 다음 수업시간의 시작 시간과 이전 수업 시간의 끝나..
백준 2457번 공주님의 정원 (C++) https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 처음 문제를 보고 투포인터 이분탐색이 생각났다. 처음 꽃은 반드시 3월 1일 이하부터 피어야하고 마지막 꽃은 12월 1일 이하에 져야한다. 그러므로 각 포인터들을 이동시켜서 최적의 조건을 만든 후 checking 절차를 하면 된다고 생각했다. 결론적으로 말하면 위 방법이 완전히 틀린 것은 아니지만 이렇게할 필요도 없고 문제의도와 맞지 않다. 이 문제의 의도는 Greedy 이다...
백준 9251번 LCS(C++) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 최장 공통 수열이란 ABCDE BCFZ E 두개가 있으면 BCE가 공통 수열이다. 즉 이어져있지 않아도 순서만 맞으면 된다는 뜻이다. 이 문제는 DP분류이지만 LCS알고리즘이라는 말이 따로 있을 정도라 카테코리로 분류해도 된다고 생각이 든다. 처음에는 2 x N 배열로 문제를 해결하려 했는데 사실 알고보니 두 문자열의 길이가 다를수도 있어서 될수가 없는..
이미지 객체 인식 DarkNet (Yolo4) DarkNet은 Yolo4 개발자가 만든 프레임워크로 아주 간편하게 객체 인식을 수행할 수 있다. 아무래도 StyleGAN2,3 Pixel2Style2Pixel, DOMIAS 등 올려져있는 깃허브를 활용하는 것 조차 어려움이 많았기 때문에 이번에도 어렵지 않을까 생각했는데 만들어진 툴들이 아주 좋아서 어렵지 않았다. 라벨링 https://yeko90.tistory.com/entry/free-image-label-tool-labelimg 이블로그에 너무도 설명이 잘 되어있다. 학습 준비 먼저 data/list 파일을 하나 만들고 세개의 txt파일을 만든다. 각 txt파일에는 test, train, valid할 이미지의 경로가 있다. 그리고 각 경로에는 라벨링한 txt파일과 이미지 파일이 1대1 대응으로 존..
백준 15683번 - 감시(C++) https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 삼성 SW 역량 기출 문제 답게 상당한 구현을 요구하는 문제이다. 접근법 - 먼저 이 문제는 CCTV들이 4방향이 가능하고 총 5가지 종류가 있다. 모든 CCTV의 상태 별 감시 위치를 확인해야하기 때문에 이 문제는 BRUTEFORCE 완전 탐색 문제이다. 그러나 브루트포스하게 몇 중 반복문으로 해결하기는 힘들다. CCTV의 숫자가 정해져있지 않기 때문이다. 내가 선택한 방법은 DFS ..
백준 1759번 암호 만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 전형적인 순열 구하기 문제이다. dfs 백트래킹으로 검사하고 주의할 것은 자음의 수가 2개 이상이라는 것만 체크하면 된다. 그런데 난 모음의 요소를 저렇게 검사했는데 맞는지 모르겠다. 시간 복잡도는 O(조합 * N) 으로 빠른시간에 해결 가능했다. N이 높지 않은 탓이다. 문제를 보고 바로 파악할 수 있었다. 코테에서도 이래야할탠데... #include #include #include using nam..
백준 9465번 - 스티커(C++) https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 2차원 DP문제이다. 이 문제를 지난학기에는 풀지 못했었는데 이번에 풀게 되어 기쁘다. 놀기만 한 건 아니라는 거지.. 아무튼, 2차원 dp배열을 선언하고 풀이하면 된다. 이 문제는 bottom up 방식으로 먼저 왼쪽부터 오른쪽으로 진행하며 풀이를 했다. 오른쪽에서 왼쪽으로 가도 상관은 없다. - 접근법 이 문제를 재귀나 분기로 풀면 어떻게 될까. 만약 0,0 을 선택했을 때 다음으로..

티스토리툴바