본문 바로가기

Algorithm

 (175)
[이코테] 큰 수의 법칙 https://github.com/ndb796/python-for-coding-test/blob/master/3/2.py GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소 github.com 1. 해결방법 그리디 문제이다. 본인은 반복문으로 풀었지만 좀 더 효율적인 방법은 가장 큰 수와 두 번째로 큰 수밖에 사용하지 않는다는 부분을 파악해야한다. 가장 큰 수를 K번 ..
[BOJ] 17406. 배열 돌리기 4 https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 1. 해결방법 r, c, s에 대한 모든 경우의 수를 2차원 배열에서 회전을 시켜야 하기 때문에 파이썬의 permutations 라이브러리를 사용하였다. 기본적으로 시계방향으로 회전하는 것이기 때문에 상하좌우 모두 값을 이동해주는 코드를 4개의 for문으로 해결하였고, 안 쪽 리스트도 이동해야해서 4개의 for문 위에 바로 s 값이 -1씩 되도록 반복해주었다. 1사이..
[BOJ] 15684. 사다리 조작 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 1. 해결방법 백트래킹 문제인데 개인적으로 정말 어려웠다. 근데 굉장히 좋은 문제로 생각하는데, 그 이유는 2차원 배열을 자유자제로 조절할 수 있어야 사다리 로직을 구상할 수 있고 가지치기를 해서 연산 횟수를 엄청 줄일 수 있다. 아이디어는 유튜브 링크를 남김. 정말 설명을 잘해주신다. https://www.youtube.com/watch?v=s5hmaRJ5jN0 2. 정답코드 (1) 가지치기가..
[BOJ] 1062. 가르침 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 1. 해결방법 완전탐색 문제이다. 본인은 알파벳을 for문 돌려서 백트래킹을 진행하였다. 처음에는 문제 이해를 잘못해서 몇시간동안 헤맸다... 알파벳 체크 여부인 chk를 만들고, 모든 알파벳을 for문 돌려서 재귀를 호출하는 것이다. 주어진 문자열 하나하나를 따로 보는 것이 아니라, 가르치는 알파벳은 주어진 문자열 모두 공통적으로 적용되는 것이기에 max() 메서드를 사용해서 얼마나 문자..
[BOJ] 1038. 감소하는 수 https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 1. 해결방법 이 문제는 완전 탐색 백트래킹으로 해결한 문제이다. ( + 조합으로도 해결 ) 처음엔 ''문자열을 시작으로 0부터 9까지의 값을 문자열에 더하면서 answer 리스트에 append 하였다. 재귀를 통해서 계속해서 문자열을 추가시켜 sort() 정렬을 해주면 감소하는 수의 리스트가 만들어진다. 2. 정답코드 (1) 백트래킹 import sys input = sys.std..
[프로그래머스] Lv.2 줄 서는 방법 https://school.programmers.co.kr/learn/courses/30/lessons/12936 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 해결방법 이 문제를 해결하는데 거의 4시간? 정도 사용한 것 같다. dfs와 permutations도 효율성 문제에서 아웃돼버렸다.. 정답을 유추하는 데에는 10분채 안걸렸지만 효율성 테스트를 어떻게 해결할 것인가에 대해서 10분을 제외한 나머지 시간을 사용했다. 핵심 포인트는 math 라이브러리에서 factorial을 사용하는 것인데,,,, 어떻게 사용할 것인가가 가장 중요하다. n이 3,..
[프로그래머스] Lv.2 배달 https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 해결방법 이 문제는 어렵지 않은, 그냥 전형적인 다익스트라 기본 문제이다. 양방향으로 이동이 가능하기 때문에 maps[]에 append할 때, 양방향으로 append해주는 것이 포인트이다. 그리고 1번에서 다른 마을까지의 거리 dist[] 리스트를 이용해서 해당 마을까지의 거리의 값을 구하고, dist에 값을 갱신한다. 거리가 K이하인 개수를 answer에 넣어주면 된다. 2. 정답코드 im..
[프로그래머스] Lv.2 삼각 달팽이 https://school.programmers.co.kr/learn/courses/30/lessons/68645 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 해결방법 이 문제에 대한 아이디어가 40% 정도밖에 떠오르지 않아 결국 포기한 문제이다. 수학적으로 접근해서 아이디어를 생각해내 해결해야 하는 구현 문제이다. n = 4일 경우에는 [1, 2, 3, 4], [5, 6, 7], [8, 9], [10] 순서대로 배열에 값이 들어가는 것을 확인할 수 있다. 각 순서의 배열은 0 ~ 3 번째로 두고, 0번째의 배열에는 4개, 1번째는 3개... 이러..

티스토리툴바