본문 바로가기

알고리즘

 (60)
2018 KAKAO 코딩테스트 추석 트래픽 https://programmers.co.kr/learn/courses/30/lessons/17676 = len(t_list): break if t_list[e][0] - t_list[s][0] >= 1000: break if t_list[e][1] == -1: cnt += 1 e += 1 if cnt > answer : answer = cnt if t_list[s][1] == 1: cnt -= 1 s += 1 return answer (다 풀고 다른 사람의 풀이를 봤는데, 1등 코드는 어려운 인덱스 처리를 간단한 트릭으로 편리하게 만들었다.) 지난번에 제출했던 코드이다. 코드를 보니 데이터의 크기가 2000으로 매우 작아 O(n^2) 알고리즘을 사용할 수 있다고 생각하여 각 time마다 비교하는 방식으..
2019 KAKAO 코딩테스트 길 찾기 게임 https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 세세한 조건을 따져가면서 그래프를 그리는 것은 구현상 힘들다고 판단했다. 그래서 다른 방법을 사용하였다. 첫째, 문제 조건에 따라 y값은 0~999 범위 내로 압축될 수 있다. 위 조건에 따라 좌표압축을 통해 y값을 변경해줬다. 이때, root(y값이 가장 큰 node)의 y 값은 0, 그다음 큰 값들은 1, ... 이런 식으로 변경하였다. 둘째, x 값 (nod..
2019 KAKAO 코딩테스트 후보키 https://programmers.co.kr/learn/courses/30/lessons/42890 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 후보키들을 찾는 문제이다. 입력의 크기가 크지 않아서(column
2019 KAKAO 코딩테스트 무지의 먹방 라이브 https://programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr Naive 하게 풀면 하나씩 음식을 먹어가면서 계산하면 된다. 하지만, 해당 방식으로는 효율성 문제에서 시간초과가 날 것이라고 생각했다. 내가 중요하게 생각했던 것은 "사라지는 음식"이었다. 1. 값이 작은 음식들부터 소진되고, 음식들은 자신보다 작은 음식들보다 늦게 소진된다. 2. 음식들이 전부 소진되는 시점은 회전판의 회전수가 "음식의 값"일 때다. 이를 고려하여 계산해본다면, i 번째 loop 에서 소모되는 음식 총량은 다음과 같다. 음식 값을 기준으로 정렬되있다고 한다면 $$ \sum_{n=0}^{i} (arr[n]-n) * ..
BOJ 11834 홀짝 https://www.acmicpc.net/problem/11834 11834번: 홀짝 홀짝 수열은 1,2,4,5,7,9,10,12,14,16,17로 시작하는 증가하는 자연수 수열이다. 홀짝 수열은 1개의 홀수, 2개의 짝수, 3개의 홀수 이런식으로 이어진다. 이 수열의 N번째 원소를 출력한다. www.acmicpc.net n번째 수가 몇번 째 그룹(몇번째 홀수 그룹, 몇번째 짝수 그룹)에 속하는지 구한다면 풀 수 있는 문제이다. 나는 다음과 같은 식을 세워서 풀었다 $$ \frac{i^2 + i}{2} = 2*a: x = b - 1 elif b*b + 3*b + 2 < 2*a: y = b + 1 else: x = b break x += 1 a..
BOJ 14391 종이조각 https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 완전탐색 문제이다. (r,c) 에서 오른쪽으로 한칸씩 늘리거나. 아래쪽으로 한칸씩 늘려 종이 조각의 숫자를 구하고, 이를 재귀적으로 완전탐색하여 풀면 된다. 내 코드는 다음과 같다. #include int n,m; int map[4][4]; int answer = 0; bool checked[4][4]; void dfs(int r, int c, int max){ if(c >= m){ c = 0;..
BOJ 2013 선그리기 www.acmicpc.net/problem/2013 2013번: 선그리기 첫째 줄에 선분의 개수 N(1second.size(); it->second.pop(); while(it->second.size()){ auto after = it->second.top(); if(max >= after.first && after.first >= min){ answer -= 1; if(min > after.second) min = after.second; } else{ max = after.first; min = after.second; } before = after; it->second.pop(); } } printf("%d\n", answer); return 0; } 소수 처리때문에 애를 먹었던 문제였다. 처음엔 ..
BOJ 14226 이모티콘 www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 해당 문제를 점화식으로 바꿀 수 있다. arr[ i*j ] = min ( arr[ i*j], arr[ i ] + j ) , j >=2

티스토리툴바