본문 바로가기

알고리즘 문제풀이

 (31)
백준(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][..
프로그래머스 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은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다...
프로그래머스 Lv1. 완주하지 못한 선수(python) Lv1. 완주하지 못한 선수(파이썬)https://programmers.co.kr/learn/courses/30/lessons/42576문제 설명수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.제한사항마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.completion의 길이는 participant의 길이보다 1 작습니다.참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.참가자 ..

티스토리툴바