whiporithm

문제 https://school.programmers.co.kr/learn/courses/30/lessons/77886 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 해당 문제는 "110" 을 찾아서, 어떻게 옮길지가 관건인 문제다. 우선 "사전순으로 앞서는" 숫자의 개념을 생각해보자. 10과 01이 있을경우 사전순으로 앞서는 숫자는 01이다. 10은 10진수로 2이고, 01은 1이다. 이 말은 2진수로 나타낸 숫자를 10진수로 바꾸었을때, 작은 숫자가 사전순으로 앞선다는 뜻이다. 동시에 2진수는 왼쪽일수록 가중치가 높아지기 때문에 작은 숫자를 만들..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 딕셔너리를 활용하여 풀었다. 첫째로 자신을 추천해준 사람을 저장해주는 recommender 두번째로 판매원들마다 수익을 저장할 income 이다. enroll과 referral 을 활용하여 recommender 를 key는 추천받은 사람, value는 추천해준 사람으로 초기화 하고, 이 때 income도 판매원마다 0으로 초기화 해준다. 이후에 수익을 계산해준다. 우선 10프로가 1원 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/68646 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 작은 값은 '한번만' 터트릴 수 있는게 문제의 요점이다. 내가 선택한 풍선이 살아남기 위해서, 내가 가장 작은값이 아니라면 언젠가 가장 작은값을 터트려야한다. 결국 작은값을 터트리는 선택지는 가장 작은 풍선을 만났을때만 사용할 수 있는 것이다. (가장 작은 값을 가진 풍선은 무조건 살아남을 수 있다.) 만약 내가 가장 작은값 왼쪽에 존재한다고 해보자, 내 오른쪽은 가장 작은 값의 풍선이..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/49993?language=python3# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 tech라는 딕셔너리를 선언했고, 키는 스킬이고 밸류는 그 스킬을 배우기 위한 직전 스킬을 넣어주었다. 따라서 만약 A스킬이 skill에 있고, 그 스킬을 배우기 위해서 무엇을 배워야하는지 tech를 통해 알 수 있다. (1부터 넣은 이유는 첫 스킬은 선행스킬이 없기 때문에) 이후 skill_trees 를 순회한다. 한 스킬셋마다 가능한지 여부를 따져주기..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/49994 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이동한 길만 체크하는 문제이다. 이렇게 저렇게 삽질좀 해보다가, 두 지점의 좌표를 set에 넣고 검사해보면 되겠다 싶었다. (1, 0) => (1, 1) 이라면 set에 (1, 0, 1, 1)과 같이 넣는다. 단, (1, 1) => (1, 0) 도 같은 경로를 사용하기에 여기에 대한 검사를 해줘야한다. 따라서 (1, 0) => (1, 1) 을 갈때 (1, 0, 1, 1) 과 (1, 1,..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/87390?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 만약 n*n배열을 모두 만들어서 값을 추출하려하면 메모리 초과 + 시간초과가 걸릴것이다. (n은 최대 1000만인데, n*n은 답도 없다.) 따라서 문제의 핵심은 left부터 right 값만 구하는 것이다. right - left는 최대 10만으로 명시되어 있기에 시간이나 메모리에 걸릴일이 없다. 2차원적으로 생각해서 시작하는 행과, 끝나는 행을 구할필요가..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17683# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 (해당 풀이는 처음 풀었을때의 풀이고, 뒤에 훨씬 간단한 개선 풀이 코드가 있음) 문자열로 들어온 시간을 파싱해서 노래의 재생시간(runningTime)을 구했다. 처음에는 단순히 int로 바꾼다음 끝나는 시간에서 시작시간을 빼면 될거라 생각했으나 "13:50 ~ 14:10" 처럼 끝나는 시간의 '분' 이 더 앞설때 처리하기가 까다로워 datetime 을 활용하여 처리했다. compl..

문제 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 풀이 python3으로는 시간초과가 나서 pypy3으로 제출했다. 우선 구름의 위치를 저장하는 배열을 선언하고, 각 구름의 이동을 수행한다. 배열의 범위를 초과하면 순환되는 구조이기에 그 부분부터 구현하면 된다. '마법사 상어와 파이어볼' 에서 처리한것과 똑같이 처리해주면 된다. (아래 참고) 파이어 볼 이동 2차원 배열을 돌면서 한개라도 파이어볼이 있다면 현재위치 + 방향 * 속도 ..

문제 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 풀이 요구사항과 조건이 굉장히 많은 구현 문제다. 풀이를 하다보면 놓치는 부분이 많을것이라고 생각하여서 우선 요구사항을 내가 이해하기 편하도록 작성했고, 그에 따른 슈도코드나 솔루션도 생각나는대로 작성했다. 해당 문제의 큰 흐름을 확인해보자. 존재하는 블록그룹을 확인한다. 우선 탐색은 bfs로 가정한다. 블록그룹은 우선 무지개블록, 검은블록이 아닌 일반블록이 하나는 있어야한다. 또한 기준..

문제 https://www.acmicpc.net/submit/20058/63063274 로그인 www.acmicpc.net 풀이 해당 문제는 각 격자를 l의 값에 따라 잘 나누고, 접근해서 로직만 잘 수행하면 풀 수 있는 문제이다. 그 외에 배열 회전, 얼음 감소, 가장 큰 대륙 찾기등 부가적인 요소는 간단하게 해결할 수 있다. 예시를 보자. n이 8, l이 1일때는 64 / 4 => 16개의 격자가 생긴다. n이 8, l이 2일때는 64 / 16 => 4개의 격자가 생긴다. 이 값은 (2^n)^2 / (l^2)^2 라는 공식으로 얻을 수 있다. 이후에는 각 격자에 접근한다음에, 배열을 회전해줘야한다. 위와 같이 4군데에 접근해야하고 각 격자에 해당하는 부분만 탐색해야한다. 처음에 x, y는 0으로 시작..