본문 바로가기

분류 전체보기

 (336)
백준 7579번 앱 (C++) https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 문제를 보면 어떻게 접근해야할지 어려울 수 있다. 나도 처음에 dp라는 알고리즘 분류를 못봤다면 매우 어렵게 풀었을 것이다. 이 문제를 배낭 문제라고 판단해야할 프로세스는 다음과 같다. 1. 모든 경우의 수를 따져봐야한다. 그렇다면 경우의 수를 따질 수 있는 알고리즘을 검토한다. 2. 재귀, dfs 백트래킹, 브루트포스, dp - 재귀: N이 100이므로 사용할 수 없다. - dfs 백트래킹: 마찬가지로..
SWEA - 햄버거 다이어트 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com N이 20밖에 안되기 때문에 재귀 방식으로 풀어낼 수도 있다. 처음 부터 요소를 살펴보면 두가지 행동이 가능할 것이다. 아직 제한 칼로리를 넘지 않았음을 깔아두고 1. 이번 재료를 소모하고 지나간다. 2. 이번 재료를 쓰지 않고 넘어간다. 그렇다면 함수는 아주 간단하다. void dfs(int idx, int sum_socre, int sum_cal){ answer = max(answer, sum_socre); //cout value >> weight;..
백준 11729번 하노이 탑 이동 순서 (C++) https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 하노이탑은 재귀문제에서 가장 기본적인 문제로 대학 강의에서 처음 배우게 된다. 그러나 나름 어려운 편이고 기본기를 정확히 하자는 의미로 하노이탑을 풀어봤다. 접근법 하노이 탑의 가장 기본적인 요소는 높이가 4인 하노이탑을 3번 막대로 옮기기 위해서는 맨아래 판을 제외하고 높이 3인 탑을 2번 막대로 옮기는 순서가 필요하다. 그러므로 Hanoi(4) -> Hanoi(3) 이렇게 포함이된..
프로그래머스 - [1차]뉴스 클러스터링 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/17677 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근법 - 우선 소문자와 대문자를 구분하지 않으므로 모두 소문자 혹은 대문자로 바꿔줘야한다. 그리고 합집합과 교집합을 구하면되는 간단한 문제인데 은근히 조건에 맞는 문자열을 구성하는 구현 실력을 요구했고 기본적인 집합 공식인 A + B - A n B = A U B 를 알고있어야했다. 처음 접근했을 땐 set 자료구조에 모두 박아놓으면 합집합이 될 것이라 생각했으나 1 2 2 3 2 2 3 이라하면..
백준 29792번 규칙적인 보스돌이 (C++) https://www.acmicpc.net/problem/29792 29792번: 규칙적인 보스돌이 보스의 체력 $P$의 제한 $2.66 \times 10^{11}$와 드랍하는 메소 $Q$의 제한 $1\,596\,506$은 2023년 8월 10일 업데이트 이전의 가장 많은 체력(카오스 혼테일)과 결정의 가격(노멀 파풀라투스)을 가진 일간 보 www.acmicpc.net - 접근법 이 문제는 다이나믹 프로그래밍 배낭문제이다. 그러나 캐릭터 1,2,3이 있다고 할 때, 1,2,3마다 dp를 돌려서 마지막 최댓값을 모두 저장해놓고 답을 도출하면 된다. 가장 중요한 건 배낭문제를 잘 이해하고 있느냐는 것이다. 배낭문제를 복기해보자. 최대 10kg 담을 수 있고 물건은 번호 무게 가치 1 4 6 2 2 7 3 5..
OS - 모니터 (멀티 스레드 프로그래밍) 프로세스/쓰레드 동기화 도구 중 하나이다. 세마포어는 너무 오래된 것이고 최근 자바는 모니터를 지원한다. Java의 모든 객체는 모니터가 될 수 있다. 베타 동기 - Common Variable 은 오직 하나만 접근할 수 있다. → synchronized 키워드 사용 조건 동기 - wait(), notify, notifyAll 메소드 사용 notifyAll 하면 모든 스레드가 풀려난다. 모니터는 사실 멀티코어 컴퓨팅 강의에서 배운 멀티 스레드 프로그래밍과 같은 것을 알게 되었다. 아래는 멀티코어 프로그래밍에서 과제로 해결한 소수찾기 문제이다. package Task; public class pc_dynamic { // 20만까지 테스트하기 위함 private static final int NUM_END ..
백준 15681번 트리와 쿼리 (C++) https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 접근법 - 먼저 그래프가 주어지고 이것의 루트가 주어진다. 그리고 트리를 구성하게된다. 그래프가 주어지고서 이것을 트리로 바꾸어야하기 때문에, 이것을 문제의 그림으로 표현하면 다음과 같다. 이 그래프에서 5를 루트라고 하였으므로 아래처럼 트리를 구성할 수 있다. 그리고 각 노드들의 서브트리의 노드 개수를 출력하면 된다. 이해하기는 쉽지..
백준 11438번 LCA 2 (C++) https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net LCA 공부를 열심히 하고서 풀이한 문제이다. LCA는 https://tigerfrom2.tistory.com/186 여기서 자세히 설명해두었다. 이 문제는 LCA1과 같은 문제지만 주어지는 노드의 수가 늘어났고, 시간이 더 타이트해졌다. LCA1은 조상을 탐색할 때 1씩 올라가며 탐색해도 AC를 받을 수 있었다. 그러나 이 문제는 dp를 활용하여 LCA를 개선하는 테이블을 미리 만들어둬..

티스토리툴바