본문 바로가기

전체 글

 (34)
백준(boj) 17825_주사위 윷놀이 (파이썬, c++) https://www.acmicpc.net/problem/17825풀이주사위 10개의 턴이 주어지는데, 이를 이용해서 최대 점수를 구하는 문제이다. 완전 탐색 하였다. 요점 1. 말 4개를 가지고 게임을 하는데, 2. 이미 말이 있는 곳은 갈 수 없다. 3. 각 칸에는 점수가 있고 4. 파란색 선이 있는 부분은 파란 방향으로, 그 외엔 빨간 방향으로 가야 한다. 해결책 1. horse 라는 리스트에 [방향, 인덱스]를 표현해서 해결 2. visit 리스트를 이용하여 해결 3. 판에 있는 점수들을 a리스트에 표현하여 해결(a리스트 방향에 따라 셋팅) 4. 방향(d 변수)이랑 인덱스(x 변수)로 빨간 방향 부분이면 거기로 향하게 함 a 리스트를 그림으로 표현하면 다음과 같다. python3from sys i..
백준(boj) 12100_2048 (파이썬, c++) https://www.acmicpc.net/problem/12100풀이상하좌우 4방향으로 이동을 할 수 있는데, 같은 값을 갖는 두 블록이 충돌하면 두 블록이 하나로 합친다. 단, 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐지지 않도록 한다. st=[] (스택의 역할을)라는 리스트와 idx(index의 역할을)라는 변수를 사용해서 구현했다. 비교하려는 idx값이 없으면 => 이전에 추가된 값이 없으므로 값만 추가해준다. idx는 그대로 둔다. 비교하려는 idx값이 있으면 => 이전에 추가된 값과 비교하고 idx를 1 올려준다. 만약 비교값이 같으면 합쳐지는 것이므로 두 배 해주고, 다르면 새로운 값을 추가해준다. 그렇게 최댓값을 구해야 하므로 완전 탐색 해준다. solve() 함수를 ..
백준(boj) 17822_원판 돌리기 (파이썬, c++) https://www.acmicpc.net/problem/17822풀이인접한 곳에 같은 숫자이면 지워주고, 같은 숫자가 없는 경우에는 숫자들을 평균이랑 비교하여 1을 더하거나 빼주는 문제이다.원판을 2차원 배열로 생각하면 크게 3가지 상황으로 나타낼 수 있다.1.가로로 인접한 경우2.세로로 인접한 경우3.가로로 인접하나 처음과 끝으로 떨어져 있는 경우(원판이라서 나타나는 특징) 인접한 곳에 같은 숫자가 있는 경우 visit배열에 표시해놓고 전부 살펴본 후에 체크되어 있는 숫자들을 지워주었다. (가로, 세로 둘 다 같은 숫자인 경우 먼저 지우면 원하는 값을 못 구하므로 다 돌리고 처리) 1, 2 번은 4방향 위치 배열을 만들고 이 배열을 이용해 탐색하면서 체크해 주었고, 3번은 나머지 연산을 이용하였다. ..
백준(boj) 15684_사다리 조작 (파이썬, c++) https://www.acmicpc.net/problem/15684풀이세로선과 가로선이 그려져 있는 사다리가 주어진다. 이 사다리에 선을 추가하여 출발지점과 도착지점이 모두 같아지게 하는 최소의 선 개수를 구하는 문제이다. solve() 함수를 가지고 완전 탐색 한다. 이때 출발지점과 도착지점이 모두 같은지는 check() 함수를 이용해서 검사해준다. python3(pypy로 제출)from sys import* input = stdin.readline def check(): for i in range(m): s = i #i가 시작 사다리 위치, s가 현재 사다리 위치 for j in range(n): if a[j][s]: s+=1 #사다리 표시되어있으면 오른쪽으로 elif s-1 >=0 and a[j][..
[자료구조] 스택(stack)_파이썬(python) 구현 [자료구조] 스택(stack)_파이썬(python) 구현스택이란?나중에 들어간 데이터가 먼저 나오는 후입선출(Last In First Out; LIFO)의 자료구조이다. 동전을 쌓고 뺄때는 무너지지 않게 위에서 부터 뺀다고 생각하면 쉽다. 일반적으로 저장소의 끝 부분(맨 위)을 탑(Top) 이라고 하고, 데이터를 추가하는 push 연산, 데이터를 꺼내는 pop 연산이 있다. ++함수의 호출도 스택을 기반으로 실행되므로 나중에 DFS(Depth First Search)를 구현할 때 따로 스택을 안쓰고 함수를 재귀적으로(recursion)만들어서 구현할 수 있다. 동작 과정스택이 동작하는 과정을 간단히 보면 다음과 같다.첫 번째 그림은 스택이 빈 상태이다.두 번째 그림은 5를 push한 그림이다. 세 번째 ..
프로그래머스 Lv1. K번째수(python) 프로그래머스 Lv1. K번째수(파이썬)https://programmers.co.kr/learn/courses/30/lessons/42748문제 설명배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.2에서 나온 배열의 3번째 숫자는 5입니다.배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배..
프로그래머스 Lv1. 모의고사(python) 프로그래머스 Lv1. 모의고사(파이썬)https://programmers.co.kr/learn/courses/30/lessons/42840문제 설명수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 ..
프로그래머스 Lv1. [2020카카오공채] 문자열 압축(python) 프로그래머스 Lv1. [2020카카오공채] 문자열 압축(파이썬)https://programmers.co.kr/learn/courses/30/lessons/60057문제 설명데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다...

티스토리툴바