본문 바로가기

전체 글

 (336)
백준 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 을 선택했을 때 다음으로..
OS - 식사하는 철학자 문제와 교착상태(DeadLock) 식사하는 철학자 문제 철학자들은 밥먹고 생각하는게 일이다. 참 팔자 좋은 인생들.. 아무튼, 그들은 밥상 머리 앞에서도 생각을 한다. 한 입 먹고 내려놓고 생각하고 한 입 먹고 내려놓고 한다. 그런데 사람이 5명인데 젓가락도 5개다. 쌍이 아니라 5개다. 원형 탁자에 앉아있다고 가정하면 다음과 같은 사진이 될 것이다. 1번 철학자가 양쪽 젓가락을 들었다고 하자. 그렇다면 2번과 5번은 젓가락이 하나밖에 없기 때문에 밥을 먹을 수 없다. 계속 철학자들은 밥을 먹고 내려놓고 생각하고 반복한다. 그런데, 언젠가 이런 일이 생긴다. 3번이 오른쪽 젓가락을 들었을 때 4번이 오른쪽을 들고 … 즉, 모두가 자신의 오른쪽 수저를 들어버리는 것이다. 이렇게 되면 어떻게 될까 . 아무도 밥을 먹을 수 없다! 아무도 젓가..
백준 3079번 입국심사(C++) https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 처음 문제를 봤을 때 우선순위큐 문제라고 생각했다. 그러나 몇 초 쉬고 다른 심사대로 이동하는 것을 생각해보면 아무래도 우선순위 큐로는 풀어낼 수 없다. 그러다가 분류를 보니 이분탐색 파라메트리 서치가 보였다. ? 아니 이걸 어떻게 파라메트리로 ? 라고 생각해서 기다렸다가 가는 시간초를 파라메트릭으로 판단하나? 생각했는데 그걸리가 없지. 파라메트릭은 보통 "정답" 을 반환한다. an..
프로그래머스 - 거리두기 확인하기 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/81302 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근법 - 처음 봤을 때는 bfs 한번으로 해결하기 위해 고민했으나 각 P 별로 bfs를 돌아도 N이 워낙 작아서 시간초과가 나지 않는 문제이다. 플로이드-워셜도 생각이 났는데 플로이드 워셜은 행렬에서 사용해본적이 없고 간선의 비용이 주어지면 행렬로 표현하는 것이라 결이 다르다고 생각이 된다. 각 대기실은 5x5크기이기 때문에 bfs의 시간복잡도는 25이고, 모든 칸에 P가 존재하는 경우의 수를 ..

티스토리툴바