본문 바로가기

알고리즘/백준

 (68)
백준 2206 벽부수고 이동하기 - 이제는 3차원 visited 배열이 필요하다. c++ 문제링크 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net 해결 과정 컨셉이 비슷한 문제로 다음과 같은 문제가 있다. https://www.acmicpc.net/problem/..
백준 14500 테트로미노 - 모든게 다 dfs로 되는건 아니다 c++ 문제 링크 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 풀이 생각 및 아이디어 한 점에서 블록 3개(이미 있는 블록 한개 포함 4개) 가 뻗어나가는 모든 경우의 수를 구하는 것..
백준 14888 - 연산자 끼워넣기 - 백트래킹 (C++) https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net 학교를 개강하고 정말 오랜만에 시간이 나서 알고리즘 문제를 풀어 보았다. 쉬운 문제는 그래도 술술 푸는걸 보니, 아직 감이 완전히 죽진 않은것 같다 ㅎㅎ 오늘 풀어본 문제는 연산자 끼워넣기. 삼성 sw 역량테스트 문제이다. 남은 연산자의 개수가 0이 될때까지, 각각의 +-*/ 연산자를 쓸 수 있는 ..
백준 13460 구슬탈출2 - 구현 자체가 너무 까다로운 bfs문제 c++ https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 진짜 코드도 길고, 구현도 까다로운 문제다. 삼성 sw역량테스트 기출문제라길래, 평소에 풀어야지 풀어야지 하다가 오늘 날잡고 풀..
백준 2098 외판원 순회 - 비트마스킹,dp,dfs c++ 문제 링크 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 해설 및 회고 쉽지않은 문제였다. 전날 밤 12시에 자기전에 이 문제를 처음 보고 다음날 오늘 오후에 걸려서 다 풀었다. 종만북을 이제 첨 보기 시작했는데, 2권 첫장에 나온 내용이 비트마스킹 관련된 부분이었다. 외판원 문제에 비트마스킹을 적용해야 하는 이유 외판원 문제를..
백준 14226 이모티콘 - 2차원 배열로 상태저장 bfs - c++ 링크 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용 www.acmicpc.net 아이디어 오랜만에 bfs관련 풀어본 문제. 이문제는 주의해야 할점이, 클립보드에 복사한 이모티콘 갯수는 몇번이고 재사용이 가능하..
백준 16194 카드구매하기 2 - 쉬운 dp문제 c++ https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 우선 입력으로 받은 카드의 가격들을 arr에다가 담는다. 이것들이 기저 조건들이 된다. 그 다음엔 2개가 들어있는 카드팩부터, n개 들어있는 카드팩을 사는게 이득인지, n-k개 카드팩 + k개 카드팩 을 사는게 이득인지를 k = 1부터 n-1까지 돌려보면 쉽게 구할 수 있다. 최대 카드팩 장수가 1000이고, O(n^2)로 코드가 돌아가기 때문에 충분히 시간내에 풀 수 있다. 1 2 3 4 5 6 7..
백준 17779 - 게리맨더링2 - 시뮬레이션 (c++) 문제 링크 : https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다 www.acmicpc.net 2019 하반기 삼성 sw 역량테스트 기출문제였던 문제를 풀어보았다. 결국 문제는 중심이 되는 x,y좌표와 d1,..

티스토리툴바