[BOJ]1463. 1로 만들기 # DP # 메모이제이션 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제요약 정수 N에 대해 '2로 나누거나, 3으로 나누거나, 1을 빼거나' 셋 중 하나의 연산을 반복해서 실행할 수 있다. 결과적으로 1을 만들고자 하는데, 최소 연산 횟수를 구해야 한다. 과정 - 십여분 고민 -> 구글링으로 답 확인 후 풀이 - 못 푼 이유 : dp 접근법을 못떠올림 - 기본적인 dp 방법으로 풀고, 제출 현황에서 python 시간을 살펴봤는데, 시간 차이가 꽤나는 답을 발견해서 추가적으로 재귀와 메모제이션에 대해 공부했다. >> 풀이1 (메모리:39504KB / 실행시간: 588ms / 결과: PASS) ''' 1. 연산 횟수 저장할 dp 테이블 만들기... [백준] 7682. 틱택토 - python 7682번: 틱택토 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입 www.acmicpc.net >> 요구사항 틱택토 게임의 최종 상태가 될 수 있는지 판별하는 프로그램 - x가 시작하고, 그 다음으로 o가 놓는다. - xxx 혹은 ooo가 발생하면 게임은 끝난다. - 혹은 어느 줄도 빙고가 나오지 않은 상태로 게임판이 다 차도 게임은 끝난다. >> 아이디어 아래의 세 케이스 중 하나에 속하면 valid(최종상태로서 성립 가능), 그렇지 못하면 invalid(불가능)한 것으로 판단. 1. x와 o 의 개수가 같으면서 / o 빙고줄은 존재하고,.. [SWEA] 격자판의 숫자 이어붙이기 #파이썬 #DFS https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제요약 임의의 위치에서 시작해서 6번의 이동(인접 영역, 즉 상하좌우)을 하면서 숫자를 이어붙이면 7자리 숫자가 된다. 나올 수 있는 숫자 종류(개수)를 출력하는 프로그램을 작성 아이디어 1. 모든 좌표를 순회한다. 2. 매좌표마다 깊이우선 탐색(깊이는 6으로)으로 숫자를 생성해 리스트에 담는다. 2-1. 이 때, 이미 들어가 있는 숫자는 리스트에 담지 않고 pass. 3. 마지막에 리스트에 담긴.. [Algo] 입력줄 개수를 모를 때 알고리즘 문제 풀다가 어렵지는 않은 문제인데, 입력줄이 몇 줄이 주어지는 지에 대한 정보를 안주는 문제를 만났다. (백준 11718 그대로 출력하기) 인풋이 몇 개일지 모르는 상황에 주어지는 인풋마다 아웃풋을 출력하라는데 어떻게 해야하지? 일단 이것저것 찍어보다가 이렇게 냈는데, 통과하긴 했지만 몇 가지 의문이 생겼던 게 있어서 정리. import sys a = sys.stdin.readlines() for i in a: print(i.rstrip()) 입력을 통으로 읽어와서 반복문을 통해 하나씩 출력했다. Q. strip()은 정확히 어떤 함수? strip() 함수는 문자열에 사용하는 함수로, 시작과 끝의 공백을 제거해준다. 만약 괄호 안에 문자 매개변수를 넣으면, 시작과 끝에 해당 문자가 있다면 그 .. [백준]2178. 미로탐색 - python https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net - 최단 경로를 찾는거니까 bfs 로 탐색 - 거리를 답으로 출력해야 하므로, 다음 이동할 칸을 찾아 큐에 담을 때 지금까지 온 거리에 +1을 한다 - 방문 표시를 위한 배열을 따로 만들어두고 방문하는 곳은 표시 - 방문한 적 없고 해당 좌표의 숫자가 1이면 (방문표시 하고 그 때까지의 거리를 기록하고, 큐에 담는다) - 방문한 적 없고 해당 좌표가 N,M(배열 상으로는 N-1,M-1)이면 그 때까지의 거리를 기록하고, 그 값이.. [SWEA]12712.파리퇴치3 - 파이썬 https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AXuARWAqDkQDFARa SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com - 델타 접근 연습하려고 푼 문제 - 처음에 더하기 모양 분사와 곱하기 모양 분사를 나눠서 함수를 만들어줬는데, 합쳐서 할 수 있다는 걸 알게되서 두번째 풀 때는 8방향 델타를 돌면서 같이 구했다. - 주의할 점이 있다면 주어진 세기만큼 반복해서 델타를 돌면서 더해줘야 하는데 초기화 값을 0이 아닌 해당 좌표에 쓰여진 파리수로 설정해야하고, 1부터 주어진세기-1까지만 반복해줘야한다. .. [BOJ] 2667. 단지번호붙이기 - 파이썬 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 아이디어 1. 1이 있는곳(집)을 만나면 dfs나 bfs로 인접한 모든 곳을 탐색해서 끝까지 간다. 2. 끝까지 가면 단지 하나를 정복한 것한 것이고, 탐색 때마다 카운트를 올려준다. - 인접한 곳은 델타 탐색을 이용. - 탐색한 곳은 나중에 중복해서 탐색하면 안되기 때문에 값을 0으로 바꾼다. - 한 단지에 집이 몇개인지도 알아야하기 때문에 탐색을 시작할때 home_cnt변수를 만들어두고, 이동할.. [BOJ] 7682. 틱택토 (실패) https://www.acmicpc.net/problem/7682 7682번: 틱택토 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입 www.acmicpc.net - 장렬히 실패 - 기준을 정확히 안세우고 이것저것 조건을 추가했던게 문제였던 것 같다. - 스터디때 공부하고 다음에 다시 도전해볼 예정 풀이과정 [BOJ] 1012. 유기농배추 - 파이썬 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 아이디어 1. 인접한 곳(상하좌우)면 한 곳으로 치니까 출발점을 만나면 끝까지 탐색해 1을 카운트해주면 한 곳을 셀 수 있다. 2. 이미 카운트한 곳은 중복으로 탐색하면 안되므로 탐색할때 방문 표시를 해둬야한다. - 끝까지 탐색하면 되는 문제이므로 bfs,dfs 든 관계없다. 나는 bfs를 이용했다. - 0과1로 된 배열을 읽어와 풀어도 되는데, 나는 그냥 좌표만 읽어와서, 특정 좌표가 좌표 리스트(cabba.. [SWEA] 1238. contact - 파이썬 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com - 인접한 노드로 뻗어나가는 구조이므로, 너비우선 탐색(bfs)를 이용한다 - 사람이 최대 100명까지 있다고 해서, 사람번호를 인덱스로 하고, 그 사람이 연락을 받았을 때의 시작사람과의 거리가 얼마인지를 저장해두는 리스트를 만들고 시작했다.(contacted 변수에 할당. 거리를 저장해두는 용도와 이미 연락했는지 확인하는 두가지 용도로 사용) - 가장 마지막에 연락을 받는 사람이 여러명일 수 있으.. 이전 1 다음
