티스토리

시나위

검색하기

블로그 홈

시나위

sinawi.tistory.com/m

하고 싶은 거 다하고 정리하는 블로그

구독자: 6

방명록 방문하기

주요 글 목록

[Leetcode] 2353 Design a Food Rating System, C++ 문제 요약 Food Rating System을 만들면 됨 접근 1. 구현 초기화 모든 값을 저장함 -> 새로운 값이 들어올때마다 추가함. cuisines[i]에 어떤 값이 들어있는지 모르므로 새로운 값이 들어올때마다 저장해야함.(unordered_map) cuisines[i] 마다 foods[i]와 ratings[i] 를 우선순위를 주어 저장해야함. (priority_queue) -> 점수가 같으면 사전순으로 작은 이름이 우선임 changeRating 새로운 값으로 바꿈 priority_queue를 사용하므로 값을 제거하기 어려우므로 추가만하는 방향으로 진행 highestRated priority_queue를 사용하면 제일 위에 있는 값을 출력하면 됨. changeRating에서 값을 제거하지 않고 추가.. 공감수 0 댓글수 0 2022. 10. 13.
[백준] 1922 네트워크 연결, C++ 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제 요약 모든 컴퓨터를 연결하는데 필요한 최소 비용을 출력한다. 접근 1. BFS 최소 비용이면 BFS라고 생각할수 있겠지만 시작점에서 특정 지점까지의 최소 거리이므로 조건과 맞지않다. (몇몇 조건은 만족할수 있다.) 2. MST(Minimum Spanning Tree) 최소신장트리 사용된 간선들의 가중치 합이 최소인 트리이다. 신장트리를 만들때 최소의 간선을 사용해서 모든 노드를 방문해야 하고, 사이클을 만들지 않아야한다. Kruskal 낮은 비용의 간선부터 차례로 선택함 사이클이 생기는 간선은 제거함(cycle이 만들어지는지 확인 필요, ex. .. 공감수 0 댓글수 0 2022. 10. 13.
[프로그래머스] 가장 먼 노드, C++ 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 1번 노드에서 가장 멀리 떨어진 노드 찾기 접근 1. 그래프 탐색 BFS로 탐색하면 1에서부터 각 노드마다의 거리가 나온다. 가장 마지막 구해진 거리(가장 먼 거리)와 같은 개수를 구하면 된다. max_dist = max(max_dist, visit[adj]); 모든 노드를 탐색할때 가장 큰 값을 저장해놓고 int ret = 0; for (auto v:visit) { if (v == max_dist) ret++; } return ret; 해당 값을 사용해서 같은 거리인 노드의 개수를 센다. 전체 코.. 공감수 2 댓글수 0 2022. 10. 13.
[백준]17070 파이프 옮기기 1, C++ 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 요약 두칸짜리 파이프를 옮겨 (N,N) 위치까지 옮기는 방법의 개수 구하기 파이프는 세가지 방향으로만 움직일수 있음 접근 및 알고리즘 1. 메모리 제한이 512MB인거보면 DP다. 세가지 방향으로 움직일수 있는지 확인 (checkMove) Top Down 방식으로 해당 위치에 값이 있으면 값 리턴, 끝에 도착하면 1을 저장하고 리턴 전체 코드 #include #include #include using namespace std; #de.. 공감수 2 댓글수 0 2022. 10. 12.
[백준] 1167 트리의 지름, C++ 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 요약 트리의 지름 출력 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것 접근 1. 생각의 흐름 그래프 탐색 두번으로 진행하면 될 것 같다. 아무 점에서 시작해서 가장 먼 지점까지 탐색한다. 첫번째 탐색이 끝나면 가장 먼지점에서 두번째 탐색을 시작한다. // 1. 아무 노드에서 시작해서 가장 먼노드까지 간 다음, pair tmp; tmp = bfs({1, 0}); // 2. 가장 먼노드 노드에서 가장 먼노드까지 탐색 tmp = bfs({t.. 공감수 1 댓글수 0 2022. 10. 12.
[백준] 1043 거짓말, C++ 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 요약 진실을 모르는 파티의 최대 개수 출력 접근 1. union find union find로 풀어야될거같았다. 입력받을 때 같은 파티에 있는 사람들끼리 union 시킨다. for (size_t i = 1; i > length; party[i][0] = length; for (size_t j = 1; j > party[i][j]; if (j == 1) contin.. 공감수 0 댓글수 0 2022. 10. 12.
[백준] 2812 크게 만들기, C++ 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 요약 주어진 길이 N의 숫자에서 K개를 제거해서 가장 큰 수를 만들어야함 접근 1. 앞에 있을수록 9에 가까워야하고 뒤에 있을수록 0에 가까워야한다고 생각이 들었다. 하지만 K가 작으면 만들기기 어렵다고 생각이 들었다. 이쯤 도저히 머리가 안돌아가서 힌트를 봤다. 스택을 사용하라고 되어있어서 어떻게 풀어야할지 고민을 꽤 했다. 그러다가 갑자기 스택에 넣고 뺄때 비교하면 될거같다고 생각이 들었다. 스택의 최상위 값이랑 index 가 가리키는 값을 비교해서 최상위 값이 크거나 같을때까지 스택에서 pop하고, K 개의 원소를 뺄 때까지 계.. 공감수 1 댓글수 1 2022. 10. 11.
[백준] 2493 탑 C++ 문제 요약 현재 탑의 크기보다 큰 탑 중 왼쪽으로 가장 가까운 탑찾기 접근 1. 생각의 흐름(Greedy) 출력 아무것도 없을때 0 값이 있으면 해당 인덱스 값 출력 -> (value, index ) 같이 넣어야할듯 저장한 값보다 값이 크면 큰값이 나올때까지 pop 저장한 값보다 값이 작으면 push 전체 코드 #include #include #define MAX_N 500000 using namespace std; int N; int arr[MAX_N]; int main() { cin >> N; for (size_t i = 0; i > arr[i]; stack s; // value, index for (size_t i = 0; i < N; i++) { if (s.empty().. 공감수 0 댓글수 0 2022. 10. 11.
[프로그래머스] 모음사전, C++ 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 알파벳 aeiou 로 만들어지는 단어에 대한 사전순 위치 구하기 접근 1. 완전탐색 생각없이 완전탐색으로 구현했다. 모든 값을 구해서 map에 저장한다. for문으로 구현하는데 실패해서 재귀함수를 사용했다. void make(int ind, string word) { if (ind == 6) { return; } if (word != "" && !dict.count(word)) { // dict[word] = index++; 아래 두줄을 하나로 합쳐도 된다. dict[word] = index; in.. 공감수 0 댓글수 1 2022. 10. 11.
[백준] 2143 두 배열의 합, C++ 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 문제 요약 두 배열이 주어졌을때 각각의 배열로 만들수 있는 부배열의 합이 T가 되는 부배열쌍의 개수 구하기 접근 1. 생각의 흐름 각 배열의 부배열합을 구해서 저장해야한다. 원소가 1개인 것부터 모든 원소가 들어간 것 까지의 부배열을 만들고 그의 합을 저장했는데 누적합을 사용했다. void makeArr( vector& arr, vector& cumArr, int size ) { a.. 공감수 0 댓글수 0 2022. 9. 18.
[백준] 1351 무한수열, C++ 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 문제 요약 무한 수열 A의 N 번째 값 구하기 A0 = 1, Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1) (⌊x⌋는 x를 넘지 않는 가장 큰 정수이다.) 접근 1. 구현 주어진 조건에 대해 구현하기. N 에 대해서 구해야하므로 Top Down 방식이 나을듯 했다. 그리고 max(N) = 10^12 이므로 꽤 많은 연산이 있을 것이고 중복 되는 값이 있을 것이므로 Dynamic Programming으로 구현한다. DP을 위해 배열을 사용해서 메모리를 잡으면 공간복잡도는 O(N)이나 최대값이 4*10^12이므로 메모리 제한을 초과한다. -> 해시(unordered_map)를 사용해서 필요한 값만 저장.. 공감수 0 댓글수 0 2022. 9. 18.
[백준] 1103 게임, C++ 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 문제 요약 동전이 보드 위에서 움직일 수 있는 최대횟수 구하기 접근 1. 생각의 흐름 1 - BFS 보드가 이차원이고 모든 방향을 탐색하면서 최대로 움직이는 횟수를 파악해야하므로 그래프 탐색중 BFS를 사용해야할 것 같았다. BFS는 특정 지점까지의 최소 거리를 구할 때 사용하는데 이 경우에서도 충분히 사용할수 있을 거라고 생각했다. (멈추는 지점까지의 최소 거리를 구하면 최대로 움직인 거리를 구하는 거랑 같을 거니까) 간단하게 적어보면 다음과 같다. (0,0).. 공감수 0 댓글수 0 2022. 9. 12.
[Softeer] 교차로, C++ Softeer 자율주행차가 아래와 같은 교차로를 통과하는 상황을 생각하여 보자. 이 문제에서 다루는 교차로에서는 직진만 가능하기 때문에, 아래 그림과 같은 네 가지 방법으로만 교차로 softeer.ai 문제 요약 자동차별로 교차로를 통과하는 시간 출력하기 우측 도로에 자동차가 없어야 통과할수 있음 접근 1. 머리에 생각나는 대로 알고리즘 작성 A~D까지 도로 Queue 생성, 입력에 대해서 도로별로 시간을 push 출력을 위해 queue도 생성 Time(t) = 0 부터 시작해서 매 초 각 도로 확인 A~D 도로의 첫번째 차가 도착한 시간 확인. 차 시간이 현재 시간보다 작거나 같은 경우 오른쪽에 차가 없으면 체크 나머지 경우 패스(현재시간보다 크거나, 작거나 같지만 오른쪽에 차가 있는 경우) 네 도로 .. 공감수 1 댓글수 3 2022. 9. 5.
[백준] 2252 줄세우기, C++ 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 요약 비교 상태를 사용하여 줄 세우기, 위상 정렬 접근 1. 트리 트리를 생성한다음 최상위 노드에서 후위 순회하는 방식으로 접근했다. 이 접근방식을 구현할때 반례가 바로 떠올라 안될거같아서 적당히 구현했다. #define MAX_SIZE 32000 int visit[MAX_SIZE + 1]; // 128kb int parent[MAX_SIZE + 1]; // 128kb void postorder(int index,.. 공감수 1 댓글수 1 2022. 9. 5.
[백준] 12865 평범한 배낭, C++ 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 요약 N개의 물건으로 가방을 싸는 문제 최대 무게 K를 넘지 않으면서 가방에 든 물건이 최대 가치를 지녀야한다. 접근 1. Greedy 무게가 높고 가치가 높은 순으로 정렬한 뒤에 하나씩 넣으면서 해도 정렬을 한뒤에 풀어도 괜찮은지 고민해봤지만 풀리지 않는 예제가 있어서 바로 넘어갔다. 2. Bruteforce 그 다음 쉬운 방법인 브루트 포스 이다. 모든 물건에 대해서 넣거나 넣지 않거나 모.. 공감수 1 댓글수 5 2022. 9. 1.
[백준] 11055 가장 큰 증가 부분 수열, C++ 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 문제 요약 수열 A에서 증가 부분 수열 중 합의 최댓값 찾기 접근 1. 규칙찾기 알고리즘 규칙찾기 새로 알게된 것 dp 너무 어려운데..? 전체 코드 #include #include // max #define MAX 1000 using namespace std; int N, answer; int arr[MAX]; int memo[MAX][MAX]; void printMemo(int size) { for (.. 공감수 0 댓글수 0 2022. 8. 30.
[백준] 2133 타일 채우기, C++ 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 요약 3xN 크기의 벽을 2x1, 1x2의 타일로 채우는 경우의 수 접근 1. 규칙찾기 n이 홀수면 만들수 없음 n이 짝수인 경우 만들수 있음. n= 2: 3개 n= 4: (n = 2인 타일에 n = 2인 타일을 추가하는 경우) + (n=4인 타일을 추가하는 경우, 새로운 타일) 3*3 + 2 개 = 11개 n= 6: (n = 4인 타일에 n = 2인 타일을 추가하는 경우) + (n = 2 인 타일에 n=4인 타일을 추가하는 경우) + (n = 6 인 타일을 추가하는 경우, 새로운 타일) - (중복값 제거) 11*3 + 2 + 2*3 = 33 + 2 + 6 = 41개.. 공감수 0 댓글수 0 2022. 8. 30.
[백준] 2580 스도쿠, C++ 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 요약 스도쿠 정답을 찾으면된다. 행과 열, 3X3 안에 1~9가 중복없이 들어가야한다. 접근 1. Brute-force 숫자를 넣어야하는 자리수는 최대 81개이고 1부터 9까지 모든 값을 넣어서 확인하려면 981 이 된다. O(232) 는 대충 42초 정도 걸리는데 이 값보다 크므로 이 방법으로 풀수 없다. 물론 0인 위치에서만 확인하면 되지만 찾아야하는 위치가 9개 이상이면 3초가 넘으므로 입력값을 알지 못하면 풀수 없다. 2. Backtracking 백.. 공감수 0 댓글수 0 2022. 8. 21.
[프로그래머스] 메뉴리뉴얼, C++ 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 손님들이 주문한 단품 메뉴로 코스요리(조합)를 만든다. 코스 요리는 단품 두개 이 상으로 이루어져있다. 코스 요리의 길이(단품 메뉴의 개수)를 보고 그 중에 가장 많이 선택된 조합을 반환한다. 접근 모든 손님들이 주문한 단품 메뉴로 모든 조합을 만들어야한다. 조합을 만들 때 반복문, 라이브러리, 백트래킹으로 구현할수 있다. 1. 조합만들기 - 반복문 반복문을 중첩해서 사용하면 쉽게 조합을 만들수 있다. 예를 들면 ABCDE에서 3개의 원소를 가지는 조합을 만들기 위해선 다음과 같이 짜면 된다. st.. 공감수 0 댓글수 0 2022. 8. 21.
[백준] 2641 다각형그리기, C++ 2641번: 다각형그리기 모눈종이에 다각형을 그리려고 한다. 그리는 방법은 모양수열로 표시된다. 모양수열은 1과 4사이의 숫자가 연속되어 나열된 것으로 1은 오른쪽으로, 2는 위쪽으로, 3은 왼쪽으로, 4는 아래쪽으로 www.acmicpc.net 문제 요약 처음 주어지는 모양수열로 만들어진 도형과 같은 도형이 나오는 수열을 찾는 문제이다. 모양수열은 방향을 가리키는 숫자 (1: 우, 2: 상, 3: 좌, 4: 하)로 이루어진 수열이다. 회전이나 뒤집었을때 같은 도형은 다른 것으로 생각한다. 접근 1. 쉬운 도형을 직접 그려서 규칙 확인 크기가 1인 정사각형의 모양수열을 확인했다. 좌측 상위의 점을 시작점으로 잡았을 때 시계방향으로 도는 모양수열은 1-4-3-2가 된다. 같은 시작점이고 반시계방향인 모양수.. 공감수 0 댓글수 0 2022. 8. 20.
[백준] 1149 RGB거리, C++ 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 알고리즘 스터디의 첫 문제이다. 이 문제의 알고리즘은 Dynamic Programming 이다. 이웃하는 집의 색이 같지 않게 하면서 모든 집을 칠해야하고, 이 때의 최소 비용을 구해야한다. 제일 처음 생각했던 건 Greedy 방식이다. 매순간 마다 최소 비용을 선택하되 이웃하는 집의 색이 같지 않게 칠하면 된다. 3 1 100 100 100 100 100 1 100 100 위와 같은 입력에서 입력이 1번 집은 최소 비용이 1인 빨강을 선택.. 공감수 0 댓글수 0 2022. 8. 13.
[LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree, C++ https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/submissions/ Lowest Common Ancestor of a Binary Search Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이진 탐색 트리에서 가장 가까운 공통 조상을 찾는 문제이다. 알고리즘 순서는 다음과 같다. 1. 주어진 root를 시작으로 BFS를 진행한다. 1-1. 이 때 unorde.. 공감수 0 댓글수 0 2022. 8. 13.
[백준] 3649 로봇 프로젝트 python https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 투 포인터 문제이고 어렵진 않았다. 다만, try except를 사용해서 에러를 캐치해야하는게 별로 좋지 않은 문제인듯 하다. import sys; input = sys.stdin.readline def main(): while(1): try: # 0 input x = int(input()) * 10**7 n = int(input()) nums = [int(input()).. 공감수 0 댓글수 0 2022. 5. 23.
[프로그래머스] 단체사진 찍기, 2017 카카오코드 본선, C++ https://programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 꽤 오래 걸린 문제이다. 우선 어떻게 풀어야할지 감이 안왔다. 처음 문제를 봤을때 순열을 구하는 공식을 사용해서 만들어야하나 고민했다. 하지만 level 2에서 그런 문제가 나올리가 없다고 생각해서 다른 방법을 생각했다. 물론 공식을 사용해서 풀수만 있으면 훨씬 빠르게 끝낼수 있었겠지만 범위가 있어서 공식은 아니라고 판단헀다. 오랫동안 고민했는데 도저히 떠오.. 공감수 1 댓글수 0 2022. 5. 19.
[백준] 8972 미친 아두이노 python https://www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 구현문제이므로 설명은 패스 import sys; input = sys.stdin.readline d = [(1, -1), (1, 0), (1, 1), (0, -1), (0, 0), (0, 1), (-1, -1), (-1, 0), (-1, 1), ] def calculate_direction(arduino, js): r1, s1 = js r2, s2 = arduino if r1 < r2: dr =.. 공감수 1 댓글수 0 2022. 4. 11.
[백준] 7682 틱택토 python https://www.acmicpc.net/problem/7682 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 구현문제이다. # import sys; input = sys.stdin.readline def check_line(string, player): ret = False if player == string[0] == string[1] == string[2]\ or player == string[3] == string[4] == string[5]\ or player == string[6] == str.. 공감수 0 댓글수 0 2022. 4. 8.
[백준] 17609 회문 python https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 회문 체크하는게 굉장히 오래걸렸다. 처음 시도는 슬라이싱으로 했으나 시간초과가 되어 인덱스로 접근하는 방식으로 했다. # import sys; input = sys.stdin.readline def check_palindrome(string, start=None, end=None): if start is None: start = 0 if end is None: end = len(string) - 1 cnt = 0 pre_idx.. 공감수 0 댓글수 0 2022. 4. 7.
[백준] 21608 상어 초등학교 C++ https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 구현문제여서 알고리즘 설명은 스킵. #include #include using namespace std; typedef struct Seat { int num; // student number int adj[4]; // u l r d int adj_student; // number of adjacent student } SEAT; SEAT arr[20][20]; int like[401].. 공감수 0 댓글수 0 2022. 4. 4.
[백준] 17281 ⚾ C++ https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 브루트포스 문제이고 시뮬레이션 방식으로 풀었다. 알고리즘은 다음과 같다. 1. 입력 vector에 array를 추가하는 방식으로 이닝별 선수들의 행동을 저장했다. 2. 브루트포스 2-1. 1~9까지 순열 구하기(permutation) 2-2. 구한 순열로 시뮬레이션해서 점수 구하기 2-3. 최대 점수 갱신 1부터 9까지 숫자를 가지고 있는 배열(players_order)을 선언하고 algorithm 헤.. 공감수 0 댓글수 0 2022. 4. 1.
[백준] 20056 마법사 상어와 파이어볼 Python https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 시뮬레이션 문제이다. 알고리즘 순서는 다음과 같다. 1. 입력 1-1. board: 격자 정보, fireballs: 파이어볼 정보 1-2. 0 공감수 0 댓글수 0 2022. 3. 31.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.