알고리즘
[프로그래머스] 위클리 챌린지 5주차 모음사전
https://programmers.co.kr/learn/courses/30/lessons/84512 코딩테스트 연습 - 5주차 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr 모음사전 알고리즘 : 순열 / 구현 풀이가 정말 다양한 문제입니다. 정답 제출 후 다른 사람의 풀이를 보니 이게 왜 되지..? 싶은 코드가 많은 것 같습니다. 시간제한이 넉넉하니 편한 방법으로 풀이하면 될 것 같습니다. #include #include #include #in..
2020 KAKAO BLIND RECRUITMENT 1차예선 풀이
카카오 2021 문제를 푼 뒤 2020 문제로 넘어왔습니다. 이전 글과 마찬가지로 매일매일 공부기록용으로 글을 작성하는 것이기 때문에 문제를 풀면 글이 업데이트 하는 식으로 진행할 생각입니다. 2020은 문자열 문제가 많다는 느낌을 받았습니다. (문자열에 약한..) 또한 문제에 오해를 할 수 있도록 내놓은 구문이 많아 헷갈리기 쉬우므로 주의가 필요합니다. https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr..
2021 KAKAO BLIND RECRUITMENT 1차예선 풀이
요즘 클린코드 책을 공부하느라 알고리즘에 손을 떼고 있었는데, 다음 달에 있는 2022 KAKAO BLIND RECRUITMENT를 참여하기 위해 연습삼아 풀어봤습니다. (진행중) 싸지방에서 시간이 되는대로 예전 문제까지 풀어볼 생각입니다. 카카오 코딩테스트는 프로그래머스에서 진행되는데 처음 접해보신 분들은 제출 환경에서 당황할 수 도 있습니다.solution 함수를 구현하되 매개변수와 return 값은 건들면 안되고, 제출 시 main 함수는 있어도 되니 똑같이 제출하면 됩니다. https://programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가..
[BOJ / DFS] 17370 육각형 우리 속의 개미
https://www.acmicpc.net/problem/17370 17370번: 육각형 우리 속의 개미 무한히 많은 정육각형이 서로 맞닿아 놓인 형태의 개미 우리가 있다. 다음 그림과 같은 형태이고, 하얀색 변으로만 개미가 다닐 수 있다. 개미 우리의 모습 곤충 관찰이 취미인 유이는 세 정육각 www.acmicpc.net 17370 육각형 우리 속의 개미 알고리즘 : Bitmask / DFS 육각형 필드를 배열에 넣는 방법이 중요한 문제입니다. 육각형 이전 움직임에 따른 다음 움직임을 6*2 배열에 넣어두고 현재 배열의 상태를 최대 길이가 44이므로 (오른쪽 왼쪽으로 22칸씩 진행가능하므로) long long int를 이용한 비트마스크로 현재 방문 상태를 저장합니다. 이를 활용해 풀이 가능합니다. < ..
[BOJ / 2-SAT] 11281 2-SAT - 4
https://www.acmicpc.net/problem/11281 11281번: 2-SAT - 4 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net 11281 2-SAT - 4 알고리즘 : 2-SAT / 강한연결요소(SCC) 이전 글에서 풀었던 2-SAT-3의 심화 문제입니다. 이전 문제는 가능한지 판별만 하였다면, 이번 문제는 가능한 케이스 한 개를 같이 출력하여야 합니다. (스페셜 저지) isVisited 변수는 SCC를 구성하는 순간 쓸모가 없어지므로 이 변수에 몇 번째 S..
[BOJ / 2-SAT] 11280 2-SAT - 3
https://www.acmicpc.net/problem/11280 11280번: 2-SAT - 3 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net 11280 2-SAT-3 알고리즘 : 2-SAT-3 / 강한연결요소(SCC) SCC 알고리즘를 활용한 알고리즘으로 2-SAT이라는 알고리즘이 있습니다. 전에 휴리스틱으로 풀었던 변수 3개까지 항을 가진 3-SAT은 NP문제인 반면 변수가 2개인 2-SAT은 강한연결요소를 이용하여 풀이할 수 있습니다. (X_i V X_j)인 경우 !X..
[BOJ / SCC] 4196 도미노
https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 4196 도미노 알고리즘 : 강한연결요소(SCC) SCC를 이용하여 사이클을 하나의 정점으로 만들어 위상정렬의 방식을 일부 따와서 푸는 문제입니다. 위상정렬은 사이클이 존재하면 풀리지 않으므로 SCC를 이용하여 사이클을 제거해주고 새로운 SCC에서 indegree가 0인 것을 카운팅 해주면 풀이됩니다. #include #include #include #include #include using na..
[BOJ / 휴리스틱(시뮬레이티드 어닐링)] 2582 동전 뒤집기 2
https://www.acmicpc.net/problem/2582 2582번: 동전 뒤집기 2 첫째 줄에 32 이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 2582 동전 뒤집기 2 알고리즘 : 휴리스틱(시뮬레이티드 어닐링) 시뮬레이티드 어닐링을 처음 공부할 때 풀었던 문제입니다. 첫 공부 시 다른 사람의 소스를 분석하여 풀이하느라 유사한 점이 많습니다. 밑 코드에서 주석으로 표기하였으니 이해하시는데 도움이 되었으면 좋겠습니다. 핵심 풀이 시 이해하여야 하는 것은 해당 줄에 앞면이 많은지 뒷면이 많은지는 중요한 것이 아니라 앞뒷면 수의 차이가..