본문 바로가기
반응형

알고리즘 풀이164

[백준 14468] 소가 길을 건너간 이유 2 (python) https://www.acmicpc.net/problem/14468 14468번: 소가 길을 건너간 이유 2 존의 농장에는 원형 목초지가 있고, 그 둘레에 길이 둘러져 있다. 존의 소는 매일 아침 이 길을 건너가 풀을 먹고 저녁에 다시 길을 건너가 헛간으로 돌아간다. 이 소들은 자신의 습관대로 매일 www.acmicpc.net 소가 길을 건너간 이유 2 소가 길을 지날 때 경로상 겹치게 되는 위치를 찾는 문제 ※ 그림으로 보는 문제 이해 검은색 화살표 처럼 겹치게 되는 경우를 찾으라는 뜻 📌 문제 접근 포인트 1. 총 52개의 알파벳 쌍이 2개씩 나오고, 위 그림처럼 겹치는 부분을 찾아야 한다. 2. 선택한 알파벳부터, 다음 알파벳이 나올 때까지 탐색해 주자. 그리고 그 안에 있는 내용물 중에서 알파벳이.. 2023. 4. 27.
[백준 14667] 소가 길을 건너간 이유 1 (python) https://www.acmicpc.net/problem/14467 14467번: 소가 길을 건너간 이유 1 3번 소는 위치 1, 0, 1에서 관찰되었으므로 길을 최소 두 번 건넜음을 확인할 수 있다. 4번 소도 길을 한 번 건넜으며, 나머지 소는 길을 건넌 기록이 확인되지 않는다. www.acmicpc.net 소가 길을 건너간 이유 1 2개의 목초지가 있을 때 총 10마리의 소가 서로 다른 목초지로 이동하는 횟수를 구하는 문제 단순 구현 문제 📌 문제 접근 포인트 1. 소가 이동하는 것에 대해 나타내줄 리스트를 만들어주자. 2. 최초에 소가 자리에 없으면 해당 위치에 소를 넣어주자. 3. 다음에 같은 소가 선택됐는데 목초지의 위치가 다르다면 소를 그 목초지로 이동시키고, 횟수를 세어주도록 만들어주면 구.. 2023. 4. 27.
[백준 15685] 드래곤 커브(python) https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 드래곤 커브 문제 n-1 세대 드래곤 커브의 끝점을 기준으로 90도 시계 방향 회전하여 끝점에 붙여나가 n세대 드래곤 커브를 만들 때, 주어진 시작점과 방향을 고려하여 원하는 세대까지 만들었을 때, 1x1 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 구하는 문제 방법을 찾아 구현하는 문제였다. 📌 문제 접근 포인트 1. 예제를 기준으로 규칙성을 찾기 위.. 2023. 4. 25.
[백준 13909] 창문 닫기 (python) https://www.acmicpc.net/problem/13909 13909번: 창문 닫기 서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 2번째 사람은 2의 배수 번째 www.acmicpc.net 창문 닫기 문제 N 개의 창문이 있을 때, 1부터 시작해서 해당 수의 배수만큼 닫혀있으면(0) 열고(1), 열려있으면(1) 닫고(0)를 반복하고, 최종적으로 열려있는 창문의 개수를 확인하는 문제 수학적 접근으로 해결할 수 있었다. 📌 문제 접근 포인트 1. 조건을 몇 개 직접 구현해 보자. 주어진 숫자 N이 21억이란 숫자이므로, 단순 반복으론 해결할 수 없다. 2. 그렇다면 직접 경우의.. 2023. 4. 25.
[백준 13140] Hello World! (python) https://www.acmicpc.net/problem/13140 13140번: Hello World! N이 주어질 때 hello + world = N을 만족하는 서로 다른 한 자리 자연수(0 포함) d, e, h, l, o, r, w를 구해서 아래 그림과 같은 형태로 출력하는 프로그램을 작성하여라. 단, h와 w는 0이 될 수 없다. www.acmicpc.net Hellow World 문제 숫자 값 N을 입력받고 h, e, l, o, w, r, d에 각각 0~9까지 숫자를 할당했을 때 hello+world = N이 되는 것을 찾는 문제 완전 탐색을 통해서 해결할 수 있었다. 📌 문제 접근 포인트 1. 각각의 h, e, l, o, w, r, d에 숫자를 넣어서 비교할 방법을 찾아보자. 2. 주어진 숫자.. 2023. 4. 25.
[백준 17103] 골드바흐 파티션 (python) https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 골드바흐 파티션 문제 짝수 N이 주어졌을 때 두 소수의 합으로 나타낼 수 있는 경우의 개수를 세는 문제 에라토스테네스의 체를 이용해서 해결 할 수 있었다. 📌문제 접근 포인트 1. 테스트케이스만큼 반복해서 숫자를 탐색해야 하므로, 미리 소수의 리스트를 만들어서 찾는 게 시간을 줄일 수 있다. 2. 에라토스테네스의 체를 이용해서 소수 리스트를 만들어주고 탐색을 해보자. 3. 숫자를 찾을 때, 두 소수.. 2023. 4. 23.
반응형

티스토리툴바