거의 알고리즘 일기장

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 풀이방법 비트연산만 할줄안다면 풀수있다. void add(int x) { S |= (1

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이방법 https://kunkunwoo.tistory.com/60 프로그래머스_가장 긴 팰린드롬 https://programmers.co.kr/learn/courses/30/lessons/12904 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업.. kunkunwoo.tistory.com 이 문제와 유사하다. 자세한 설명은 위에 해놨으니..

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활�� www.acmicpc.net 풀이방법 냅색 알고리즘의 일종이라고 한다. (알고싶다면 밑의 블로그 참조할것) https://namnamseo.tistory.com/entry/%EB%83%85%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 냅색 알고리즘 냅색 문제는 유명한 다이나믹 문제 중 하나이다. (사진 출처 wikipedia.org) 가장 유치하지만 또 가장 많이 쓰이는 설명으로는, 한 가게..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지 www.acmicpc.net 접근 주어진 조건들을 먼저보자. 시간은 2초, MxN 행렬 (M, N [백준][1520번][DP] 내리막길 내리막길 https://ww..

https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다. www.acmicpc.net 주의사항 1. 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 2. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다. 풀이방법 https://kunkunwoo.tistory.com/101 백준 11066번 _ 파일 합치기 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 주의사항 소설이므로 장이 섞이면 안된다. -> 그러므로 바로 옆에 있는것하고만 파일을 합칠수있다! 접근 총 파일이 4개라고 하면 ..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이방법 예시인 1 ,2 5원으로 10원이 나올수있는 동전의 경우의 수를 잘 생각해보자. 일단 1원만 사용했을경우 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1, 2원 사용했을 경우 1 2 3 4 5 6 7 8 9 10 1 2 2 3 3 4 4 5 5 6 1, 2, 5원 사용했을 경우 1 2 3 4 5 6 7 8 9 10 1 2 2 3 4 5 6 7 8 10 잘 보면 ..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이방법 벨만 포드 알고리즘 사용. 음수 사이클 판별은 n번째에와 n-1번을 비교해서 다르면 음수사이클이 있다고 판단. 주의사항 1. 같은 경로로 여러가지 값이 들어올수 있으므로 최솟값만 저장하게 코드를 작성할것. 2. 거리값이 최대 6000*10000 으로 6억까지 들어올수 있으므로 int로 쓰면 오버플로우 될수있음. long long..

https://codeforces.com/problemset/problem/158/B Problem - 158B - Codeforces codeforces.com 풀이방법 1. 4명, 3명, 2명인 그룹을 먼저 태운다 ans = numOfGroup[4] + numOfGroup[3] + numOfGroup[2]/2; 2. 1명인 그룹, 2명인 그룹을 위에 맞춰 끼워탄다. ( 1번은 3번에 2번은 2번끼리 ) numOfGroup[1] -= numOfGroup[3]; numOfGroup[2] -= (numOfGroup[2] / 2)*2; 3. 2명인 그룹, 1명인 그룹이 남았으면 그에 맞춰 계산한다. if (numOfGroup[2] > 0) { ans += 1; numOfGroup[1] -= 2; } if (..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 www.acmicpc.net 풀이방법 1. cctv를 기준으로 left, right, up, down을 채울수 있는 함수 4개를 만든다. (밑의 코드참조) void f..