greentea31's Note

https://leetcode.com/problems/longest-palindromic-substring/submissions/

풀이 과정

문자열 내에서 가장 긴 팰린드롬 부분 문자열을 구하는 문제이다.

팰린드롬 문자열은 뒤집어도 뒤집기 전의 문자열과 같은 문자열을 의미한다. DP로 풀 수 있는 잘 알려져 있는 문제이지만 O(N^2)로 부분 문자열을 확장해가며 해결하였다.

다음과 같은 알고리즘을 구현해 문제를 해결하였다.

소스 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(i):
            left, right = i, i
            while left >= 0:
                if s[i] == s[left]:
                    left -= 1
                else:
                    break
            while right <= len(s) -1:
                if s[i] == s[right]:
                    right += 1
                else:
                    break
            
            while left >= 0 and right <= len(s) - 1:
                if s[left] == s[right]:
                    left -= 1
                    right += 1
                else:
                    break
            
            return s[left+1:right]
                
        answer = ''
        for i in range(len(s)):
            answer = max(answer, expand(i), key=len)
        return answer

https://leetcode.com/problems/most-common-word/

풀이 과정

문자열에서 금지되지 않은 단어 중에, 가장 많이 나온 단어를 출력하는 문제이다.

isalpha(), islower() 등의 파이썬 내장 함수로 알파벳, 소문자 처리를 문제 조건에 맞게 처리해준 후, collections 모듈의 Counter 객체를 사용하여 문자열 안에 나온 단어의 개수를 세주었다. 

Counter 사용법

a = [1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]이라고 하면,

b = collections.Counter(a) -> Counter({3: 5, 2: 4, 1: 2})

위와 같이 각 원소가 a에서 몇번 나왔는지 카운터 객체로 반환받을 수 있다.

c = b.most_common() -> [(3, 5), (2, 4), (1, 2)]

most_common() 함수를 통해 튜플을 포함한 리스트의 형태로 반환받을 수 있으므로 c[0][0]으로 접근해 a에서 가장 많이 나온 원소가 무엇인지 파악할 수 있다.

소스 코드

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        real_para = ""
        
        for letter in paragraph:
            if not letter.isalpha():
                letter = ' '
            else:
                letter = letter.lower()
            real_para += letter
        
        paragraph = real_para.split()
        paragraph = collections.Counter(paragraph)
        
        for word in paragraph.most_common():
            if word[0] not in banned:
                return word[0]

https://leetcode.com/problems/reorder-data-in-log-files/

풀이 과정

Letter-logs와 Digit-logs로 나누어 정렬하되, Letter-logs가 Digit-logs보다 앞에 와야 하고, Digit-logs는 입력받은 순서대로 정렬하고 Letter-logs는 사전적으로 정렬을 해야하는 문제이다.

logs의 원소들을 split(' ')으로 공백을 기준으로 쪼갠 후, Letter와 Digit을 분류해주었다.

lets.sort(key=lambda x: (x.split()[1:], x.split()[0]))으로 letter log를 사전식으로 정렬하고, [1], [2], [3]...의 모든 원소가 같으면 identifiers로 정렬하게끔 하였다. 

소스 코드

class Solution:
    def reorderLogFiles(self, logs: list[str]) -> list[str]:
        lets, digs = [], []

        for log in logs:
            if log.split(' ')[1].isdigit():
                digs.append(log)
            else:
                lets.append(log)

        lets.sort(key=lambda x: (x.split()[1:], x.split()[0]))
        return lets + digs

현재 m1 맥북 에어에 BenQ사의 EX2510이라는 모니터를 연결해서 사용 중인데, 때때로 외장 모니터의 화면이 불안정? 해지면서 깜빡거리는 경우가 있습니다. 구글링 하여 인터넷에 나와있는 다양한 해결 방법을 시도해봤지만 해결이 되지 않던 중, 최근 해결 방법을 찾게 되어 기록 및 정보 공유 겸 글을 남깁니다.

https://support.apple.com/ko-kr/HT212232

macOS 최신 버전인 macOS Monterey에서는 적응형 동기화라는 기능을 지원합니다. 맥북 프로 14, 16 및 최신 기종의 아이폰 프로 라인업에서 지원하는 Promotion과 동일하다고 보시면 됩니다. 144hz 모니터를 사용하면 모니터가 꺼지기 전까지 항상 144hz로 동작하죠. 하지만 동영상을 본다거나 하는 경우에는 대부분의 경우 30fps, 일부 영상에서만 60fps까지 올라가므로 모니터가 144hz로 동작할 필요가 없습니다. 모니터가 30hz 혹은 60hz로 가동되어도 초당 보여주는 영상의 프레임은 같고, 144hz의 고정 재생률로 모니터가 작동될 때보다 전력을 적게 소모하니, 이런 경우에는 모니터의 재생률을 낮춰 전력 소모를 낮춰주는 기능입니다.

