본문 바로가기

프로그래밍

 (100)
[C++] 백준 2156번: 포도주 시식 문제 바로가기 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 개요 대표적인 다이내믹 프로그래밍 분류 문제이다. 문제를 푸는 방법은 점화식을 찾고 구현하는 것. N이 최소일 때부터 손으로 써가며 규칙을 찾는 것이 중요하다. 풀이 N이 1일 때부터의 경우를 차근차근 생각해보자 i번째 잔에 들어있는 포도주의 양을 W[i], i번째 잔까지 마실 수 있는 포도주의 최대값을 S[i]라고 하면 아래와 같이 나타낼 수 있다. N 잔을 선택하는 경우 식 1 ● W[0] 2 ● ● W[0] + W[1] 3 ● ● ○ S[i -..
[C++] 백준 2580번: 스도쿠 문제 바로가기 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 개요 백준에서 단계별로 풀어보기를 쭉 이어나가다가 이 문제를 맞닥트렸다. 무려 골드4의 난이도를 자랑한다. 의외로 첫 풀이는 간단했다. 그냥 규칙을 적용했더니, 예제는 그냥 풀려버렸다. 그냥 빈 칸 마다 들어갈 수 있는 후보 하나를 쭉 대입하는 방식이었다. 하지만, 당연하게도 그건 답이 아니었다. 풀이 이 문제는 백트랙킹으로 분류된 만큼, 빈 칸에 들어갈 수의 후보가 하나가 아닐 수도 있다. 그래서 재귀함수를 구현했다. 기존 코드에서 큰 변화는 없..
Visual Studio에 OpenGL 설치하기 이것 참 설치하기 어렵다. 그래픽 드라이버를 설치할 때 자동으로 설치된다고는 하지만 VS에서는 안 되는걸... ※ 나중에 알게 됐지만, 그래픽 드라이버를 설치할 때 자동으로 설치되는 파일은 OpenGL32.dll이다. glut32.dll이 아니다! 간략하게, 다음 파일들을 다운로드 하자. 1. freegult.zip 아래 링크에서 freeglut 3.0.0 MSVC Package 부분에 있는걸 다운로드 하자. https://www.transmissionzero.co.uk/software/freeglut-devel/ freeglut Windows Development Libraries Introduction Whilst at the University of Essex, I took a module call..
[C++] 백준 16236번: 아기 상어 문제 바로가기 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 NxN 크기의 공간에 물고기 M 마리와 아기 상어 1마리가 있다. 아기 상어의 처음 크기는 2이고, 1초에 한 칸씩 이동하며 물고기를 먹는 시간은 무시한다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있으며, 자기 크기만큼 물고기를 먹으면 크기가 1 커진다. 아기 상어의 이동방향 결정 방법은 아래와 같다. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. 먹을 수 있는 물고기가 1마리라면..
[C++] 백준 1107번: 리모컨 문제 바로가기 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 수빈이는 악력이 지나치게 쎈가보다. 리모컨을 다루다가 일부 숫자 버튼이 고장났다. - 숫자 버튼이 고장났다는 내용을 문제 다 풀고 글 쓰는 지금 알았다. +, -도 고려하는 줄 알고 assert까지 써가봐 확인했는데... 역시 문제를 몇 번은 꼼꼼히 읽는 버릇을 들여야겠다. 0~9번까지의 숫자, +, - 버튼이 있다. 수빈이는 N번 채널로 이동하고 싶다. 어떤 버튼이 고장났는지 주어질 때, 채널 N으로 이동하려면 최소 몇 번 ..
[C++] 백준 10026번: 적록색약 문제 바로가기 문제 크기가 N×N인 그리드의 각 칸에 RGB 중 하나를 칠한 그림이 있다. 같은 색으로 이루어져 있는 구역으로 몇 개 나뉘어져 있다. 같은 색상이 상하좌우로 인접해 있으면 같은 구역에 속한다. 적록색약인 사람은 R과 G를 구별하지 못 한다. 그리드가 주어졌을 때, 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역수를 세어보자. 조건 1 ≤ N ≤ 100 풀이 이 문제는 2667번의 응용버전이다. 그리드에서 RGB 문자가 있는 한 칸을 기준으로 너비우선탐색을 하는데, 한 번 방문한 칸에는 숫자 등을 채워 넣는다. 그리고 더 이상 RGB 문자가 등장하지 않을 때까지 이를 반복한 뒤, 몇 번을 반복했는지만 출력하면 그게 구역의 수이다. 이 문제에서는 이를 두 번..
[C++] 백준 15686번: 치킨 배달 문제 바로가기 ⛳문제⛳ 1. 크기가 N×N인 도시는 (r, c) 좌표에 1×1크기의 칸으로 구성돼 있고, r과 c는 1부터 시작한다. 2. 도시의 각 칸은 치킨집(2)과 빈칸(0), 집(1) 중 하나이며 각 숫자로 주어진다. 3. 치킨 거리란 어떤 집과 그 집에서 가장 가까운 치킨집 사이의 거리이며 거리는 각 좌표의 차이(절댓값) 합이다. 4. 도시의 치킨 거리는 도시 내 모든 집 각각의 치킨거리 합이다. 5. 도시의 치킨 집 중 M개 점포를 남기고 나머지는 폐업시키고자 한다. 6. 치킨집 중에서 최대 M개를 골라 도시의 치킨 거리가 최소가 됐을 때, 도시의 치킨 거리를 구해보자. 🧨입력조건🧨 2 ≤ N ≤ 50 1 ≤ M ≤ 13 ✨풀이✨ 1. 좌표 순서대로 입력을 받는다. 2. 입력된 수가 1 또는 ..
[C++] 백준 7569번: 토마토 문제 바로가기 🎊문제 개관🎊 이전에 풀었던 7576번과 유사하다. 하지만 그 때보다 한 차원 증가했다. 나는 오른쪽과 같은 좌표계를 사용할 것이다. // Vector3(h, r, c) typedef tuple Vector3; 🧨입력 조건🧨 2 ≤ N, M, H ≤ 100 🎢풀이🎢 📖 이전에 풀었던 7576번의 풀이를 많이 참고했다. 1. 토마토의 상태를 보여주는 3차원 배열 tomatos, 오늘 익은 토마토의 위치를 저장하는 큐 today, 내일 익을 토마토의 위치를 저장하는 큐 tomorrow가 있다. 2. 오늘 익은 토마토의 위치를 모두 한 번씩 방문하며 다음(3~5)을 반복한다. 3. 인접한 토마토(neighbor)가 아직 안 익었다면, 내일 익을 토마토에 위치를 저장해둔다. 4. 그 토마토의 상태..

티스토리툴바