본문 바로가기

Programming456

[C/C++] 백준 #2210 숫자판 점프(집합, 백트래킹) #2210은 실버 문제로 난이도는 높지 않습니다. 백트래킹 알고리즘을 이용해서 모든 경우의 수를 찾아내었고, 집합을 이용해서 중복을 제거해서 풀었습니다. 문제 링크입니다. https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 기본적으로 2차원 배열에서 백트래킹은 경계조건하고 상하좌우 움직임 등만 잘 처리하면 큰 무리가 없습니다. 집합 자료구조는 C++에서 제공하는 것이 두가지인데, 일반 집합 자료구조는 se.. 2023. 4. 17.
[C/C++] 백준 #2207 가위바위보(2-SAT) #2207 문제는 문제 설명이 조금 어렵습니다. 사실, 모든 경우에 필승전략은 k번째 주먹, k번째 가위를 말하면 반드시 맞으니까, 필승전략이 되겠죠. 문제는 바로 이러한 필승 전략을 요구하는 것으로 보이지만, 실제는 그것이 아니라, 학생들이 말한 내용이 필패전략(즉, 한명이라도 맞추지 못하는)이 될 수 있는지 검사하라는 것입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2207 2207번: 가위바위보 첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각각의 학생들의 선택을 나타내는 두 정수 x, y(1 ≤ |x|, |y| ≤ M)이 주어진다. x가 양수일 경우에는 원장선생님이 x번째에 가위를 낼 거라는 www.acmicpc.net 필패전략이 되지 않으려면.. 2023. 4. 16.
[Python] 프로그래머스 택배 배달과 수거하기(탐욕 알고리즘) 이번 문제는 Level2 문제입니다. 탐욕 알고리즘을 사용하면 풀 수 있는 문제입니다. 문제의 링크입니다. https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제는 등간격을 가지는 집들이 택배사를 기점으로 있을 때, 각각의 집에서 요청한 택배의 개수와 수거품들을 최소한의 거리 이동으로 모두 처리하는 문제입니다. 그림에서와 같이 왼쪽에 택배사가 있고, 여러 집들이 1의 거리를 사이로 위치하고 있습니다. 택배차에는 실을 수 있는 택배 상자의 개수가.. 2023. 4. 16.
[C/C++] 백준 #2206 벽 부수고 이동하기(너비 우선 탐색) #2206은 평범한 너비 우선 탐색 문제는 아닙니다. 벽을 한번까지는 부실 수 있는 조건이 있기 때문에, 이에 대해서 처리를 해주어야 합니다. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제는 한번 이동하는데 항상 1이라는 가중치가 있는 그래프이기 때문에, 벽을 뚫고 갈 수 있다는 것을 원칙을 정해서 풀면 됩니다. 1) 벽을 한번 부수고 지나간 길은 음의 값으로 경로값을 적는다... 2023. 4. 16.
[C/C++] 백준 #2193 이친수(수학, 피보나치 수열) #2193은 수학적 원리를 알고 있으면 쉽게 풀 수 있습니다. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 이친수는 0으로 시작하지 않고, 1이 연속으로 나타나지 않는 수입니다. 이것과 관련해서 제가 쓴 글이 있습니다. https://sdev.tistory.com/319 동전을 n번 던졌을 때, 연속으로 앞면이 나타날 경우의 수는? 이런 경우의 수를 계산하는 것이 쉽지는 않습니다. 어떻게 생각을 해.. 2023. 4. 13.
[C/C++] 백준 #2188 축사 배정(이분 매핑) #2188 문제는 이분 매핑의 대표적인 문제입니다. 이분 매핑(binary mapping)이라는 것은 최대 유량 알고리즘(maximum flow algorithm)의 특별한 버전입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net 문제에서 축사를 소에 배정을 해주는데, 소들은 자신들이 원하는 축사들 중 하나를 배정받지 않으면 다른 축사에 들어가지 않으려 합니다. 이럴 경우 가능한 많은 소를 원하는 축사에 배정하는 알고리즘입니.. 2023. 4. 13.

티스토리툴바