하지만 맥북에 외부 디스플레이를 연결해 사용하는 경우에는 대부분 전원을 연결해서 사용할 것이고 적게 전력을 소모하는 기능이 크게 유용하지 않습니다.

심지어 애플 공식 문서에서 외부 디스플레이가 깜박이는 경우가 있을수 있다고 따로 분류까지 해놓고 그 때의 해결책을 적어놓기까지 했지요. macOS Monterey를 사용 중이고, 외부 디스플레이 깜빡임 문제가 있는데 인터넷에 나온 여러 방법을 시도해봐도 해결이 되지 않았다면 적응형 동기화 기능을 꺼 볼 필요가 있습니다.

적응형 동기화 기능을 끄는 방법 자체는 간단합니다. 디스플레이 설정에 들어가서 재생률을 클릭하고 가변(30~144Hz)로 설정되어 있는 재생률을 다른 재생률로 바꿔주기만 하면 됩니다.

144Hz 등의 다른 재생률로 바꿔주면 화면 깜빡임 문제가 해결됩니다. 그러나 맥을 잠자기 상태로 두고 다시 깨우거나, 모니터 연결을 해제하고 다시 연결하는 경우에 재생률이 다시 가변(30~144Hz)으로 바뀌고 깜빡이게 됩니다. 물론 다시 디스플레이 설정에 들어가서 가변 재생률을 고정 재생률로 바꿔주면 문제가 해결되긴 하지만 맥을 잠자기에서 깨울 때마다 디스플레이 설정에 들어가는 건 매우 귀찮습니다.

Reddit의 외국 맥 사용자들도 Monterey 업그레이드 이후 모니터가 깜빡거린다는 증상을 호소하고 있네요.

Reddit에서 nerdy_coder_라는 사용자가 앱스토어에서 EasyRes 어플리케이션을 설치하고 해상도와 재생률을 설정했더니 한번 설정한 해상도와 재생률이 다시는 바뀌지 않는다고 자신의 해결법을 공유해주었습니다. 이 말을 따라 App store에서 EasyRes를 설치합니다. 무료 프로그램입니다.

EasyRes를 실행하고 External 모니터의 해상도와 재생률을 설정해줍니다. 이러면 맥을 잠자기 후 깨우거나 모니터 연결을 해제한 후 다시 연결해도 가변 재생률로 다시 변경되지 않게 됩니다.

교내 학과 게시판에 삼성 SDS에서 알고리즘 특강을 진행한다는 글이 올라와 지원서를 접수했다. 알고리즘 문제를 풀면 해결을 위한 배경지식이 헷갈리게 기억이 나는 경우가 잦아서 한번 정리해야겠다고 생각했었는데, 10일 동안 집중해서 정리할 수 있는 좋은 기회가 생겨 바로 지원하게 되었다.

사전 테스트

총 5개의 문제를 일주일 동안 풀어야 한다. 시간제한이 아주 넉넉하고 검색도 가능한 환경이므로 한 문제를 오래 고민하며 풀 수 있다. 난이도는 백준으로 따지면 최소 실버 1 이상의 문제들로 구성되어 있었다. 지원서 접수 때 냈던 서류와 사전 테스트 결과로 교육 입과생을 선발하게 된다.

교육 입과

이전에는 잠실에 있는 삼성 sds타워에서 강의를 진행했다고 알려져 있지만 현재는 knox meeting이라는 삼성의 화상 회의 플랫폼을 통해 특강이 진행된다. 삼성 sds에서 자체 제작한 교재로 이론을 설명한 후, 관련된 문제를 백준에서 풀어보는 형식으로 강의가 진행된다. 알고리즘 기초, 자료구조, 정수론, 조합론, 그래프에 대한 내용을 10일 동안 익혀야 하고, 이론 교육을 듣고 적용해서 풀어보는 문제가 바로 백준 기준 골드 ~ 플래티넘 수준의 문제임을 생각해보면 상당히 난이도가 있는 과정이다.

강의를 진행하시는 주강사 님과 질문을 받아주시는 보조강사님이 따로 계셔서 듣다가 이해가 안 가는 부분은 보조강사님께 바로 질문이 가능해 피드백 과정이 빠른 점이 좋았고, 수업시간에 같이 풀어본 문제들은 강사님이 백준 그룹 게시판에 코드를 올려주셔서 내가 짠 코드랑 비교해가며 실력을 증진시킬 수 있었다. 백준 그룹 게시판에 올라온 총 문제는 76문제였는데, 수료 테스트 이전에 다 풀어보면 좋은 문제들이지만 10일 내에 평균 골드 수준의 문제를 76문제 다 푼다는 것은 쉽지 않을 것이다. 하루 수업 중 약 4문제 정도를 풀 시간을 주고 리뷰가 진행되는데, 리뷰가 이루어진 문제 위주로 복습을 진행하고 남는 시간에 문제집의 다른 문제도 더 풀어보았다.

