나의 기록, 현진록

https://www.acmicpc.net/problem/11657  1. 문제이해한 도시에서 출발하여 다른 도시에 도착하는 버스가 있다.N개의 도시(노드), M개의 버스(간선)입력 형태는 A, B, CA는 시작 도시, B는 도착 도시, C는 버스를 타고 이동하는데 걸리는 시간C는 양수가 아닌 음수일 수도 있다.(타임머신)1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하자 - 요구 출력만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 -1 출력 (음의 사이클)1번 도시에서 출발해서 모든 나머지 도시마다 가장 빠른 시간을 출력하되 해당 도시로 가는 경로가 없다면 -1 출력 2. 접근방법가중치에 음수가 있으므로 밸만-포드 알고리즘 사용하기밸만-..

https://www.acmicpc.net/problem/17825  1. 문제이해시작 칸에 말 4개말은 화살표 방향대로만 이동 가능말이 파란색 칸에서 이동을 시작할 경우에는 파란색 화살표로만 이동 가능A 말이 주사위 값 만큼 이동해야 할 곳에 다른 말이 있다면 A 말은 이동 불가, 도착점일 경우엔 상관 없음말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가됨게임은 총 10개의 턴(10개의 주사위)만큼 이루어지고, 입력으로 주사위에서 나올 수 10개가 주어짐얻을 수 있는 점수의 최댓값을 구하라. 2. 접근방법입력으로 발판에 대한 입력이 주어지지 않아 발판에 대한 구조를 설계해야 함배열 형식에서의 최댓값을 구하라 = dfs, 완전탐색, 백트래킹어떠한 자료구조로 말이 이동하도록 할 것인가?중복된 점수가..

https://www.acmicpc.net/problem/2116 1. 문제이해마주 보는 면에 적힌 숫자의 합이 반드시 7이 되는 것이 아닌 주사위주사위를 아래에서부터 위로 쌓기주사위 쌓기 규칙은 다음과 같다서로 붙어 있는 주사위가 아래에 있는 주사위의 윗면 숫자와 위에 있는 주사위의 아랫면 숫자가 일치해야 한다.1번 주사위는 마음대로 놓을 수 있다.주사위의 윗면과 아랫면은 고정하고 회전 시킬 수 있다.주사위 쌓기 규칙을 준수하며 최종적으로 긴 사각 기둥이 되도록 주사위를 쌓았을 때 총 네 개의 옆면 중 어느 한면의 숫자의 합의 최댓값을 구하기 2. 접근방법숫자 배열 → 전개도 → 주사위 추상화마주 보는 면의 쌍 구하기[A, F] → [0, 5][B, D] → [1, 3][C, E] → [2, 4]주사위..

https://www.acmicpc.net/problem/17182  1. 문제이해행성 간 이동에 걸리는 시간이 2차원 행렬로 주어진다.planet[ i ][ j ]은 i 행성에서 j 행성까지 이동하는데 걸리는 시간이다.이미 방문한 행성도 다시 방문 가능출발은 K 행성부터 시작한다.모든 행성을 탐사하는데 걸리는 최소 시간 구하기2. 접근방법이미 방문한 행성도 다시 방문이 가능하기 때문에 A → B 보다 A → ? → B로 가는 경로가 더 가까울 수 있다.planet[i][j]는 i → j 로 직접 가는 시간이 아닌 i → j 로 갈 때 최소 시간이 저장되도록 플로이드 워셜 알고리즘 사용planet[i][j]에 각 행성마다 이동하는 최소 시간이 저장되어 있다면 이미 방문한 행성은 방문하지 않도록 dfs+백..

