취업 준비 및 일상

반효경 교수님의 강의 및 '운영체제와 정보기술의 원리'를 바탕으로 정리하였습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그렇게 어려운 문제는 아닌데, 독해력 문제로 많이 헤맸습니다. 헤맨 부분 '입출력 예 #2'에서 왜 "AB"는 정답이 아닐까? -> 길이가 같은 course에 대해서는 등장횟수가 가장 많은 메뉴만 코스메뉴 요리 후보군에 넣기 때문입니다. 아마 "... 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다."가 저 logic이지 않나 싶은데, 알고 읽..

링크: 설명 / 문제집 처음 KMP 알고리즘을 접했을 땐, 이해하는데 1시간 반이 걸렸습니다. 그래도 한번 공부해서 그런지, 오랜만에 봐도 이해하는데 30분밖에(?) 걸리지 않았네요. 되돌아서면 헷갈리는 알고리즘입니다. 문제 풀이 백준 16916번 부분 문자열, 백준 16172번 나는 친구가 적다 (Large) - 기본적인 KMP 활용 문제입니다. Python에서 in 연산이 O(N)이라, 코테에서 이런 유형의 문제가 나오면 python 및 C++의 library를 활용하는 것이 낫습니다. 백준 1786번 찾기 - 기본 KMP 문제인데, 위 두 문제와 다르게 '부분 문자열이 몇 번 나왔으며, 시작 위치가 어디인지'를 구해야 합니다. KMP 알고리즘을 활용해서 풀었다면 위 문제에서 '부분 문자열을 찾은 순..

https://www.acmicpc.net/problem/16455 16455번: K번째 수 찾는 함수 C++17, Java 8, C11, PyPy3, C99, C++98, C++11, C++14, Java 8 (OpenJDK), Go, C99 (Clang), C++98 (Clang), C++11 (Clang), C++14 (Clang), C11 (Clang), C++17 (Clang) www.acmicpc.net 풀이 N = pivot} 으로 나누어, |L| + |C| K이면 L에서 새로운 pivot을 찾고, |L| = K이면 적당히 L or C에서 K번째 원소를 찾는 방법입니다. quicksort랑 다르게 amortized O(N) 시간복잡도를 가지지만, worst case..

https://www.acmicpc.net/problem/24025 24025번: 돌의 정령 줄세우기 $4$, $1$, $5$, $2$, $3$으로 배치한다면 돌의 정령 무리들의 시야점수는 각각 $2$, $1$, $10^9$, $1$, $10^9$로 조건을 만족한다. www.acmicpc.net 풀이 전형적인 코드포스 스타일의 구성적/그리디 문제입니다. 쌩 브루트포스는 O(N!)일테니 절대 안되며, 적당히 가지치기한다고 해도 O(N^2) 이하로 줄이기가 쉽지 않아보입니다. 그러다 보면, '최적의 배치가 존재하지 않을까?'와 같은 생각에 도달하게 됩니다(그리디 말고는 생각나는게 없으니...). 그리디하게 찾아보도록 합니다. 1-based를 기준으로, 1 = 1이므로, 언제나 조건을 만족합니다. 그리고, N..

현대모비스 알고리즘 경진대회를 본 이후, 1) CP에 관심이 생겨서 2) 언젠가 한 번은 해보고 싶어서 3) 백준 아이디를 파랗게 칠하고 싶어서 코드포스를 좀 했습니다. 총 6번의 round를 치루면 소위 '배치고사'가 완료되어 본인의 rating이 결정됩니다. 배치고사 이내 블루를 찍어서 다행입니다. 코드포스 문제 스타일 (DIv.2 기준) A~D 공통 구현이 그렇게 중요하진 않습니다. 삼성 SW 테스트는 툭하면 한 문제당 코드 100줄이 넘어가는데, 그런 문제는 별로 없어요. 디버깅도 그렇게 중요하진 않습니다. 어차피 채점(실시간으로 작은 샘플인 pretest로 채점을 해 주는데, pretest 통과하면 왠만하면 system testing도 통과합니다.)도 해주고, A, B는 많이 틀릴 일이 없고, ..

백준 13459번: 구슬 탈출 백준 13460번: 구슬 탈출 2 백준 15644번: 구슬 탈출 3 백준 15653번: 구슬 탈출 4 3달 전 즈음에 구슬 탈출 2를 풀었습니다. 당시 구현에 급급하여 간신히 풀었고, 풀고 나서 '어휴 이런 문제는 꼴도 보기 싫다~' 하고 눈 앞에서 치워버린 기억이 납니다. 다시 풀어보니, 구현이 적당히 많고 까다로우며, 시간 커팅할 부분이 많은 흥미로운 문제라 느껴집니다. 풀이 '백준 13459번: 구슬 탈출'을 기준으로 설명합니다. 기본 구현 0) 기울일 때마다 움직이는 건 구슬 2개뿐이므로, 각 구슬의 좌표를 따로 저장하여 관리합시다. 그리고 구멍 좌표도 따로 저장해둡니다. 1) 방향과 빨간 구슬, 파란 구슬 위치에 따라 어느 구슬을 먼저 움직일 지 결정합니다. 2) ..

https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 한 번에 시행동안 1) 가장 적은 물고기를 가지고 있는 어항에 물고기 넣어주기 - putFish() 2) 첫 번째 마법 - magic1() 3) 물고기 수 조절 - spread() 4) 다시 일자로 펴주기 - badak() 5) 두 번째 마법 - magic2() 6) 물고기 수 조절 - spread() 7) 다시 일자로 펴주기 - badak() 8) 최대 물고기 수 어항 - 최소 물고기 수 어항

https://www.acmicpc.net/problem/23289 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net 풀이 한 번의 과정은 5단계로 나뉩니다. 1) 온풍기에서 바람이 나감 - 가장 어려운 부분이었습니다. - 각 칸마다 바람이 퍼질 수 있는지 bfs/dfs로 판정하면 됩니다. - 저는 가로벽을 해당칸에 1, 세로벽을 해당칸에 2로 나타내어 비트처리해줬습니다. - 4방향을 다 한꺼번에 처리할 수도 있겠으나, 생각이 잘 안나서 저는 하드코딩 했습니다. - 그리고 여기서 오타나서 고생했습니다. 이게 방향..

https://www.acmicpc.net/problem/18235 18235번: 지금 만나러 갑니다 첫 번째 줄에 세 정수 N, A, B가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ A, B ≤ N, A ≠ B) www.acmicpc.net 풀이 풀이를 쓸 생각이 없었는데, 1) 왠지 모르겠는데 난이도가 골드 3이나 되길래 인터넷에 검색해보니 2) 다들 이차원 dp로 풀이를 적길래 풀이를 작성합니다. 1. BFS 처음 Queue에 시작점, 도착점을 넣고, 각 단계마다 visited 배열을 초기화하여 한 단계 내에서 특정 지점을 두 번 방문하면 그 단계를 정답으로 출력하면 됩니다. 이진수의 특성 상 특정 점 s에서 x단계에 e로 가는 경우의 수는 (존재한다면) 유일하기에 가능한 풀이입니다. 2. ..