본문 바로가기

알고리즘 삽질장

 (228)
[BOJ] 9093번 - 단어 뒤집기 문제설명 https://www.acmicpc.net/problem/9093 9093번: 단어 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 www.acmicpc.net 사고과정 주어진 문장을 띄어쓰기 단위로 문자열을 입력받은 뒤 iterable한 객체에 인덱싱 [::-1]을 붙여주면 거꾸로 되는 것을 활용했음! 그리고 다시 join 문법을 통해 이어 붙이기 풀이 for tc in range(int(input())): sentence = input().split() result = [] for s in sentence: result.append(s..
[BOJ] 10828번 - 스택 문제설명 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 사고과정 입력을 받을 때마다 출력시켜야 하므로 for loop 안에서 바로 출력하도록 했다. 그냥 input()을 사용하면 시간 초과 에러가 발생한다. 주어지 시간 범위도 0.5초 밖에 안된다.. 그래서 sys 라이브러리를 사용했다 나머지는 문제에서 설명해준 대로 구현하면 된다. 다시 기초부터 시작..! 풀이 import sys input = sys.stdin.readl..
[이코테] BFS - 블록 이동하기 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 하단의 링크를 참조하자. https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 사고과정 로봇 좌표를 하나의 노드, 로봇의 좌표들 간의 비용을 이동하는 데 걸리는 시간(1)으로 간선으로 하여 모든 간선의 비용이 동일할 때 최솟값을 찾는 전형적인 BFS 문제라고 한다. 매우 어려웠..
[이코테] DFS/BFS - 인구 이동 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 하단의 링크를 참조하자. https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 사고과정 주어진 N by N 정보를 어떻게 그래프 데이터로 만들지?에 대해서 사고가 멈추었다. 인접행렬? 인접리스트? 방식을 생각했으나 도통 답이 안나왔다. 결국 포기하고 답을 보았다. 풀이..
[이코테] 구현 - 외벽 점검 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 하단의 링크를 참조하자. https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하 programmers.co.kr 사고과정 완전탐색이라는 것을 눈치를 채긴했다.. 주어진 데이터 범위가 워낙 작아서 말이다.. 그런데 문제는 원형으로 된 정보를 어떻게 하느냐에서 감이 오지 않아 포기했다..
[이코테] 그래프 알고리즘 - 최종 순위 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 하단의 링크를 참조하자. https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 사고과정 문제에서 키워드를 잘 추출해내지 못했다.. 문제에서 캐치해야 할 것은 "작년 순위가 주어졌을 때, 이에 맞게 전체 팀들의 순위를 나열"하라는 것에서 노드의 선후관계를 고려한 위상정렬 알고리..
[이코테] 다이나믹 프로그래밍 - 편집 거리 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 두 개의 문자열 A, B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 한다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있다. 삽입 : 특정한 위치에 하나의 문자를 삽입한다. 삭제 : 특정한 위치에 있는 하나의 문자를 삭제한다. 교체 : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체한다. 이 때, 편집 거리란, 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미한다. 문자열 A를 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성해라. 예를 들어, sun..
[이코테] DFS/BFS - 감시 피하기 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 하단의 링크를 참조하자. https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 사고과정 저번에 풀어본 DFS로 완전탐색을 구하는 연구소 문제와 비슷한 유형인 것 같았다. 주어진 데이터 범위도 적고 완전탐색으로 해결할 것이라는 것은 잘 예상했다. 그래서 연구소 문제처럼 DFS..
[이코테] 다이나믹 프로그래밍 - 못생긴 수 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 못생긴 수란 오직 2, 3, 5 만을 소인수로 가지는 수를 의미한다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미한다. 1은 못생긴 수라고 가정한다. 따라서 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... } 순으로 이어지게 된다. 이 때, n번째 못생긴 수를 찾는 프로그램을 작성해라. 예를 들어 11번째 못생긴 수는 10이다. 입력조건 첫째 줄에 n이 입력된다.(1
[이코테] 구현 - 치킨 배달 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 하단의 링크를 참조하자. https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 사고과정 구현에서 문제가 길어지면 요구사항을 놓치는 경우가 빈번한 것 같다.. 주어진 데이터 범위가 크지 않다고 생각해서 완전 탐색인 것 같다고 생각했다. 그런데 문제에서 요구하는 도..
[이코테] 그래프 알고리즘 - 행성 터널 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 하단의 링크를 참조하자. https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 사고과정 최소 신장 트리를 만드는 크루스칼 알고리즘을 활용하는 거라고 생각했다. 그런데 문제에서 간선 비용을 계산하는 문제가 또 있었는데 그것을 해결하지 못했다..심지어 책..
[이코테] 최단 경로 - 숨바꼭질 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있다. 동빈이는 1 ~ N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발한다. 전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결한다. 또한 전체 맵은 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어진다. 동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있다. 이 때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미한다. 동빈이가 숨을 헛간의 ..
[이코테] 다이나믹 프로그래밍 - 병사 배치하기 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 하단의 링크를 참조하자. https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 사고과정 DP의 전형적인 '뒤의 입장에서'를 생각하고 풀어보려 했지만 구현은 했지만 다른 테스트 케이스를 통과하지 못했다.. 도저히 모르겠어서 풀이를 보았고 가장 긴 증가하는 부분 수열 길이를 ..
[이코테] DFS/BFS - 연산자 끼워 넣기 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 하단의 링크를 참조하자. https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 사고과정 DFS인지 BFS인지 명확히 판단하기가 어려웠다.. 완전 탐색 문제인 것 같기도 해서 순열을 구하려 했으나 풀지 못함. 또 그래프 데이터로 ..
[이코테] 구현 - 기둥과 보 설치 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 하단의 링크를 참조하자. https://programmers.co.kr/learn/courses/30/lessons/60061 코딩테스트 연습 - 기둥과 보 설치 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1]..
[이코테] 그래프 알고리즘 - 어두운 길 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 한 마을은 N개의 집과 M개의 도로로 구성되어 있다. 각 집은 0~N-1번까지의 번호로 구분된다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일하다. 예를 들어, 2번과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 가정하자. 하루 동안 이 가로등을 켜기 위한 비용은 7이 된다. 정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 한다. 결과적으로 일부 가로등을 비활성하여 최대한 많은 금..
[이코테] 최단 경로 - 화성 탐사 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 당신은 화성 탐사 기계를 개발하는 프로그래머이다. 그런데 화성은 에너지 공급원을 찾기가 힘들다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 한다. 화성 탐사 기계가 존재하는 공간은 N X N 크기의 2차원 공간이며, 각각의 칸 을 지나기 위한 비용(에너지 소모량)이 존재합니다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N-1][N-1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성해라. 화성 탐사 기계는 특정한 위치에서..
[이코테] 다이나믹 프로그래밍 - 퇴사 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 하단의 링크를 참조하자. https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 사고과정 DP는 "뒤 입장에서 생각" 해야한다는 관점으로 문제를 풀어보려 했지만 풀지 못했다. 대체 어떻게 점화식을 세워야 하는지 닿을락말락...하지만 닿지 않았음^^ 풀이를 보니 DP 테이블에는 i일부터 마지막 날(N일)까지 얻을 수 있는 최대 금액을 기록하는 것이었음. i일에 상담을 하는데 걸리는 시간 time이 가변적인데 이를 어떻게 해..
[이코테] 이진 탐색 - 가사 검색 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 하단의 링크를 참조하자. https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 사고과정 무엇을 이진탐색하는가?에 대해서, 쿼리로 주어지는 문자열 중 ?로 시작하거나 끝나는 인덱스를 찾는 것인지 했다. 그러나 아니었고 ?의 원소 개수를 이진 탐색으로 세는 것인가 했지만 아니었다.. 풀이를 보니 이진 탐색으로 원소 개수를 세는 함수를 사용하는 것이었음. 하지만 이 때, 어떤 원소 개수를 세는지에 대해 접근법이 잘못되었음. 필자는 쿼..
[이코테] DFS/BFS - 괄호 변환 해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 문제설명 하단의 링크를 참조하자. https://programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 사고과정 문제를 이해하는게 너무 어려웠다. 그래서 프로그래머스 질문 사이트에서 보니 나만 그런게 아니라 다른 분들의 질문 답변을 통해서 문제를 이해했다. 그리고 재귀함수를..

티스토리툴바