코딩테스트 준비

1

평균 138'Sol : 44'

평균 180'

평균 100'Sol : 44' 40''수행 시간 : 90ms메모리 : 18MB

평균 107'sol : 30' 53''수행시간 : 110ms 메모리 : 20MB

자율주행 자동차 Simulation 평균 : 98'

평균 110'sol : 72' 51''수행 시간 : 2542ms메모리 : 24MB

평균 75'sol : 수행 시간메모리

평균 : 180'sol : x수행 시간 : -메모리 : -

평균 : 153'sol : 75' 45''수행 시간 : 54ms메모리 : 16MB

평균 : 51'sol : 18' 11''수행 시간 : 88ms메모리 : 19MB

평균 : 180'sol : 수행 시간 : 메모리 :

디버깅 Backtracking, Simulation 평균 : 180' sol : 수행 시간 메모리

드래곤 커브 Simulation 평균 : 180' sol : 수행 시간 : 메모리 :

병원 거리 최소화하기 Backtracking 평균 : 92' sol : 수행 시간: 메모리:

평균 : 110'sol : 37' 48''수행 시간 : 291ms메모리 : 24MBNew skill learnedBFS 내에서 visited를 사용하는 게 기본 골격이라면, 해당 타이밍에서 내가 원하는 정보들을 뽑아올 수도 있어야 한다.이 코드에서는 'mixed_are

바이러스 실험 Simulation 평균 : 180' sol : 150' 20'' 수행 시간 : 4060ms 메모리 : 100MB > New skills list에서 특정 값 제거 : ex) remove를 하면 for loop에서 끝나버리는 문제가 발생. > 시간

평균 : 180'sol : 114' 42''수행 시간 : 55ms메모리 : 16MBNew skills최단거리가 그래서 얼만데? -> Queue에 넣는 타이밍을 구분할 줄 알아야 하는데..큐에 넣을 때 number를 같이 넣어주도록 설계해서 해결!이번 문제는 매우 깔끔하

평균 : 136'sol : 89' 15''수행 시간 : 654ms메모리 : 24MBEasy.

생명과학부 랩 인턴 simulation 평균 : 180' sol : 수행 시간 : 메모리 :

격자 숫자 놀이 Basic 평균 : 180' sol : 수행 시간 메모리

평균 : 158'sol : 116' 30''수행 시간 : -메모리 : 80MB 초과New skills최대한 재사용 가능한 지표들을 파악해서 활용해야 메모리 초과를 피할 수 있다.

평균 : 180'sol : 190' 08''수행 시간 : 295ms메모리 : 23MBNew skillsBacktracking은 진짜 죄악일 수도 있구나.오히려 4중 for문을 돌리는 게 시간을 훨씬 더 절약했다.왜냐, 백트래킹은 재귀 호출 / 리턴 스택 오버헤드 제거를