수료 테스트

10일간의 교육과정을 마치고, 바로 다음날 선릉역에 있는 삼성 sds 멀티캠퍼스 건물에서 수료 테스트가 이루어졌다. 삼성 sds professional 등급의 SW 검정 테스트를 봄으로써 수료 테스트가 이루어지는데, 합격하지 못하더라도 80% 이상의 출석과 수료 테스트 응시까지만 하면 수료 처리가 되어 수료 인증서가 발급된다. 하지만 수료 테스트에 합격을 해 Pro 등급을 취득하게 되면, 추후 진행되는 삼성 sds 채용과정에서 큰 메리트를 얻게 된다. pro 전형에 지원해 서류 제출 후 임원 면접을 통과하면 삼성 sds에 입사할 수 있는 혜택이 주어진다.

pro 시험은 4시간 동안 1문제를 푸는 시험이다. 많은 시간이 주어지니 바로 코드를 짜기보단 2장 주어지는 연습장에 문제 풀이 방법을 신중히 구상하는 것이 좋다. 수업 중에 강사님께서도 언급해주시지만, 강의에서 배운 알고리즘을 단순히 구현해서 풀리는 문제는 당연히 나오지 않는다. 배운 알고리즘을 사용해 문제 조건을 따라 추가적으로 응용해야 문제를 해결할 수 있다.

후기

pro 시험에 합격해 pro 전형으로 sds에 지원할 수 있는 기회도 얻었고, 기존에 머릿속에 정리되지 않았던 알고리즘 지식을 정리하여 실력이 증진되기도 해서 교육을 통해 많은 것을 얻어갔다. 4학년 이상의 학생을 대상으로 모집하고, 사전 테스트까지 진행하는 만큼 교육의 난이도가 쉽지만은 않기에 알고리즘 문제를 어느 정도 풀어본 사람이 아니라면 교육을 따라가기 쉽지 않을 것 같았다. 취업 준비로 바쁜 4학년 방학 도중 9 to 6 교육을 10일 동안 들어야 한다는 게 시간이 부담이 될 수 있지만, 시험에 붙는다면 sds의 pro 전형에 지원할 수 있고, 붙지 못하더라도 IT 직군 취직에 필요한 알고리즘 능력을 기를 수 있는 과정인 만큼 추천할 수 있는 특강이다.

https://leetcode.com/problems/reverse-string/

풀이 과정

문자열 s를 뒤집는 문제이다.

크게 3가지 방법을 떠올릴 수 있다.

1. 내장 함수 사용

그냥 파이썬 내장 함수 써서 뒤집는 방법이다. s.reverse()를 사용하면 된다.

2. 투 포인터 사용

문자열의 시작과 끝에 포인터 2개를 두고 포인터의 인덱스에 해당하는 문자끼리 서로 바꿔가면서 왼쪽 포인터는 한칸 전진, 오른쪽 포인터는 한칸 후퇴하면서 계속 바꿔가면 된다. 이 방법대로 문제를 풀이하였다.

3. 문자열 슬라이싱

s = s[::-1]로 뒤집어서 할당해주면 될 것 같지만 문제에서 공간복잡도를 O(1)로 제한하였다. s[:] = s[::-1] 같은 트릭을 사용하여 이 방법으로도 문제를 해결 할 수 있다.

소스 코드

class Solution:
    def reverseString(self, s: List[str]) -> None:
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

https://leetcode.com/problems/valid-palindrome/

풀이 과정

문자열 s가 팰린드롬인지 확인해주는 기능을 구현하면 된다.

팰린드롬이란 문자열을 뒤집어도 똑같은 문자열을 말한다. 예를 들면 기러기, 토마토, 스위스, 인도인, 별똥별, 우영우, 역삼역 등의 단어는 모두 팰린드롬을 만족하는 단어이다.

문제의 조건에 맞게 대문자는 소문자로 바꿔주고, 알파벳이 아닌 문자는 문자열에서 전부 무시해준 다음, 문자열 s와 s[::-1]을 비교해 같으면 팰린드롬 문자열이라고 판단하였다.

굳이 s와 동일한 원소를 가진 s'를 선언해서 s'.reverse()로 뒤집은 다음 s == s'인지 비교할 필요 없이 문자열 슬라이싱으로 더 빠르게 해결할 수 있다.

소스 코드

class Solution:
    def isPalindrome(self, s: str) -> bool:
        chars = []
        for char in s:
            if char.isalnum():
                char = char.lower()
                chars.append(char)
        if chars == chars[::-1]:
            return True
        else:
            return False