https://www.acmicpc.net/problem/7569  1. 문제이해M: 상자의 가로, N: 상자의 세로, H: 상자 갯수3차원 배열 형태의 토마토 상자익은 토마토 주변에 있는 토마토는 하루가 지나면 익은 토마토가 된다.주변의 범위는 토마토의 앞, 뒤, 좌, 우 그리고 위에 있는 상자와 아래에 있는 상자에 대한 토마토 총 6방향모든 토마토가 익기 위해서 며칠 걸리는지 구하기 2. 접근방법일반적인 BFS에서 윗 상자와 아랫 상자에 있는 토마토의 경우가 추가 됨예시)0 0 0 0 0        0 0 0 0 00 0 0 0 0        0 0 1 0 00 0 0 0 0  →   0 0 1 0 00 0 1 0 0         0 1 1 1 0 토마토는 3차원 배열이지만 2차원 배열 만들어서..

https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. 문제 이해한 심사대에서는 한명만 심사 가능가장 앞에서 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있다.더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사 받을 수 있다.모든 사람이 심사를 받는데 걸리는 최소 시간을 구하라.2. 설계입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하이분탐색이분탐색은 기준 값(mi..

1. 문제 이해(이긴게임 / 게임횟수) * 100 = 승률승률이 변하는 최소 게임 횟수를 구하라.앞으로 모든 게임에서 승리승률이 변한다 == 승률이 높아진다승률이 변하는 높아지는 최소 게임 횟수를 구하라.2. 설계X : 게임횟수Y : 이긴 게임( (이긴게임+N) / (게임횟수+N) ) * 100 = 승률 → ( (Y+N) / (X+N) ) * 100 = 승률조건1부터 10억까지 순서대로 연산은 시간 초과이분탐색으로 최소 게임 횟수 구하기3. 코드( (Y+N) / (X+N) ) * 100 밑줄 친 부분이 실수가 됨실수에서의 곱하기 연산 시 부동소수점 오류 발생수정 → ( (Y+N) * 100 ) / (X+N)예시) 0.99 * 100보단 9900/100가 안전0.9899999999…, 0.333333333..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 못 풀겠어서 풀이를 검색했고 이걸 왜 못 풀었나 싶어서 죄책감과 함께 오랜만에 글 씁니다. 문제 풀이 근무 태도와 동료 평가 점수 "모두" 다른 사원보다 낮을 경우 인센티브를 제외한다는 조건을 보고 어떤 방식으로든(이중 포문, 정렬 등) 탐색을 생각했다. 하지만 score에 길이가 최대 10만이기 때문에 O(N)으로 풀 수 있는 방법을 생각했는데 생각이 나질 않았다. 근무 태도와 동료 평가 점수 두 가지를 고려해야 하기 때문에 어려웠다. 정렬을 사용한다는 건 알았는데 말이지... 인센티브를 제외할 놈만 쉽게 ..

시간 초과 문제를 해결하기 위해 고민을 많이 했다. queue의 합을 구하기 위해 reduce나 반복문을 사용하면 queue의 길이만큼 연산하게 되니O(n), 처음 queue의 합을 구하고 합에서 요소만큼 더하기 빼기 연산으로 하면 O(1) queue를 쓰게 되면 removeFirst(), append() 연산 할 때마다 시간 복잡도가 증가함O(n) -> queue 두 개를 합쳐서 dequeue 사용O(1) import Foundation func solution(_ queue1:[Int], _ queue2:[Int]) -> Int { var result = 0 var sumQ1 = 0 var sumQ2 = 0 var dequeue = queue1 + queue2 var dequeuelen = deque..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 기사단원의 번호를 순회하기 위한 포문과 약수를 구하기 위한 포문 두 개의 이중 포문으로 구현하면 number가 최댓값인 100,000일 때 시간복잡도는 백만의 제곱이 되므로 시간초과이다. 메모라이징을 써야할지 고민했는데(아직 감이 없음...) 수학을 응용한 방법이 있었다. number가 10일 때의 약수는 1, 2, 5 10 number가 16일 때의 약수는 1, 2, 4, 8, 16 number가 20일 때의 약수는 1, 2, 5, 10, 20 ...... 무언가 1부터 number까지 포문이 순회하지..