평균 : 180'sol : 163' 21''수행 시간 : 98ms메모리 : 20MBNew SkillsQueue를 활용하고 싶은데, 순서 역전을 할 때 큐도 역정렬이 가능한가?horse_map = \[\[deque() for \_ in range(n)] for \_ in

평균 : sol : -수행 시간 : 152ms메모리 : 21MBNew Skills

평균 : 180'sol : 240'수행 시간 : 372ms메모리 : 25MBNew Skills도착한 말은 horsespos == -1인데, 현재 코드는 이 케이스를 건너뛰지 않고 paths-1로 읽어버려(파이썬 음수 인덱싱).→ 엉뚱한 배열(sc_30)을 보면서 가짜

평균 : 180'sol : 131' 30''수행 시간 : 282ms메모리 : 24MBNew Skills딱히 새로운 기술을 터득한 건 없고, 그냥 꼼꼼하게 설계 다 하고 푸니까 쉽게 풀었다.

술래잡기 체스 Backtracking 평균 : sol : 수행 시간 메모리 > New Skills

승자독식 모노폴리 Simulation 평균 : 180' sol : 수행 시간 : 메모리 : > New Skills

평균 : 180'sol : 318' 04''수행 시간 : 233ms메모리 : 24MB진짜 줜나 너무하네... 5시간 넘게 걸렸다...설계는 진짜 잘했는데, 집중력에서 이슈가 생겼고, 막바지에 꼼꼼하지 못했다. 아쉽다. 그래도 L15를 해결해서 만족.New SkillsB

평균 : 180'sol : 87'43''수행 시간 : 50ms메모리 : 16MBNew SkillsBFS 사용시1\. 최단거리 가능 여부2\. 최단거리 길이3\. 최단거리 역추적위 3개 확실히 숙지하자.

평균 : 178'sol : 85'28''수행 시간 : 87ms메모리 : 18MBNew SkillsL11은 이제 너무 쉽다.

평균 : 180'sol : 164' 44''수행 시간 : 시간 초과메모리 : 32MBNew Skills1\. atoms 리스트만 가지고 1차원으로 풀 것인가?2\. grid를 생성해서 2차원 상에서 풀 것인가?리스트를 통해 풀려고 하니까 리스트 삽입, 삭제가 너무 많이

평균 : 180'sol : 146'57''수행 시간 : 575ms메모리 : 25MBNew Skills어렵지 않은 문제라 생각해서 너무 대충 풀다가 시간이 오래걸렸다.이런 문제는 1시간 안에 끝내자.

회전하는 빙하 Simulation, BFS 평균 : sol : 수행 시간 메모리 > New Skills 회전 드디어 나왔다! 먼저 수식으로 접근해보자. n x n 정방행렬의 전체 범위 시계 방향 90도 회전 row, col이 0부터 시작한다고 가정하면 n x n

놀이기구 탑승 Simulation 평균 : 180' sol : 수행 시간 메모리 > New Skills

평균 : 180'sol : 96' 36''수행 시간 : 212ms메모리 : 23MBEasy. 수행 시간도 모범 답안과 매우 근사.

나무 타이쿤 Simulation 평균 : 170' sol : 수행 시간 메모리 > New Skills

평균 : 180'sol : 131' 12''수행 시간 : 132ms메모리 : 21MBNew SkillsEasy

평균 : 180'sol : 192' 50''수행 시간 : 54ms메모리 : 17MBNew Skills한 번 짤 때 좀 제대로 짜자.초반 설계시 데이터 구조 & 알고리즘 보다 명확하게 짜고 들어가자.

왕실의 기사 대결 Simulation 평균 : 180' sol : 수행 시간 메모리 > New Skills

평균 : 180'sol : -수행 시간 : -메모리 : -New Skills연쇄 이동 -> 재귀 함수 호출 : 약점 보완 필요

고대 문명 유적 탐사 Simulation, BFS 평균 : 180' sol : 수행 시간 : 메모리 : > New Skills

마법의 숲 탐색 Simulation, BFS 평균 : 180' sol : 149' 12'' 수행 시간 : 429ms 메모리 : 25MB > New Skills 진짜 하나라도 놓치는 순간 틀리는거야... BFS 구현할 때 하차칸에 인접한 다른 골렘으로 이동하는 조건에서 바로 cgol = nextgol로 바꿔줬다가 틀렸다. availgol.append(ne...

미지의 공간 탈출 Simulation, BFS 평균 : 180' 수행 시간 메모리 > New SKills

DFS

sol : 43'06''골드5 정도..?

몇번 풀다보니 자동으로 이런 템플릿을 만들게 되더라..

lv : 실버4 느낌

lv(개인적인 느낌) : 실버1New Skills배열 내 연속값 찾기는 앞으로 뒤에서 앞칸 확인하기 전략으로 가자.

lv(개인 평가) : New Skills마름모 좌표 구하는 걸 굳이 BackTracking으로 풀었다가 시간초과.곱게 맨해튼 거리로 구하자. 훨씬 빠름.

평균 : 180'sol : 127' 47''수행 시간 : 403ms메모리 : 25MBNew Skillsset을 되게 많이 썼다.

New Skillsmap 자료구조의 등장.dictA = { key: value, key: value, ... }new_map\[(nr, nc)] = \[] -> 즉, \[] value를 갖는 key를 먼저 선언해준 뒤, 나중에 append하는 방식도 있다.

평균 : 180'sol : -수행 시간 : -메모리 : -New SkillsBFS를 더 자유롭게 쓸 수 있다는 걸 깨달았다.모범 답안

예술성 Simulation, BFS 평균 : 180' sol : 2:25:59 수행 시간 : 13ms 메모리 : 3MB

평균 : 180'sol : 75' 38''수행시간 : 15ms메모리 : 0MBEasy.

평균 : 180'sol : 180' 53''수행 시간 : 8ms메모리 : 0MBtuple 대신 struct 사용공통 행동을 함수화해서 재사용상태 갱신 책임을 더 명확히 분리변수명/함수명으로 의도를 드러내기“정답 코드”에서 한 단계 더 나아가 “읽기 좋은 코드” 만들기

평균 : 180'sol : 117' 13''수행 시간 : 8ms메모리 : 0MBLearnings모범 답안을 보니 BFS를 한 번 돌려서 원하는 기능들을 수행한다. 내 코드에서는 두 번의 BFS를 구현하는데, 이는 더 추상화할 여지가 있음을 의미한다.

평균 : 180;sol : 232' 54''수행 시간 : 10ms메모리 : 0MB대각 좌표 보정을 틀려서 1시간 넘게 헤맴.솔직히 어렵진 않았고, 디버깅도 그렇게 어렵진 않았는데 전혀 예상치 못한 곳에서 버그가 발생했다.앞으로는 코드 작성시 애매한 부분이 있으면 Deb

평균 : 180'sol : 171' 26''수행 시간 : 9ms메모리 : 0MB피곤할 땐 차라리 쉬자.그리드 내 임의의 영역에서 좌표 회전

평균 : 180'sol : 190' 26''수행 시간 : 9ms메모리 : 0MB너무 어렵게 풀었다. 직사각형의 좌표들을 전부 갖고 움직일 필요 없이, 직사각형의 겹침 여부를 중점으로 짰다면 훨씬 쉽게 풀 수 있었을 것.재귀에 너무 두려워하지 말자.

평균 : 180'sol : 137' 33''수행 시간 : 9ms메모리 : 0MB항상 페이즈 덩어리별로 주어지는 건 아니니까 문제 유형에 익숙해졌다고 대충 읽지 말자!!!

평균 : 180'sol : 174' 13''수행 시간 : 9ms메모리 : 0MB구현 자체는 이제 다 할 수 있으니까, 보다 간단한 방법을 생각해보자.처음에 설계할 때부터 천천히 고민해보자.삭제 대상이 연결 성분이면 bool 배열보다 좌표 벡터가 더 적합할 때가 많다.상

sol : 119' 49''vector<pair<int, int>> wormholes\[5];를 초기화하려면이렇게 해주어야 한다. 지금의 wormholes->clear();는 wormholes\[0].clear()와 같다. 즉, 첫 번째 벡터만 지워진다.방향

마법의 숲 탐색 Simulation, BFS 평균 : 180' sol : 150' 42'' 수행 시간 : 23ms 메모리 0MB > ### Learnings

평균 : 180'sol : -Learnings문제 접근이 잘못됐음.

평균 : 180'sol : 65' 54''수행 시간 : 8ms메모리 : 0MB전처리가 가능해보이면 먼저 전처리해놓고 접근해도 좋을 것 같은데, 어차피 삼성 1번 문제 특성상 시간이나 메모리 성능을 강제하는 문제는 아니므로, 만약 시간이 남아서 최적화할 시간이 남았다면

평균 : 180'sol : 194' 59''수행 시간 : 14ms메모리 : 0MBLearnings방향 전파 BFS를 실제로 구현해볼 수 있었다.

평균 : 180'sol : 311' 33''수행 시간 : 15ms메모리 : 0MB시야 기능을 설계할 때, 자료구조 '큐'의 본질적인 기능을 자유롭게 활용할 수 있었다면 시간을 크게 줄일 수 있었을 것.메두사의 시선을 상하좌우에 맞춰 대각으로 뻗어나가는 BFS는 잘했는데

sol : 24' 41''골드5는 확실히 쉬워졌다.

sol : 39' 55''Easy

평균 : 180'sol : 187' 38''수행 시간 : 32ms메모리 : 0MB비트마스크식 표현 기술정렬 key를 tuple 하나로 압축하는 기술Optimized VerInitial Ver

sol : 35'33using namespace std;int r, c, t;int dustGridMAX_R;int tempGridMAX_R;// 하, 상, 우, 좌int ds4 = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };int airClea

sol : 31' 21''using namespace std;int n;int gridMAX_N;int sec;bool visitedMAX_N;// 상, 좌, 하, 우int ds4 = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };struct Sha

sol : 97' 55''수행 시간 : 68ms메모리 : 2064KB확실히 쉽게 느껴진다. 회전 구현만 안막혔으면 훨씬 빨리 풀었을듯.상대 좌표에 따른 회전 공식도 너무 어렵게 계산할 필요가 없었다.이전엔 전역에서 직접 좌표를 수학적으로 계산해서 넣었는데, 그냥 각 위

sol : 102' 42''수행 시간 : 16ms메모리 : 2044KB조합 구현

평균 : 180'sol : 197' 06''수행 시간 : 8ms메모리 : 0MB너무 비효율적으로 짜는 것만 아니면 수행 시간 문제로 틀리는 건 거의 없을 것.

평균 : 180'sol : 366' 38''수행 시간 : 24ms메모리 : 0MB애매한 로직은 피를 부른다.어려운 건 잘 구현해놓고 가장 쉬운 로직을 틀려서 디버깅을 3시간 넘게 했다.그래도 오답 원인을 찾아서 해결해서 다행.

sol : 58' 35''BFS의 본질적인 기능에 대해 훨씬 추상적으로 이해할 수 있게 됐다.골드2라기엔 생각보다 너무 쉽게 풀었다.

sol : 113' 04''수행 시간 : 4ms메모리 : 2028KB구조체를 복사할 경우 전부 복사하는 값을 줄이기 위해 <utility> 라이브러리의 swap() fn을 사용하면 복사 대신 소유권만 이전하게 된다.수행 시간 : 0ms메모리 : 2028KB빨리 풀

sol : 115' 12''수행 시간 : 4ms메모리 : 2028KB내 맘대로 판단하지 말자.BFS는 최단거리만 보장해줄 뿐, 실제로는 부모 q에 의존하여 자식 q가 방향 우선순위를 지키지 못하는 경우가 존재한다.

sol : -DFS를 연습해야겠다.

sol : 62' 53''수행 시간 : 252ms메모리 : 2340KB수행 시간을 어떻게 더 줄일 수 있을까?temp grid 필요 X ... 252ms -> 192msshark move에서 시간 대폭 줄일 수 있을 것 같다.\-> 192ms -> 32ms

sol : 72' 55''수행 시간 : 0ms메모리 : 2028KB게임 종료 조건을 변수 하나로 가져가자.\-> O(m)에서 O(1)로 단축.

sol : 159' 59''수행 시간 : 8ms메모리 : 2036KB모두 같은 구슬일 경우 점수 합산 로직을 빼먹어서 1시간 넘게 디버깅했다.

sol : 74' 58''수행 시간 : 4ms메모리 : 2036KB사이즈 계산 잘하기. orders 사이즈를 n^2-1로 해줬어야 하는데 n으로 했다가 암살당했다.

sol : 118' 21''이번엔 CanGo 함수를 사용해서 좀 더 깔끔하게 짜보려 했는데, 여기서 마지막에 return을 선언해주지 않아 오류 코너 케이스가 발생했다.물고기 정보는 굳이 아이디까지 관리할 필요가 없었다. 현재 발생하는 가장 큰 병목은 매번 상어가 물고

sol : 104' 10''수행 시간 : 88ms -> 32ms메모리 : 2996KB하드코딩말고 뭔가 더 멋있게 할 수 있는데 당장 생각이 안났다.cin.tie(0)->sync_with_stdio(0) 이거 꼭 쓰자.

평균 : 180'sol : 187' 24''수행 시간 : 14ms메모리 : 0MB상태 관리를 좀 더 명확하게 하자. 로직은 전부 맞게 짰는데, 상태 관리를 동기화해서 업데이트 해주지 않은 실수로 디버깅에 1시간 넘게 잡아먹혔다.

sol : 63' 40''그리드 밖을 벗어나는 경우의 로직 처리에 대해서 더 깔끔하게 할 수도 있다.

sol : 67' 20''수행 시간 : 28ms메모리 : 2812KB비트마스크를 연습해보자.\-> mask:1 ... 전부 짝수, mask:2 ... 전부 홀수, mask:3 ... 섞임꼭 가지고 있어야 할 정보가 무엇인지 고민하는 습관을 실천해봤다.Fireball은

평균 : 180'sol : 72' 47''수행 시간 : 9ms메모리 : 2MB

sol : 38' 28''수행 시간 : 8ms메모리 : 2028KB전처리를 하면 좋은 문제였다.실전에서도 이렇게 전처리 생각이 먼저 떠오르려나.미지의 영역 탈출도 같은 논리였다.전처리를 하고 수행하니까 8ms에서 0ms로 줄었다.

평균 : 180'sol : 108' 5''수행 시간 : 7ms메모리 : 0MB처음 풀었을 때는 9ms였는데 이번에 7ms가 나왔다.상태관리를 적재적소에서 잘한 것 같다.재귀가 약점이었는데 상태 관리를 위한 분기를 명확하게 처리했다.

sol : 138' 33''깔끔하게 전부 정리하고 풀면 1시간 이내도 가능했을 것.암산 절대금지

sol : 81' 40''수행 시간 : 4ms -> 0ms메모리 : 2032KB다음엔 1시간 이내로 풀어보자.

평균 : 180'sol : 165' 24''수행 시간 : 149ms메모리 : 0MB직사각형이어서 좌표를 전부 가지고 다닐 필요가 없었다.

sol : 101' 09''회전한 채로 그리드를 계속 생각하는 방식이 흥미로웠다.

평균 : 180'sol : 90' 18''수행 시간 : 8ms메모리 : 0MB// 1-baseint n, k, l;int dustGridMAX_N;int robotGridMAX_N;// 우, 하, 좌, 상const int ds4 = { {0, 1}, {1, 0}, {0

평균 : 180'sol : 235' 27''수행 시간 : 13ms메모리 : 0MB두 번째 푸는데도 4시간 걸리는 미친 문제주 병목은 부채꼴 진행

sol : 67' 43''수행 시간 : 0ms메모리 : 2024KBDFS시 매번 독립된 분기 데이터들을 직접 다뤄야 하므로 & 잊지말자.