https://www.acmicpc.net/problem/11404

풀이 과정

도시와 도시 사이를 오가는 버스의 비용이 주어질 때, 모든 도시의 쌍 (A, B)에 대해 A에서 B로 가는 최소 비용을 구하는 문제이다.

도시는 정점, 버스의 비용은 가중치를 갖는 간선으로 생각하면 하나의 그래프로 모델링할 수 있고, 그래프의 모든 정점의 쌍에 대한 최소 비용을 구하는 문제로 생각할 수 있다.

그래프의 최소 비용 문제에서는 BFS, 다익스트라, 벨만-포드, 플로이드-와샬 알고리즘을 생각해 볼 수 있으며 그중에서 모든 정점의 쌍에 대한 최소 비용은 플로이드-와샬 알고리즘을 사용해서 구할 수 있음이 알려져 있다.

플로이드-와샬 알고리즘을 사용하여 문제를 해결하였다.

소스 코드

#include <iostream>
#include <vector>
using namespace std;

const int INF = 987654321;
int d[105][105];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 1 ; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = INF;
        }
    }

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }

    for (int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (d[i][j] == INF) cout << "0 ";
            else cout << d[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

https://www.acmicpc.net/problem/2606

풀이 과정

컴퓨터와 연결된 네트워크가 주어질 때, 1번 컴퓨터와 네트워크로 연결되어서 웜 바이러스에 걸리게 되는 컴퓨터의 수를 구하는 문제이다.

컴퓨터와 네트워크는 그래프의 정점과 간선으로 모델링 할 수 있고, 1번 정점과 연결된 연결 요소에 포함된 정점의 개수 - 1이 정답이 될 것이다. 연결 요소의 정점의 개수는 DFS 혹은 BFS로 정점들을 탐색하면서 구할 수 있다.

소스 코드

DFS

#include <iostream>
#include <vector>
using namespace std;

vector<int> E[101];
bool visited[101];
int answer = -1;

void dfs(int x) {
    answer++;
    visited[x] = true;

    for (auto next : E[x]) {
        if (visited[next]) continue;
        dfs(next);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int computer, edge, u, v;
    cin >> computer;
    cin >> edge;

    for (int i = 0; i < edge; i++) {
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    dfs(1);
    cout << answer << '\n';

    return 0;
}

BFS

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> E[101];
bool visit[101];
int answer;

void bfs(int start_x) {
    queue<int> Q;
    Q.push(start_x);
    visit[start_x] = true;

    while(!Q.empty()) {
        int cur = Q.front(); Q.pop();
        for (auto next : E[cur]) {
            if (visit[next]) continue;
            Q.push(next);
            answer++;
            visit[next] = true;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int computer, e, a, b;
    cin >> computer;
    cin >> e;

    for (int i = 0; i < e; i++) {
        cin >> a >> b;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    bfs(1);

    cout << answer << '\n';

    return 0;
}

https://www.acmicpc.net/problem/9663

풀이 과정

NxN 크기의 체스판 위에 퀸 N개를 서로 공격할 수 없게 배치하는 경우의 수를 구하는 문제이다.

유명한 백트래킹 문제이다. 체스판 위에 퀸을 하나 하나 놓아가면서 이전에 놓았던 퀸이랑 같은 행, 열, 대각선에 위치하면 여기에는 못놓는다 판정하고 다음 위치에 놓아보는, 이러한 과정을 코드로 구현하면 된다.

체스판에서의 퀸의 위치를 2차원 배열로도 표현할 수 있지만, board[i] = j (i번째 행에 j번째 열에 퀸이 존재함) 과 같이 1차원 배열로도 퀸의 위치를 나타낼 수 있다.

1차원 배열과 재귀함수로 백트래킹을 해가면서 답을 구하였다.

소스 코드

#include <iostream>
using namespace std;

int board[16];
int N, answer;
void nQueen(int y) { // y개의 퀸이 체스판 위에 존재함
    int ko;

    if (y == N) { // N개 다 놓았으면 정답을 증가시킴
        answer++;
        return;
    }

    for (int i = 0; i < N; i++) { // y번째 행의 i번째 행의 칸에 대해서
        ko = 1;
        for (int j = 0; j < y; j++) { // 이미 놓인 퀸들에 대해서
            if (board[j] == i || abs(i - board[j]) == abs(y - j)) {
                ko = 0; // 같은 열에 존재하거나, 대각선에 이미 퀸이 존재해서 배치 불가능
                break;
            }
        }

        if (ko) { // 배치 가능하면
            board[y] = i; // 배치하고
            nQueen(y+1); // y+1개의 퀸이 존재하는 체스판 위에서 알고리즘을 다시 시행함
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    nQueen(0);

    cout << answer;
    return 0;
}