https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr # 2020 카카오 블라인드 코딩테스트 1차 문제이다. # 단순 구현문제이다. 생각보다 쉬웠는데 정답률이 25.9%여서 놀랐다. # 일단 1번문제이기도 하고 처음에 문제를 볼땐, 완전 탐색을 생각해서 시간초과가 나지 않을 것 같으면 짜보는 게 좋은 것 같다. (열심히 짜놓고 시간초과 나면 손해긴 하지만..) # 문자열을 잘랐을 때 나오는 부분의 최대 길이..
https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net # Trie(트라이) 자료구조를 사용해서 푸는 문제이다. (물론 그냥 내장함수 startswith을 사용해도 풀리긴 한다) * insert함수: string 문자열의 한 글자씩 트리의 children에 저장해주고 마지막 노드에는 전체 문자열인 string을 저장해준다. * search함수: string 문자열을 하나씩 돌며 트리의 children을 계속 방문한다. 문자열을 ..
https://programmers.co.kr/learn/courses/30/lessons/60059# 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr # 몇시간동안 헤매다 겨우 풀었다.. # 삼성기출에 자주나오는 유형과 같이 구현, 시뮬레이션 문제인데 2차원배열을 회전시키는 건 처음이어서 오래걸린 것 같다. # M과 N이 20이하이기 때문에, 모든 key배열과 lock배열을 돌며 하나하나 검사해도 될 것이라 생각했다. rotate함수를 통해 key배열을 돌려주면서 lock의 모든 좌표에 끼워주면서 check함수를 통해 모든 자물쇠의 홈이 끼워졌는지 확인하면..
https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net # 사이클 단어에 눈돌아가서 DFS로 풀려다 실패했다. 단방향 그래프라서 그런건지, 그냥 플로이드-와샬 알고리즘을 사용해서 풀면되는 간단한 문제이다. # dist에 각 정점들 사이의 거리를 입력해주고 플로이드-와샬 알고리즘을 사용해 모든 dist값들을 최단경로로 갱신해준다. # ans에 inf값을 넣어주고 dist배열을 모두 확인하며 dist[i][j]와 dist..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net # DFS로 '사이클'을 찾으면 되는 문제이다. 코테나 다른 그래프 문제중에 사이클을 찾는 문제들을 자주 볼 수 있는데, 생각보다 코드로 구현하기 힘들다. 재귀가 함수 안에서 함수를 계속 부르고 그런것이 가시적이지 않아서 그런 것 같다. 쨋든, 사이클을 찾는 방법은 자주 쓰이니 이해하고 외워두는 것이 좋다! # 배열의 인덱스는 0부터 시작하기 때문에 편하게 숫자를 보기위해 graph에 [0]을 맨앞에 ..
https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net # Union-Find와 BFS 등 여러 풀이가 있는 문제이다. I. Union-Find union, find, check함수는 well-known이니 따로 설명하지 않겠다. 1. 우선 처음에 N, M을 입력받고 진실을 아는 사람수 t와 그 사람들 리스트 tp를 입력받는다. tp에 있는 사람들 번호에 해당하는 know_truth[i]를 True로 바꿔준다. 그리고 M줄에 걸쳐 각 파티마다 오는 사람의 수 p..
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net # BFS/DFS + 시뮬레이션 문제이다. BFS나 DFS 중 아무거나 선택해서 풀면 되는데, BFS가 편해서 BFS로 풀었다. 1. 매 시간마다 m을 돌면서 m[i][j]가 0이 아니고 방문하지 않은 지점이라면 iceberg를 1증가시키고 bfs(i, j, visited)를 실행한다. # bfs함수: 상하좌우를 탐색하며 m[nx][ny]가 0이면 diff[(x, y)] += 1을 해줌으로써..
https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net # 처음에 그냥 union-Find문제인 줄 알고 풀었는데 요구하는 바가 약간 달랐다. 단순히 한 사람이 다른 몇명과 친구인지가 중요한게 아니라 문제에서 요구하는 A-B, B-C, C-D, D-E 이 4가지의 경우를 만족하는지 확인하는 문제이다. 따라서, DFS를 사용하여 꼬리에 꼬리를 무는 식으로 풀었다. # DFS함수: cnt와 x를 넘겨받아 cnt가 4가 되면 문제에서 요구하는 친구관계가 성립되었으므로 1을 출력하고 프로그램을 종료한다. graph[x]안의 원소들을 돌면서 i원소를 방문하지 않았으..
모르는 사이에 조금씩 조금씩..
